Proof by Induction

Proof by Induction is a method of proving that a statement is true for all positive integers.

Prerequisites

We'll assume that you know about:

• Number Systems: Real, Rational, Integer
• Sum Notation
• Direct Proof: "Show That"

Concept

The structure of Proof by Induction is always the same. The goal to prove a statement is true for all positive integers, and we'll take it in three steps:

• show the statement to be true for a base case, normally $n=1$.
• the induction step: assume the statement is true for some value, $n=k$, and show that it then would also be true for $n=k+1$.
• the conclusion: the statement is true for all positive integers.

Introductory Example

Say we want to prove $\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$ by induction, for all positive integers $n$.

For simplicity, we'll call this statement $(*)$, like this:

$\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}\quad (*)$

Base Case

Let $n=1$.

Looking at $(*)$ when $n=1$, the left-hand side is $\sum _{i=1}^{n}i=\sum _{i=1}^{1}i=1$.

The right-hand side of $(*)$ is ${\frac {n(n+1)}{2}}={\frac {1(1+1)}{2}}=1$.

As we expect, they are the same. This proves that $(*)$ is true for the "base case" of $n=1$.

When writing this out for an examiner, it's important to show that you have genuinely looked at both sides. If you take a short-cut here, it might not be clear that you have understood what to do.

Induction Step

It might now be tempting to look at $n=2,n=3,n=4$, etc. However, the goal is to prove the statement for every positive integer - so this would be an infinite process, requiring infinite work. We won't do this.

The key to induction is to take a different approach: if we know the statement is true for one integer, can we prove it for the next integer (the successor).

Induction Step: Assumption

We always start the induction step with an assumption: that the statement $(*)$ is true for a particular value, $n=k$.

So, here, we assume that $\sum _{i=1}^{k}i={\frac {k(k+1)}{2}}\quad (\dagger )$

Note that $k$ is different from $n$ here. $k$ is representing one specific positive integer, while $n$ is representing all positive integers generally. That makes $(\dagger )$ different from $(*)$, even though they may look the same.

Induction Step: Goal

We now want to show that the statement $(*)$ is true for $n=k+1$, whenever our assumption is true.

So, we want to show that $\sum _{i=1}^{k+1}i={\frac {(k+1)((k+1)+1)}{2}}={\frac {(k+1)(k+2)}{2}}$.

Be warned! This has become a "show that" question - we must be careful not to use circular logic. I like to write this goal in a cloud to the side, to remind myself what the goal is and also remind myself not to work with it.

Induction Step: "The Meat"

Typically, we plan to start from one side of the goal, and work towards the other side, as in a "show that" question.

We expect, at some point, to use the assumption $(\dagger )$ above. That means we will need to "force" the assumption to appear by extracting it algebraically out of what we have. This is likely to mean breaking some usual rules of algebraic simplification: we may un-simplify. In this case, we'll break up our sum of $k+1$ terms into a sum of $k$ terms, plus an extra final term.

Starting with the left-hand side:

${\begin{aligned}\sum _{i=1}^{k+1}i&=\sum _{i=1}^{k}i+(k+1)&\quad &{\text{split the last term out of the sum}}\\&={\frac {(k)(k+1)}{2}}+(k+1)&&{\text{apply the assumption from }}(\dagger )\\&={\frac {k+1}{2}}(k+2)&&{\text{your choice of algebra}}\\&={\frac {(k+1)((k+1)+1)}{2}}&&{\text{it's cute to rewrite so you can see the }}k+1\\\end{aligned}}$

We have reached the goal's right-hand-side, so the induction step is complete.

Conclusion(s)

Formally speaking, Proof by Induction needs three separate lines of conclusion:

1. The statement $(*)$ is true for $n=1$.
2. If the statement $(*)$ is true for $n=k$, then it is true for $n=k+1$.
3. Therefore, the statement $(*)$ is true for all positive integers.

These statements are subtle and it's important to capture the ideas behind them exactly.

However, once you understand this, the conclusion is basically always going to be the same - there is very little variation.

Next Steps

Proof by Induction is a very powerful tool and "the meat" can look slightly different in different contexts. It's worth it to look at further examples:

• Proof by Induction: Divisibility
• Proof by Induction: Recursion
• Proof by Induction: Matrices
• Proof by Induction: Inequalities
• Proof by Induction: "Strong" Induction