# MEC Lesson 4 – Proof by induction

So far we have seen two different types of mathematical proof:

1. Direct proof e.g. Pythagoras’ theorem, Euler’s formula ($V-E+F=1$)
2. Proof by contradiction e.g. Infinitely many primes

In today’s lesson we will learn a third type of proof called proof by induction. Let’s motivate the idea by working through an example. We are going to try and prove the following formula for summing the first $n$ numbers.

$\displaystyle 1+2+3+\cdots+n=\frac{n(n+1)}{2}$

Worksheet on Induction

So what’s the idea of proof by induction? A helpful analogy is found in dominoes. Think of each domino as representing one of the statements we want to prove. The induction argument is based on the idea that knocking one domino over (by proving that statement) causes all the other dominoes to get knocked over, one by one. (See for example this video)

Let’s recap the argument. We were able to verify that the formula for summing the first $n$ numbers holds in some small examples by hand. However, we want to be able to use the formula for any number $n$, for example, to add the first 1,000,000 numbers, which we clearly don’t want to do by hand. So we proved the inductive step which was to show that if the formula holds for $n=k-1$ then the formula holds for $n=k$. This is the part which says, if one domino falls, then so does the next one.

It is important to note that there are two steps involved when doing a proof by induction.

1. Base Case: First we have to show that the formula holds for $n=1$. In our example this was easy, we just verified that that formula read $1=1$!
2. Inductive step. Then we have to show that if the formula holds for $n=k-1$ then the formula holds for $n=k$.

By the base case we know the formula holds for $n=1$. Now by the inductive step, since we know the formula holds for $n=1$ we can conclude that the formula must hold for $n=2$. But since the formula holds for $n=2$, we can deduce from the inductive step that the formula must hold for $n=3$. But since the formula holds for $n=3$, we can deduce from the inductive step that the formula must hold for $n=4$. Etc, etc….

This kind of argument is very useful for proving formulas that depend on $n$, for example:

• Formula for the sum of squares

$\displaystyle 1^2 + 2^2 + 3^2 + \cdots n^2 = \frac{n(n+1)(2n+1)}{6}$

$\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}$