Proof by Mathematical Induction
Why an initial statement and an inductive step together prove a result for every positive integer, and how to write sum and divisibility proofs that collect every mark.
60 min · Proof
The full teaching. Start here.
The short version
Induction proves a statement for every positive integer in two steps.
- Initial statement. Show is true by evaluating both sides.
- Inductive step. Assume is true for some positive integer . Use that assumption to prove .
Then conclude: since is true and implies , is true for all positive integers .
For a sum, write the sum as the sum plus one new term, replace the sum using the assumption, then factorise towards the target.
For divisibility, write the assumption as an equation, such as for an integer . Rearrange it for the power, substitute into the expression, and factor out the divisor.
A valid step with a false initial statement proves nothing. So does a true initial statement with no valid step. And induction only reaches integers, stepping up from where it starts.
Why two steps are enough
A chain of implications needs a first link
AnswersChecking a formula for a million values of n does not prove it. Why do two short steps prove it for all of them?
The inductive step does not prove that anything is true. It proves an implication: if is true, then is true, for every positive integer .
An implication on its own is a promise with nothing to act on. Applied to it says ; applied to it says ; and so on forever. It is a chain of links, and none of them delivers a true statement until a true statement is fed in at the start.
The initial statement feeds one in: is true. Now the first link gives , the next gives , and every positive integer is reached after links. No case is left out, because every positive integer is a finite number of steps from .
Think of dominoes in a line. The inductive step shows they are spaced so that each one, if it falls, knocks the next over. The initial statement pushes the first one. You need both: well spaced dominoes that nobody pushes stay standing, and a pushed first domino with badly spaced ones behind it stops after one.
CheckpointAnswer before reading on.
In a proof by mathematical induction, what does the inductive step on its own establish?
Hint 1It is an if-then statement.
Hint 2It does not say anything is true yet.
Hint 3It links each case to the next one.
CheckpointAnswer before reading on.
Why is the initial statement needed in a proof by induction?
Hint 1Think of a row of dominoes.
Hint 2The step says each one knocks over the next.
Hint 3Something has to fall first.
CheckpointAnswer before reading on.
A statement is proved true for , and it is proved that true implies true. Starting from , how many applications of the inductive step are needed to reach ?
Hint 1Each application moves up by one.
Hint 2From to is one application.
Hint 3Count from to .
- Mathematical induction
A method of proving a statement for all integers : prove (the initial statement), then prove that for every integer (the inductive step).
The starting value does not have to be . A claim "for all " needs the initial statement at , and the chain then covers and nothing below.
CheckpointAnswer before reading on.
A statement is claimed for all integers . Which initial statement should the proof by induction check?
Hint 1The chain starts where the claim starts.
Hint 2Checking may fail and does not matter.
Hint 3Match the domain in the question.
What "assume" means
The phrase "assume is true" trips students up because it sounds like a claim. It is not. It is the if part of the implication. You are writing: "suppose, for the sake of argument, that some case works; I will show the next one must work too."
That is why the case you assume is and the case you prove is . Assuming and simplifying until both sides agree assumes the answer, and proves nothing.
CheckpointAnswer before reading on.
In the inductive step, a student writes: \"Assume true for \" and then simplifies until both sides agree. What is wrong?
Hint 1What is the hypothesis and what is the target?
Hint 2Assuming the conclusion is circular.
Hint 3Which case is allowed to be assumed?
The layout, which earns the marks
Induction questions in the Extension 1 paper are usually worth two or three marks, and those marks go to separate pieces of the answer: the initial statement, a correct use of the assumption, and a finished step with a conclusion. A layout that makes each piece visible collects each mark.
Write the target before you start the algebra
Straight after the assumption, write "Required to prove: …" with the statement in full. It costs one line and it does two jobs. It tells you what to factorise towards, and it shows the marker you know what the step is for. Most stalled inductive steps are students who never wrote down where they were going.
- Initial statement. Evaluate the left side and the right side separately for the first value, and say they are equal.
- Assumption. "Assume true for , where is a positive integer," with the statement written out.
- Target. "Required to prove true for ," with that statement written out.
- Proof. Start from the left side of the target. Use the assumption, and say where you use it.
- Conclusion. Name both steps and the domain.
CheckpointAnswer before reading on.
Write a concluding statement for a proof by induction of a statement for all positive integers , and explain what each part of it refers to. (2 marks)
Hint 1Two facts combine.
Hint 2Name the base case.
Hint 3Name the implication.
Proving sums
The key idea in every sum proof is that the sum to terms contains the sum to terms:
So write the case as the old sum plus one new term, and replace the old sum with the formula you assumed. The new term comes from substituting into the general term, not from adding one to anything.
CheckpointAnswer before reading on.
In proving by induction, what is the statement for that must be proved?
Hint 1Replace every by .
Hint 2On both sides.
Hint 3The left side gains one new term.
CheckpointAnswer before reading on.
The sum is being proved by induction. Write the th term.
Hint 1Substitute into .
Hint 2.
Hint 3Simplify the index.
Worked example3 marks
The sum of the first n squares
Prove by mathematical induction that for all positive integers ,
Initial statement, both sides separately
Writing only '1 = 1' does not show which side is which. Evaluating each side on its own is what the mark is for.
When : LHS . RHS . LHS RHS, so the statement is true for .
Assumption and target
Writing the target now tells you the shape to factorise towards: (k+1)(k+2)(2k+3) over 6.
Assume true for , where is a positive integer:
Required to prove true for :
Replace the old sum using the assumption
This is the one step that uses the inductive hypothesis. Without it the proof is not an induction.
Factorise, do not expand
Both terms contain (k+1), and so does the target. Taking it out keeps the expression short. Expanding everything into a cubic and factorising back is where time is lost.
Answer
The statement is true for , and if it is true for it is true for . Hence, by mathematical induction, it is true for all positive integers .
Is that answer sensible?
Test in the original: and . The quadratic factorised to , which is exactly with replaced by , so the target was hit rather than approximated.
Common mistake
Writing the new term as k² + 1, or adding 1 to the right-hand formula.
Why it happens: The phrase 'the next case' suggests adding one to something.
The next case means substituting for everywhere. In the sum, the new term is the general term at , which is . On the right, every in becomes .
CheckpointAnswer before reading on.
Prove by mathematical induction that for all positive integers . (3 marks)
Hint 1: both sides are .
Hint 2The th odd number is .
Hint 3 is a perfect square.
CheckpointAnswer before reading on.
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1The next term is .
Hint 2Expand and collect.
Hint 3Factorise .
CheckpointAnswer before reading on.
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1The th term is .
Hint 2.
Hint 3.
Sums of fractions work the same way. The only difference is a common denominator before factorising.
CheckpointAnswer before reading on.
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1At both sides are .
Hint 2The new term is .
Hint 3Put everything over and factorise the numerator.
Exam question
Standard · about 5 min
3 marks
Use mathematical induction to prove that for all positive integers ,
(3 marks)
Hint 1Check on both sides separately.
Hint 2Write the sum to terms as the sum to terms plus the th term.
Hint 3Take out the common factor .
Where students lose marks on this one
Expanding everything into a cubic and trying to factorise back.
Why it happens: Expanding feels safer than factorising.
Take out straight away. It is a factor of both terms and of the target.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1Both sides are at .
Hint 2Take out .
Hint 3.
Where students lose marks on this one
Skipping from the assumption to the target without showing the algebra.
Why it happens: The result is given, so the student writes it down.
Show every line from LHS to RHS. The algebra is the mark.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1The next term is .
Hint 2Common denominator .
Hint 3.
Where students lose marks on this one
Skipping from the assumption to the target without showing the algebra.
Why it happens: The result is given, so the student writes it down.
Show every line from LHS to RHS. The algebra is the mark.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1Both sides equal at .
Hint 2Factor out .
Hint 3.
Where students lose marks on this one
Skipping from the assumption to the target without showing the algebra.
Why it happens: The result is given, so the student writes it down.
Show every line from LHS to RHS. The algebra is the mark.
Written for this site.
Proving divisibility
"Divisible by " cannot be substituted into algebra. An equation can. So the first move in a divisibility proof is to turn the words into one:
The integer matters. Every number is times something; it is being times an integer that makes it a multiple of .
CheckpointAnswer before reading on.
Which is the most useful way to write the assumption that is divisible by ?
Hint 1Divisible means a multiple.
Hint 2Name the multiple.
Hint 3It must be an integer.
CheckpointAnswer before reading on.
In the inductive step of a proof that is divisible by , the expression is rewritten as . What is the value of ?
Hint 1Expand the index.
Hint 2.
Hint 3.
Worked example3 marks
The syllabus example: 3 to the 2n, minus 1
Prove by mathematical induction that is divisible by for all positive integers .
Initial statement
A number shown to be a multiple of 8 is divisible by 8. Say so explicitly.
When : , which is divisible by . True for .
Assumption as an equation, rearranged for the power
Rearranging for the power term produces the thing that will be substituted. The k+1 expression contains 3 to the 2k, not 3 to the 2k minus 1.
Assume for some integer , so .
Required to prove: is divisible by .
Split off the old power
The index rule a to the (m+n) equals a to the m times a to the n is what makes the assumed power appear.
Substitute and factor out the divisor
The marker needs to see the 8 taken out and the remaining bracket identified as an integer. 'Clearly divisible' does not earn that mark.
Since is an integer, is an integer, so this is divisible by .
Answer
True for , and true for implies true for . By mathematical induction, is divisible by for all positive integers .
Is that answer sensible?
: . And the formula from the proof predicts that if (so ), then . The proof's arithmetic matches the real value.
CheckpointAnswer before reading on.
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1.
Hint 2.
Hint 3.
CheckpointAnswer before reading on.
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1.
Hint 2.
Hint 3Multiply out and factor 9.
When the expression has two powers
Substitution works when one power can be isolated. When two different bases appear, the other technique is to split the expression so that the whole assumed expression appears inside it.
Worked example3 marks
Two bases: 5 to the n plus 2 times 11 to the n
Prove by mathematical induction that is divisible by for all positive integers .
Initial statement
As before, show the multiple.
: . Divisible by .
Assumption
Leave it as an equation. Neither power can be isolated neatly, so it will be used whole.
Assume for some integer .
Split so that the assumed expression appears
Taking out a factor of 5 leaves 5 times the assumed expression plus a remainder. The remainder is what has to be divisible by 3.
Answer
is an integer, so the expression is divisible by . True for , and true for implies true for , so true for all positive integers by induction.
Is that answer sensible?
The split worked because , and is a multiple of . If the remainder had not been a multiple of , that would signal an arithmetic slip, because the result is true (: ).
CheckpointAnswer before reading on.
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1 gives .
Hint 2Expand and look for .
Hint 3.
Exam question
Straightforward · about 5 min
3 marks
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1: .
Hint 2Assume .
Hint 3.
Where students lose marks on this one
Writing $3^{2(k+1)}=3^{2k}+3^{2}$.
Why it happens: Confusing multiplying powers with adding them.
.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by mathematical induction that is divisible by for all integers . (3 marks)
Hint 1.
Hint 2From the assumption, .
Hint 3Substitute into .
Where students lose marks on this one
Writing $7^{k+1}-3^{k+1}=4^{k+1}$.
Why it happens: Treating subtraction of powers like subtraction of bases.
Powers do not distribute over subtraction. Rewrite each power separately.
Written for this site.
Exam question
Harder · about 5 min
3 marks
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1At the expression is .
Hint 2Write the assumption as .
Hint 3Split as so the assumption appears.
Where students lose marks on this one
Writing "which is divisible by 3" after $15M+12\times 11^{k}$ without factorising.
Why it happens: The divisibility looks obvious.
Take out the explicitly and say the bracket is an integer. That line is the mark.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1 gives .
Hint 2Expand .
Hint 3Group so the assumption appears.
Where students lose marks on this one
Stopping at an expression like $9\times 8M+8$ and writing "divisible".
Why it happens: The divisibility looks obvious.
Factor out explicitly and state that the remaining bracket is an integer.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1.
Hint 2.
Hint 3.
Where students lose marks on this one
Stopping at an expression like $9\times 8M+8$ and writing "divisible".
Why it happens: The divisibility looks obvious.
Factor out explicitly and state that the remaining bracket is an integer.
Written for this site.
Provetypically 2 to 4 marks
- Demands
- Establish that a statement is true in every case it claims, by reasoning in which each line follows from the one before or from a stated result.
- Shape
- State what is being proved and any method (such as induction). Each line of working says or shows why it follows. Finish by stating the result as proved.
- Loses marks
- Checking a few cases, or working from both ends towards the middle, and treating the numbers agreeing as a proof.
Through a marker’s eyes
3 marks
Prove by mathematical induction that 7ⁿ − 3ⁿ is divisible by 4 for all integers n ≥ 1. (3 marks)
The attempt
1 out of 3
: ✓
Assume divisible by 4.
, which is divisible by 4.
So true by induction.
What the marker sees
The initial statement earns its mark. The split in the step is actually correct: , and . But the response never turns the assumption into an equation, so it never shows that is a multiple of . It is asserted, and so is the final divisibility.
The conclusion does not name the two steps. Three lines, each missing its justification, is the usual shape of a one-mark induction.
The same answer, fixed
3 out of 3
Initial statement. : , divisible by . True.
Inductive step. Assume for some integer , where .
Required to prove: is divisible by .
which is divisible by , since is an integer.
True for , and true for implies true for . Hence by mathematical induction, true for all integers .
Exam question
Harder · about 5 min
3 marks
Prove by mathematical induction that is divisible by for all positive integers . (3 marks)
Hint 1At the value is .
Hint 2Write in terms of and .
Hint 3Collect: .
Where students lose marks on this one
Stopping at an expression like $9\times 8M+8$ and writing "divisible".
Why it happens: The divisibility looks obvious.
Factor out explicitly and state that the remaining bracket is an integer.
Written for this site.
False proofs: when only one step holds
The syllabus asks you to find the error in a "proof" where one of the two steps fails, and to understand that the statement has then not been proved. Not proved is not the same as false, although in the examples you meet it usually is false as well.
A valid step with no true initial statement. Suppose someone shows: if is odd, then is odd. That is correct: odd plus even is odd. But is even, and so is every other case, because is a product of consecutive integers. The dominoes are well spaced, but none of them ever falls.
CheckpointAnswer before reading on.
A student proves: if is odd, then is odd. They conclude that is odd for every positive integer . Which statement is correct?
Hint 1Check the step algebra.
Hint 2Now test .
Hint 3.
A true initial statement with no valid step. The expression is prime for . That is thirty nine initial statements and still no proof, because nothing connects one case to the next. At it equals .
CheckpointAnswer before reading on.
The expression is prime for . What does this show about the claim that it is prime for every positive integer ?
Hint 1Many cases are not a proof.
Hint 2Try .
Hint 3.
CheckpointAnswer before reading on.
A proof by induction has a correct initial statement but an inductive step that does not work. What has been proved?
Hint 1What does the base case alone give?
Hint 2Does anything carry it further?
Hint 3One case only.
Worked example2 marks
Finding the flaw in a plausible proof
A student "proves" that for all positive integers as follows.
Assume . Then .
Identify the error and explain why the statement has not been proved.
Check the inductive step
The error could be in either step. Check the algebra before deciding which.
, so the step is correct: if the formula held for , it would hold for .
Check the initial statement
The student never wrote one, which is itself the error. Test it.
: LHS , RHS . False.
Answer
The initial statement is missing, and it is false. The inductive step only shows that truth would carry from one case to the next, but there is no true case to carry. The statement has not been proved, and in fact it is false for every , since the right side is always more than the true sum .
Is that answer sensible?
The two formulas differ by a constant, , and adding a constant to a correct formula does not break the step, because the constant is carried along unchanged. That is why a missing base case lets such formulas through.
CheckpointAnswer before reading on.
A student claims that . They show correctly that if it holds for then it holds for . Explain why the claim has not been proved, and show it is false. (2 marks)
Hint 1Test .
Hint 2What does the step need to get started?
Hint 3Compare with the known formula.
Exam question
Harder · about 3 min
2 marks
A student attempts to prove for all positive integers .
Initial statement: : . True.
Inductive step: Assume . Then . So true for .
Identify the error, and show that the statement is false. (2 marks)
Hint 1When is ?
Hint 2Try and .
Hint 3Test , and in the original.
Where students lose marks on this one
Blaming the base case.
Why it happens: The base case is the usual culprit.
Here the base case is fine. Check every inequality in the step for the values of it must cover.
Written for this site.
When induction is not the tool
Induction reaches a starting integer and then each next integer, upwards. That rules out three kinds of statement.
Statements about real numbers. " for all " has no next case. A chain from reaches and misses , and almost everything else.
Cases below the start. Proving and says nothing about or negative .
Statements you have not yet found. Induction confirms a formula you already have. It does not produce one. If a question asks you to find a sum, you find it some other way first.
It is also worth recognising when induction is available but a direct argument is better. is a product of three consecutive integers, so it is divisible by at once. Unless a question says "by induction", any valid proof earns the marks.
CheckpointAnswer before reading on.
For which statement is proof by mathematical induction NOT appropriate?
Hint 1Induction steps from one integer to the next.
Hint 2Which statement has no "next case"?
Hint 3Look at what the variable ranges over.
CheckpointAnswer before reading on.
A student proves , and that implies . They claim is now proved for all integers , including and negative integers. Why is this wrong?
Hint 1Which direction does the step move?
Hint 2From , where does the chain go?
Hint 3Does it ever reach ?
Exam question
Standard · about 3 min
2 marks
Explain why mathematical induction cannot be used to prove that for all real . (2 marks)
Hint 1What does the inductive step move between?
Hint 2Which values would the chain reach from ?
Hint 3What about ?
Where students lose marks on this one
Saying induction "only works for sums".
Why it happens: Most examples seen are sums.
The limit is the domain: the variable must be an integer (or run through a sequence).
Written for this site.
Exam question
Standard · about 3 min
2 marks
Prove directly, without induction, that is divisible by for every positive integer , and explain why a direct proof is preferable here. (2 marks)
Hint 1Factorise .
Hint 2Three consecutive integers.
Hint 3One is even, one is a multiple of 3.
Where students lose marks on this one
Saying induction must be used for any divisibility result.
Why it happens: The topic groups the two together.
Any valid proof earns the marks unless the question says "by induction".
Written for this site.
More sums to practise on
These use the same structure with harder algebra. In each one, factorise out whatever the target's factors suggest before expanding anything.
Exam question
Harder · about 5 min
3 marks
Prove by mathematical induction that for all positive integers ,
(3 marks)
Hint 1At the right side is .
Hint 2Collect the terms in .
Hint 3.
Where students lose marks on this one
Skipping from the assumption to the target without showing the algebra.
Why it happens: The result is given, so the student writes it down.
Show every line from LHS to RHS. The algebra is the mark.
Written for this site.
The all horses are the same colour argument
A famous false proof shows how a step can fail at one link only.
Claim: in any group of horses, all are the same colour. Initial statement: a group of one horse is one colour. Step: take horses. Remove one; the remaining are the same colour by assumption. Put it back and remove a different one; those are the same colour too. The two groups overlap, so all match.
The step is valid for , because two groups of from horses overlap when . It fails at : from two horses, removing one leaves one, and removing the other leaves the other one, with no overlap. The link from to is broken, so the chain never gets started. The general lesson is that the inductive step must hold for every from the starting value on, and the small values are where it most often breaks.
Why the step from 2 to the n beats n squared starts at 5
The statement is false for and true from . An induction starting at works: if then , and exactly when . So the step holds for , and the base case at is safely inside that range. Proving inequalities like this by induction is Extension 2 content, but the idea behind it is the one tested here: every link of the chain has to hold from where the chain starts.