**Navigation**

Topics | Register • News • History • How to • Sequences statistics • Template prototypes |

# 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]\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
_{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]\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]