# 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
_{0}. This value n_{0}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.

- Show that the statement is true for an initial value of n, say 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 F
_{0}, F_{1}, F_{2}, F_{3}, ..., the Fibonnacci sequence 0, 1, 1, 2, 3, 5, 8, 13, ... where F_{n}= F_{n-1}+ F_{n-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]