# Mathematical Induction

*Mathematical Induction (MI)* is an extremely important tool in Mathematics.

First of all you should never confuse MI with Inductive Attitude in Science. The latter is just a process of establishing general principles from particular cases.

MI is a way of *proving* math statements for all integers (perhaps excluding a finite number) [1] says:

Statements proved by math induction all depend on an integer, say, n. For example,

(1) 1 + 3 + 5 + ... + (2n - 1) = n^{2}

(2) If x_{1}, x_{2}, ..., x_{n} > 0 then (x_{1} + x_{2} + ... + x_{n})/n ≥ (x_{1}·x_{2}·...·x_{n})^{1/n}

etc. n here is an "arbitrary" integer.

It's convenient to talk about a statement P(n). For (1), P(1) says that ^{2}^{2}^{2}

Assume you want to prove that for some statement P, P(n) is true for all n starting with *Principle* (or Axiom) of *Math Induction* states that, to this end, one should accomplish just two steps:

- Prove that P(1) is true.
- Assume that P(k) is true for some k. Derive from here that P(k+1) is also true.

The idea of MI is that a finite number of steps may be needed to prove an infinite number of statements P(1), P(2), P(3), ....

Let's prove (1). We already saw that P(1) is true. Assume that, for an arbitrary k, P(k) is also
true, i.e. ^{2}.

| = |

= k^{2} + (2k+1) | |

= (k+1)^{2} |

