# 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:

## 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^{[1]}. - the
**induction step**: assume the statement is true for some value, , and show that it then would also be true for . - the
**conclusion**: the statement is true for all positive integers^{[2]}.

## Introductory Example

Say we want to prove by induction^{[3]}, for all positive integers .

For simplicity, we'll call this statement , like this:

#### Base Case

Let .

Looking at when , the left-hand side is .

The right-hand side of is .

As we expect, they are the same. This proves that is true for the "base case" of .

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 , 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, .

So, here, we assume that

Note that is different from here. is representing one specific positive integer, while is representing all positive integers generally. That makes different from , even though they may look the same.

##### Induction Step: Goal

We now want to show that the statement is true for , whenever our assumption is true.

So, we want to show that .

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 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 terms into a sum of terms, plus an extra final term.

Starting with the left-hand side:

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:

- The statement is true for .
**If**the statement is true for ,**then**it is true for .- 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

## Footnotes

- β There are exceptions. We may need to start with a different number or need two base cases.
- β Technically, this doesn't have to be positive integers. As long as you can always identify the next number in a sequence (a 'successor' function), you can potentially use induction.
- β You probably should be able to prove this with a simpler method, but we're using it here as an example for proof by induction.