Introduction to Proof by Induction

Mathematical Induction is a direct proof technique used to prove certain mathematical statements involving natural numbers.

Many students have trouble getting their heads around the technique, and perhaps one reason for its apparent mysteriousness is that the procedure lacks "explanatory" value. We might be able to satisfy ourselves by working through a series of logical steps to prove a result, but we still can be left with an uncertainty about why something ought to be true. More will be said about this later.

 

Mathematical induction - a simple example

But for now we will explore the idea of mathematical induction using a simple example:

We start by looking at the proof of a proposition that any summing of consecutive positive odd integers starting from $1$1 will always lead to a square number.

For example,

• $1=1^2$1=12
• $1+3=4=2^2$1+3=4=22
• $1+3+5=9=3^2$1+3+5=9=32
• $1+3+5+7=16=4^2$1+3+5+7=16=42

Clearly, the proposition seems to be true, at least up to the fourth case where the sum of the first $4$4 odd numbers equals $4^2$42. We could, of course, test the assertion further by using higher and higher odd numbers, but we could only ever claim it true for a certain number of cases. It does not constitute proof just as finding white swans everywhere you look doesn't constitute a proof of the statement "All swans are white". 

In the real world, a proof by mathematical induction starts by noticing a pattern and then boldly making an assertion that the pattern might continue indefinitely. Of course, we need to formalise the assertion by using algebraic symbols. 

In the case we are dealing with, we might recall that odd numbers are all of the form $2n-1$2n−1 (for example if $n=1$n=1, then $2n-1$2n−1 becomes $2\times1-1=1$2×1−1=1, and if $n=2$n=2, then $2\times2-1$2×2−1 becomes $2\times2-1=3$2×2−1=3, etc.). 

We suspect that summing $n$n odd numbers up to and including the number $\left(2n-1\right)$(2n−1) will always become $n^2$n2. 

So, using $A_n$An​ to denote our assertion, we write:

$A_n:$An​:     $1+3+5+7+...+\left(2n-1\right)=n^2$1+3+5+7+...+(2n−1)=n2

So far, so good...

We have shown the statement is true for the first four cases, so we take a huge inductive step and assume that it is true for the $k^{th}$kth case (Note that this is different to assuming that it is true for all cases, but rather we are assuming it is true for some particular case $k$k ).

So we assume that the following statement is true:

$A_k:$Ak​:  Assume that   $1+3+5+7+...+\left(2k-1\right)=k^2$1+3+5+7+...+(2k−1)=k2.

We now ask the following important question:

If it were true for this $k^{th}$kth case, would it necessarily follow that it would also be true for the very next case? In other words, would it be true for the $\left(k+1\right)^{th}$(k+1)th case as well?

How do we write down the $\left(k+1\right)^{th}$(k+1)th case?

We do it by simply adding the $\left(k+1\right)^{th}$(k+1)th odd number to the left hand side, and then change the $k$k to $\left(k+1\right)$(k+1) on the right hand side, so that it becomes $\left(k+1\right)^2$(k+1)2. 

Thus:

$A_{k+1}:$Ak+1​:      $1+3+5+7+...+\left(2k-1\right)+\left[2\left(k+1\right)-1\right]=\left(k+1\right)^2$1+3+5+7+...+(2k−1)+[2(k+1)−1]=(k+1)2

Or, more simply:

$A_{k+1}:$Ak+1​:     $1+3+5+7+...+\left(2k-1\right)+\left(2k+1\right)=\left(k+1\right)^2$1+3+5+7+...+(2k−1)+(2k+1)=(k+1)2

Look carefully at $A_{k+1}$Ak+1​, and satisfy yourself that this makes sense. The task ahead of us is to prove this last statement true, assuming that $A_k$Ak​ is true.

Proving $A_{k+1}$Ak+1​ means specifically proving that the left hand side of $A_{k+1}$Ak+1​ equals its right hand side.

