Proof by induction: writing the step that proves it

The four parts, and none of them optional

Every induction proof has the same four parts and a marker is looking for all four. Show the statement holds for the first value. Assume it holds for some particular value, and say which. Prove it then holds for the next one. Conclude, naming the principle.

The first part is one line and people skip it because it is easy. It is a mark, and without it the whole chain is attached to nothing - you would have proved that if it is ever true it stays true, which is not the same as it being true.

The last part is also one line and it is also a mark. Because it is true for the first value and true for the next whenever it is true for one, it is true for all of them by induction. Write it out. A proof that stops after the algebra has not said what the algebra proved.

• Base case - test the first value. One line.
• Assumption - assume it for n equals k. Say what you are assuming.
• Inductive step - prove it for k plus one, using the assumption.
• Conclusion - name the principle and what follows from it.

Say what you are assuming, and then use it

Write the assumption out in full, with k in it. Not assume true for n equals k - write the actual statement with k substituted, because that expression is the thing you are going to substitute later, and if it is not on the page you will have to reconstruct it under pressure.

Then, in the inductive step, point at the moment you use it. The single most common gap in an otherwise complete proof is an inductive step that never refers back to the assumption: if you could have got to the result without assuming anything, you have not done induction, and often you have quietly assumed the thing you were proving.

Some markers want the phrase by the assumption written at that line. Write it anyway. It costs four words and it makes the one thing the proof is about visible.

How the step is supposed to go

State what you are trying to show for k plus one before you start manipulating - the target, written out. Working towards a target you have written down is a different activity from working forwards and hoping.

Then start from one side, usually the left, and get to the other. Do not start by writing the thing you are trying to prove as an equation and doing the same operation to both sides until you reach something true. That proves the statement is consistent, not that it holds, and it is marked accordingly.

For a sum, the move is almost always the same: the sum to k plus one is the sum to k plus the next term, the sum to k is what you assumed, so substitute it and then do algebra until it matches the target. If you can see that shape, most sum questions are one substitution and some factorising.

Divisibility and inequality are the same four parts

For divisibility, the assumption is best written as the expression equals some multiple - say it is three times an integer M - because then M is something you can carry into the next line. Assuming it is divisible by three and never naming the quotient leaves you nothing to substitute.

Then the standard move is to write the k plus one expression in terms of the k one, so the assumed part can be replaced. Usually that means adding and subtracting the same thing, which looks like a trick the first three times and then stops being one.

For inequalities the assumption is used the same way, but you also have to be careful about direction: multiplying both sides by something negative flips it, and a proof that flips an inequality without saying so is a proof of something else.

The check before you move on

Read your own proof back and ask one question: where did I use the assumption? Put your finger on the line. If there is no such line, the proof is incomplete however neat the algebra is.

Then ask whether the base case was the value the question asked for. A statement claimed for n greater than or equal to three starts at three, not at one, and testing the wrong value is a mark lost on the easiest part of the question.

And check the conclusion actually names the range. True for all integers n greater than or equal to one is a conclusion; it follows by induction is half of one.

Where it usually goes wrong

Five of them, and four are about what is written rather than what was calculated.

• Skipping the base case because it was obvious.
• Writing assume true for n equals k without writing the statement.
• An inductive step that never uses the assumption.
• Working on both sides at once instead of from one to the other.
• Finishing on the algebra with no concluding sentence.

What to practise next

Take three induction proofs you have already done and, in each, circle the line where the assumption is used. If you cannot circle one, that proof was not finished, and finding that out on your own work is worth more than doing three new ones.

Then write out the four parts from memory as a skeleton, with no particular statement in it, and use that skeleton for the next five questions. The proof becomes filling in a shape, which is what it is.

Check yourself

Three questions on what is above. Have a go before you open them - reading an answer you have not tried to give is the version of this that does nothing.