Proof by induction

The proof by induction is a technique for proving mathematical theorems that takes advantage of the structure of the natural numbers as described by the Peano Postulates. Proof by induction is normally performed in three steps:

• Step 1

Show that the statement is true for an initial value of n, say n₀. This value n₀ is normally taken to be 1, but that is not essential. In some proofs (see example 4 below) we have to show that the statement is true for several values of n.

• Step 2

Assume that the statement is true for all values of n such that [math]\displaystyle{ n_0 \leq n \leq d }[/math]

• Step 3

Show that the statement is true for the value d+1

Example 1

Prove by induction that:

[math]\displaystyle{ \sum_{k=1}^{n}\,(2k-1)\,=\,n^{2} }[/math]

• Step 1

Show that the statement is true when n = 1

[math]\displaystyle{ \sum_{k=1}^{1}\,(2k-1)\,=\,2-1\,=\,1^{2} }[/math]

• Step 2

Assume that the statement is true for all values of n such that [math]\displaystyle{ 1 \leq n \leq d }[/math]. In particular assume it is valid for d.

[math]\displaystyle{ \sum_{k=1}^{d}\,(2k-1)\,=\,d^{2} }[/math]

• Step 3

Show that the statement is true for the value d+1

[math]\displaystyle{ \sum_{k=1}^{d+1}(2k\,-1)\,=\,d^{2}\,+\,2(d+1)-1\ =\ d^{2}\,+\,2d+1\ =\ (d+1)^{2} }[/math]

when the fact that the formula has the same form as at Step 1 and Step 2, proves the statement is true.

Example 2

Prove by induction that:

[math]\displaystyle{ \prod_{k=1}^{n}\left(1\,+\,\frac{1}{k}\right)\,=\,n+1 }[/math]

• Step 1

Show that the statement is true when n = 1

[math]\displaystyle{ \prod_{k=1}^{1}\left(1\,+\,\frac{1}{k}\right)\,=\,1\,+\,\frac{1}{1}\,=\,2 }[/math]

• Step 2

Assume that the statement is true for some value of n > 1, say d

[math]\displaystyle{ \prod_{k=1}^{d}\left(1\,+\,\frac{1}{k}\right)\,=\,d\,+\,1 }[/math]

• Step 3

Show that the statement is true for the value d+1

[math]\displaystyle{ \prod_{k=1}^{d+1}\left(1\,+\,\frac{1}{k}\right)\,=\,\left(d\,+\,1\right)\left(1\,+\,\frac{1}{d+1}\right) }[/math]

[math]\displaystyle{ =\,\left(d\,+\,1\right)\,+\,1 }[/math]

When we have, by the addition of the next term, produced an equation of the same form and so proved, by induction, that the statement is true.

Example 3

Prove by induction that:

[math]\displaystyle{ \sum_{k=1}^{n}k^{3}\,=\,\frac{n^{2}(n+1)^{2}}{4} }[/math]

• Step 1

Show that the statement is true when n = 1

[math]\displaystyle{ \sum_{k=1}^{1}k^{3}\,=\,1\,=\,\frac{4}{4}\,=\,\frac{1(2)^{2}}{4} }[/math]

• Step 2

Assume that the statement is true for some value of n > 1, say d

[math]\displaystyle{ \sum_{k=1}^{d}k^{3}\,=\,\frac{d^{2}(d+1)^{2}}{4} }[/math]

• Step 3

Show that the statement is true for the value d+1

[math]\displaystyle{ \sum_{k=1}^{d+1}k^{3}\,=\,\frac{d^{2}(d+1)^{2}}{4}\,+\,(d+1)^{3} }[/math]

Taking [math]\displaystyle{ (d+1)^{2} }[/math] as a factor leaves

[math]\displaystyle{ \frac{d^{2}}{4}\,+\,(d+1) }[/math]

[math]\displaystyle{ =\,\frac{d^{2}+4(d+1)}{4} }[/math]

[math]\displaystyle{ =\,\frac{(d+2)^{2}}{4} }[/math]

so that: [math]\displaystyle{ \sum_{k=1}^{d+1}k^{3}\,=\,\frac{(d+1)^{2}(d+2)^{2}}{4} }[/math]

When we have, by the addition of the next term, produced an equation of the same form and so proved, by induction, that the statement is true.

Example 4

This is a more complicated example that shows the power of this method.

Let F₀, F₁, F₂, F₃, ..., the Fibonnacci sequence 0, 1, 1, 2, 3, 5, 8, 13, ... where F_n = F_n-1 + F_n-2 and [math]\displaystyle{ \phi }[/math] = 1.61803... a number such that [math]\displaystyle{ \phi^2 = \phi + 1 }[/math].

Prove by induction that [math]\displaystyle{ F_n \leq \phi^{n-1} }[/math].

• Step 1

Show that the statement is true when n = 1.

[math]\displaystyle{ F_1 = 1 = \phi^0 }[/math]

Show that the statement is true when n = 2.

[math]\displaystyle{ F_2 = 1 \,\lt \, \phi^1 = 1.61803... }[/math]

• Step 2

Assume that the statement is true for n = d-1 and n = d, where d > 2.

[math]\displaystyle{ F_{d-1} \leq \phi^{d-2} }[/math]

[math]\displaystyle{ F_{d} \leq \phi^{d-1} }[/math]

• Step 3

Show that the statement is true for the value d+1.

Adding both inequalities:

[math]\displaystyle{ F_{d+1} = F_d + F_{d-1} \leq \phi^{d-1} + \phi^{d-2} = \phi^{d-2} (\phi + 1) }[/math]

From the definition of [math]\displaystyle{ \phi }[/math], the last expression parenthesized is equal to [math]\displaystyle{ \phi ^2 }[/math]. So finally,

[math]\displaystyle{ F_{d+1} \leq \phi ^{d-2} \phi^2 = \phi ^d }[/math]

External links

• Wikipedia