Since we can assume that $1+3+5+7+...+\left(2k-1\right)=k^2$1+3+5+7+...+(2k−1)=k2, then we have

$A_{k+1}:$Ak+1​:           $k^2+\left(2k+1\right)=\left(k+1\right)^2$k2+(2k+1)=(k+1)2 

The left hand side simplifies as:

$LHS$LHS	$=$=	$k^2+\left(2k+1\right)$k2+(2k+1)
	$=$=	$k^2+2k+1$k2+2k+1
	$=$=	$\left(k+1\right)^2$(k+1)2
	$=$=	$RHS$RHS

Using logic notation what we have just done is proven the proposition $A_k\Rightarrow A_{k+1}$Ak​⇒Ak+1​. That is, given $A_k$Ak​ is true then $A_{k+1}$Ak+1​ is true also.

Of course the conditional proposition is really saying that if the case where $k=1$k=1 were true, then the case where $k=2$k=2 would be true also. But the cases where $k=1,2,3$k=1,2,3 and $4$4 have already been shown to be true by direct calculation. The pattern we noticed was the original reason we started the induction proof.

So, because $k=4$k=4 is true $(1+3+5+7=4^2)$(1+3+5+7=42), then because of our conditional proposition $A_k\Rightarrow A_{k+1}$Ak​⇒Ak+1​, we know that $k=5$k=5 is true also $(1+3+5+7+9=5^2)$(1+3+5+7+9=52). We could continue using the conditional proposition to demonstrate that $k=6,7,8,...n$k=6,7,8,...n are all true. Just like dominoes knocking dominoes, on and on forever, we prove the pattern for all $n$n. 

 

Summary of procedure 

Here is a quick five point review of what we did. We:

1. Saw a pattern $A_1,A_2,A_3,A_4,...$A1​,A2​,A3​,A4​,...
2. Asserted that the pattern could be written down as $A_n$An​, suspecting it was true for all $n$n
3. Made the assumption that it was true for a particular $A_k$Ak​
4. Proved that, given the assumption $A_k$Ak​, then $A_{k+1}$Ak+1​ was also true
5. Finally argued that if $A_1$A1​ was true, then because of  $A_k\Rightarrow A_{k+1}$Ak​⇒Ak+1​, then $A_2$A2​ was true also, and if $A_2$A2​ was true, then also $A_3$A3​ was true, etc. so that it must be true for all $n$n. 

 

Does mathematical induction answer the why?

So we now know that the sum of consecutive odd numbers up to the$n^{th}$nth odd number is $n^2$n2. But did our proof really provide a satisfactory explanation to the reason why this should be the case? Are you satisfied that you understand why the sum becomes square?

Let's look at the pattern differently, as shown in this diagram:

The diagram offers a fresh perspective to the problem. Here we see the odd numbers stacking up neatly into a square. We can imagine the pattern continuing indefinitely in this way, and as such this visual becomes explanatory - perhaps far more explanatory than an inductive proof of the same pattern. We understand, at a deeper conceptual level, why the sum of consecutive odds become squares. 

However, not all patterns lend themselves to visual depictions like this. We need robust techniques to generalise many of these patterns and this is why more formal approaches are required. 

 

Instances where Mathematical Induction MAY be useful 

Whenever we notice a pattern that seems to be true for every natural number n, we can try to prove it so by using mathematical induction. Without proving any of the following examples, we will see if mathematical induction might be a sensible starting point:

Example 1

Janet notices that the sum of the cubes of the consecutive positive integers is a square number. She writes down the first few cases:

$A_1$A1​	$:$:	$1^3=1$13=1
$A_2$A2​	$:$:	$1^3+2^3=9$13+23=9
$A_3$A3​	$:$:	$1^3+2^3+3^3=36$13+23+33=36
$A_4$A4​	$:$:	$1^3+2^3+3^3+4^3=100$13+23+33+43=100

