More Advanced Induction Proofs

The inductive proofs we have considered so far have all only looked back at a single previous case in our inductive hypothesis to prove our inductive step. The reasoning we follow is:

We prove the base case for $n = 1$ , then
We apply the case $n = 1$ to prove the case $n = 2$ via the inductive step, then
We apply the case $n = 2$ to prove the case $n = 3$ via the inductive step, then
We apply the case $n = 3$ to prove the case $n = 4$ via the inductive step,
and this process continues

There are in fact other ways we can formulate an indutive hypothesis which would also allow us to create a similar chain reaction. For example, if we can establish the first $N$ base cases, then we can look back on the previous $N$ cases in our proof of the inductive step. The reasoning would be:

We prove the base cases for $n =1$ to $n = N$ , then
We apply the cases $n = 1$ to $n = N$ to prove the case $n = N+1$ via the inductive step, then
We apply the cases $n = 2$ to $n = N+1$ to prove the case $n = N+2$ via the inductive step,
and this process continues

This is what we would call a multi-step induction proof.

We could even formulate an inductive hypothesis which relies on all previous cases being proven to prove the next case. Once we prove a singular base case, we can again set off the chain reaction using the following

We prove the base case for $n = 1$ , then
We apply the case $n = 1$ to prove the case $n = 2$ via the inductive step, then
We apply the cases $n = 1$ to $n = 2$ to prove the case $n = 3$ via the inductive step, then
We apply the cases $n = 1$ to $n = 3$ to prove the case $n = 4$ via the inductive step,
and this process continues

This is an approach known as strong induction.

More complicated techniques such as forward-backward induction (or double induction) can be used to combine multiple inductive steps to prove a proposition for all values $n \in \N$ . This can be used when a single induction process is not able to prove the result for all values directly.

After establishing a base case $n = 1$ , the forward induction uses an inductive step to prove the proposition holds for progressively larger values, but leaves some gaps behind (for example, it may show that if the result holds for $n = k$ , then it must hold for $n = 2k$ ).

A second backwards induction shows that if the result holds for $n = k$ , then it must also hold for $n = k - 1$ , which can be used to 'fill in the gaps' from the first induction.

...