Proof by induction

From Prime-Wiki
Jump to: navigation, search

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 n0. This value n0 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]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]\sum_{k=1}^{n}\,(2k-1)\,=\,n^{2}[/math]
  • Step 1
Show that the statement is true when n = 1
[math]\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]1 \leq n \leq d[/math]. In particular assume it is valid for d.
[math]\sum_{k=1}^{d}\,(2k-1)\,=\,d^{2}[/math]
  • Step 3
Show that the statement is true for the value d+1
[math]\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]\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]\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]\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]\prod_{k=1}^{d+1}\left(1\,+\,\frac{1}{k}\right)\,=\,\left(d\,+\,1\right)\left(1\,+\,\frac{1}{d+1}\right)[/math]
[math]=\,\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]\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]\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]\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]\sum_{k=1}^{d+1}k^{3}\,=\,\frac{d^{2}(d+1)^{2}}{4}\,+\,(d+1)^{3}[/math]
Taking [math](d+1)^{2}[/math] as a factor leaves
[math]\frac{d^{2}}{4}\,+\,(d+1)[/math]
[math]=\,\frac{d^{2}+4(d+1)}{4}[/math]
[math]=\,\frac{(d+2)^{2}}{4}[/math]
so that: [math]\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 F0, F1, F2, F3, ..., the Fibonnacci sequence 0, 1, 1, 2, 3, 5, 8, 13, ... where Fn = Fn-1 + Fn-2 and [math]\phi [/math] = 1.61803... a number such that [math]\phi^2 = \phi + 1[/math].

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

  • Step 1
Show that the statement is true when n = 1.
[math]F_1 = 1 = \phi^0[/math]
Show that the statement is true when n = 2.
[math]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]F_{d-1} \leq \phi^{d-2}[/math]
[math]F_{d} \leq \phi^{d-1}[/math]
  • Step 3
Show that the statement is true for the value d+1.
Adding both inequalities:
[math]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]\phi[/math], the last expression parenthesized is equal to [math]\phi ^2[/math]. So finally,
[math]F_{d+1} \leq \phi ^{d-2} \phi^2 = \phi ^d[/math]

External links