Janet becomes curious about the particular squares generated, and then hits upon an idea.

She realises that $A_1$A1​ results in the square $1^2$12, and $A_2$A2​ results in the square $\left(1+2\right)^2$(1+2)2, and $A_3$A3​ results in the square $\left(1+2+3\right)^2$(1+2+3)2 and $A_4$A4​ results in the square $\left(1+2+3+4\right)^2$(1+2+3+4)2 and so on.

Recalling the arithmetic series result for the sum of consecutive integers given by $1+2+3+4+...+n=\frac{n\left(n+1\right)}{2}$1+2+3+4+...+n=n(n+1)2​, Janet boldly conjectures the following:

$A_n:$An​:     $1^3+2^3+3^3+...+n^3=\left[\frac{n\left(n+1\right)}{2}\right]^2=\frac{n^2\left(n+1\right)^2}{4}$13+23+33+...+n3=[n(n+1)2​]2=n2(n+1)24​

 

Example 2

Peter notices that for integer $n$n greater than $4$4, $2^n>n^2$2n>n2.

So for $n=5$n=5,  $2^5=32$25=32 and $5^2=25$52=25. For $n=6$n=6,  $2^6=64$26=64 and $6^2=36$62=36.

From the first few cases, it looks as though the proposition is true.

Peter decides to try to prove the following using mathematical induction:

For $n>4$n>4

$A_n:$An​:     $2^n>n^2$2n>n2 

Peter then reasons that assuming the proposition $A_k$Ak​, given by $2^k>k^2$2k>k2 for integers $k>4$k>4, the task is to prove the following:

$A_{k+1}:$Ak+1​:      $2^{k+1}>\left(k+1\right)^2$2k+1>(k+1)2. 

Example 3

Sandy conjectures that for any positive integer $n$n, $8^n-5^n$8n−5n is divisible by $5$5.

He tests the first three cases and they both work. 

Sandy then assumes $A_k$Ak​ - specifically that $8^k-5^k=5p$8k−5k=5p where $p$p is some integer.

He then attempts to prove $A_{k+1}$Ak+1​, specifically that $8^{k+1}-5^{k+1}=5q$8k+1−5k+1=5q where $q$q is some other integer. 

After a little work, Sandy proves that it is indeed true.

Example 4

Rebecca was substituting positive integer values into the expression $n^2+n+41$n2+n+41 and coming up with answers that were all prime. Here is her table:

$n$n	$n^2+n+41$n2+n+41
$1$1	$43$43
$2$2	$47$47
$3$3	$53$53
$4$4	$61$61
$5$5	$71$71

Rebecca began to believe that she had found a formula for deriving prime numbers. She continued trying numbers for a while, but then decided to prove it using mathematical induction.

Rebecca reasoned as follows:

$A_1$A1​ through to $A_5$A5​ work

Assume $A_k$Ak​ so that for some $k$k, $k^2+k+41$k2+k+41  is prime.

Then prove $A_{k+1}$Ak+1​, the proposition that $\left(k+1\right)^2+\left(k+1\right)+41$(k+1)2+(k+1)+41 is prime also.

Rebecca begins to simplify $A_{k+1}$Ak+1​:

$A_{k+1}$Ak+1​	$=$=	$\left(k+1\right)^2+\left(k+1\right)+41$(k+1)2+(k+1)+41
	$=$=	$k^2+2k+1+k+1+41$k2+2k+1+k+1+41
	$=$=	$\left(k^2+k+41\right)+2\left(k+1\right)$(k2+k+41)+2(k+1)

Uncertain as to how to proceed, Rebecca thinks about it more. After a while, she realises her conjecture breaks down completely when $k=41$k=41, since $41^2+41+41$412+41+41 is divisible by $41$41 because each part is divisible by $41$41. This means here attempt to prove otherwise has failed.

Worked examples

Question 1

Question 2

Question 3