Which exactly means that P(k+1) holds. (For

Intuitively, the inductive (second) step allows one to say, look P(1) is true and implies P(2). Therefore P(2) is true. But P(2) implies P(3). Therefore P(3) is true which implies P(4) and so on. Math induction is just a shortcut that collapses an infinite number of such steps into the two above.

In Science, *inductive attitude* would be to check a few first statements, say, P(1), P(2), P(3), P(4), and then assert that P(n) holds for all n. The inductive step "P(k) implies

## Remark

- Often it is impractical to start with
n = 1. MI applies with any starting integer n_{0}. The result is then proved for all n from n_{0}on. - Sometimes, instead of 2., one assumes 2':

Assume that P(m) is true for all

m < (k + 1). Derive from here that P(k+1) is also true. The two approaches are equivalent, because one may consider statement Q:

Q(n) = P(1) and P(2) and ... and P(n) , so that Q(n) is true iff P(1), P(2), ..., P(n) are all true.

This variant goes by the name of *Complete Induction* or *Strong Induction*.

In problem solving, mathematical induction is not only a means of proving an existing formula, but also a powerful methodology for finding such formulas in the first place. When used in this manner MI shows to be an outgrowth of (scientific) inductive reasoning - making conjectures on the basis of a finite set of observations.

There are other examples proved by MI:

- A 1-1 correspondence
- A Low Bound for 1/2 * 3/4 * 5/6 * ... * (2n-1)/2n
- A Number Theoretic Problem With the Floor Function
- A Problem of Divisibility by 5
^{n} - A Problem of Satisfying Inequalities
- A Proof by Game for a Sum of a Convergent Series
- A Property of the fusc() Function
- All Powers of x are Constant
- An Equation in Factorials
- An Equation in Reciprocals
- An Extension of the AM-GM Inequality
- An Extension of van Schooten's Theorem
- An Identity From the 2010 China Mathematical Competition
- An Inequality by Uncommon Induction
- An Inequality for Grade 8
- An Inequality in Integers III
- An Inequality in Two Or More Variables
- An Inequality with Permutations, I
- An Inequality with Permutations, II
- An infinite exponent
- An Olympiad Problem With the Floor Function
- Another pigeonhole problem
- Binary Euclid's algorithm
- Binet's Formula by Induction
- Book Index Range
- Breaking Chocolate Bars
- Cassini's Identity
- Chinese Remainder Theorem
- Committee Chairs
- Constructible Numbers
- Construction Problem
- Continued Fractions
- Counting Triangles
- Counting Triangles II
- Cutting Squares
- Dan Sitaru's Inequality by Induction
- Deceptive Appearances
- Diagonal Count
- Difference of the Cantor Sets
- Diophantine Quadratic Equation in Three Variables
- Divisibility by Powers of 2
- Euclid's Algorithm
- Expansion of Integers in an Integer Base
- Factorial Products
- Farey series
- Fermat's Little Theorem
- Fractions on a Binary Tree II
- Four Weighings Suffice
- Geometric Illustration of a Convergent Series
- Gladiator Game
- Golden Ratio is Irrational
- Golomb's inductive proof of a tromino theorem
- Graph without 3-Cycles
- Groups of Permutations
- Guessing Two Consecutive Integers
- Hamming and Levenshtein distance functions
- Helly's Theorem
- Inequality 1/2·3/4·5/6· ... ·99/100 < 1/10
- Inequality
(1 + 1 ^{-3})(1 + 2^{-3})(1 + 2^{-3})...(1 + n^{-3}) < 3 - Inequality 1 + 2
^{-2}+ 3^{-2}+ 4^{-2}+ ... + n^{-2}< 2 - Inequality between arithmetic and geometric means
- Inequality for Integer Sequences
- Inequality for Integer Sequences II
- Inequality of a Series of Square Roots
- Inequality with Nested Radicals II
- Infinite Latin Squares
- Infinitude of Primes Via Fermat Numbers
- Infinitude of Primes Via Lower Bounds
- Infinitude of Primes Via Powers of 2
- Infinitude of Primes Via *-Sets
- Integers and Rectangles: a Proof by Induction
- Integers With Digits 1 and 2 and Residues Modulo Powers of 2
- Integral Domains: Remarks and Examples
- Irrationality of k-th roots
- Jensen's Inequality
- Josephus problem
- Linear Functions
- Many Jugs to One II
- Marriage Problem
- Mathematical Induction
- Mathematicians Doze Off
- Meisters' Two Ears Theorem
- Morley's Pursuit of Incidence
- Newton's and Maclaurin's Inequalities
- Nested Radicals
- Nontrivial Ramsey numbers R(m, n) exist for all natural n and m
- Numbers That Divide the Others' Sum
- Pennies in Boxes
- Perimeters of Convex Polygons, One within the Other
- Pigeonhole problem
- Pigeonhole principle complements math induction
- Poncelet Theorem
- Prim's and Kruskal's algorithms find a minimum spanning tree
- Prime Sums in Pairs
- Problem on an Infinite Checkerboard
- Property of irreducible fractions on the Stern-Brocot tree
- Property of the Powers of 2
- Property of Two Pencils of Parallel Lines
- Ramsey's Numbers
- Rabbits Reproduce; Integers Don't
- Right Replacement
- Self-documenting Iterations
- Sierpinski Gasket
- Sierpinski Gasket and Tower of Hanoi
- Simple Cellular Automaton
- Solitaire on the Circle
- Splitting piles
- Stern-Brocot Tree
- Stern-Brocot Tree II
- Strange Integers: Divisors and Primes
- Subsets and Intersections
- Sum of Absolute Values
- The Regula Falsi - Iterated
- The Somos sequences
- The union of a finite number of cycles of a connected (di)graph is a cycle.
- Three Jugs - Equal Amounts
- Tony Foster's Integer Powers in Pascal's Triangle
- Tromino Puzzle: Deficient Squares
- Two Color Coloring of the Plane
- Two Products: Constraint and Inequality
- Ways To Count

## Reference

- D. Fomin, S. Genkin, I. Itenberg,
*Mathematical Circles (Russian Experience)*, AMS, 1996 - R. Graham, D. Knuth, O. Patashnik,
*Concrete Mathematics*, 2nd edition, Addison-Wesley, 1994. - R.Courant and H.Robbins,
*What is Mathematics?*, Oxford University Press, 1996

### On the Web

- An online and iPod video by Julio de la Yncera

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny70787926