Proof by Mathematical Induction

Starting point: what you already know

• Sigma notation: $\sum _{k=1}^{n}k=1+2+\cdots +n$.
• From arithmetic series: $1+2+\cdots +n=\frac{n(n+1)}{2}$.
• Divisible by 3 means equal to $3M$ for some whole number $M$.
• Algebra skills: factorising, expanding, finding a common denominator.

Why we need proof

The pattern $1=1^2$, $1+3=2^2$, $1+3+5=3^2$ suggests that the first $n$ odd numbers add to $n^2$. Checking more examples makes it believable, but checking a million cases still does not prove it for the next one. Induction proves it for every $n$ at once.

The structure

Let $P(n)$ be the statement you want to prove.

The assumption in step 2 is called the inductive hypothesis. You are not assuming what you want to prove. You are proving "if it works for one domino, it works for the next".

Proving sums

Proving divisibility

Quick summary

• Induction has two steps: prove the base case, then show that if it is true for $k$, it is true for $k+1$.
• For sums, add the next term to the assumed sum and simplify to the target.
• For divisibility, write the assumption as divisor $\times M$, substitute, then factor out the divisor.
• Finish with the conclusion sentence. Missing either step means there is no proof.

Quiz