Skip to content
← Explore another subjectAS and A level · 9FM0

Proof by induction: sums of series and divisibility

Edexcel Further Mathematics (9FM0) · Core Pure Mathematics: proof; complex numbers; matrices

ONE COMPLETE FREE SECTION

Your course level

This AS section is included at this level. The sample stays complete. Sign up when you’re ready to continue the unit.

0 highlighted

Proof by induction: sums of series and divisibility

Proof by mathematical induction lets you prove a statement about every positive integer nn in a few lines of algebra, even though there are infinitely many cases.

It is the proof method of Core Pure Mathematics, and it comes back in this unit for matrices, in later units for series and derivatives, and in Further Pure 2 for recurrence relations.

Core Pure content is examined on Paper 1 and Paper 2, and either paper may set any of it: an induction proof is a single question of 5 or 6 marks, marked line by line, so the layout you learn here is worth as much as the algebra.

From A level Mathematics

In A level Mathematics you met proof by deduction (start from known facts and reason forwards), proof by exhaustion (check every case), disproof by counter-example and proof by contradiction.

None of them can prove a formula such as ∑r=1nr(3r+1)=n(n+1)2\sum_{r=1}^{n} r(3r + 1) = n(n + 1)^2 for all nn: checking n=1,2,3,…,1000n = 1, 2, 3, \ldots, 1000 is still only checking.

Further Mathematics adds induction, which proves the statement for all positive integers at once.

The idea: a chain that never breaks

Think of an infinite row of dominoes.

Two facts are enough to know that every domino falls:

  • the first domino falls;
  • whenever any one domino falls, it knocks over the next one.

The photograph below shows the start of the chain: the first domino is falling, and every domino stands close enough to the next to knock it over.

Neither fact alone is enough.

Without the push, nothing falls; with gaps in the row, the chain stops at the first gap.

A photograph of a long row of upright dominoes on a table, stretching into the distance. Only the first domino is tipping over and touching the second; the rest are still standing, each close enough to knock over the next.
A photograph of a long row of upright dominoes on a table, stretching into the distance. Only the first domino is tipping over and touching the second; the rest are still standing, each close enough to knock over the next.

Induction is the same argument for statements.

Write the statement as P(n)P(n).

If you show

1. P(1)P(1) is true (the base case), and

2. if P(k)P(k) is true for some positive integer kk, then P(k+1)P(k + 1) is true (the inductive step),

then P(1)P(1) gives P(2)P(2), which gives P(3)P(3), and so on without end, so P(n)P(n) is true for every positive integer nn.

The inductive step is a conditional statement.

You do not know that P(k)P(k) is true; you assume it, and show that the next case would follow.

The base case is what turns the conditional chain into a real conclusion: without it the dominoes are lined up but nobody pushes the first one.

Why it works (not examined). Suppose the base case and the inductive step are both proved, but the statement fails for some positive integer.

Then there is a smallest positive integer mm for which it fails.

mm is not 1, because P(1)P(1) is true, so m−1m - 1 is a positive integer for which the statement is true.

The inductive step then makes P(m)P(m) true, which contradicts the choice of mm.

So no failing integer exists.

The four parts of every induction proof

Every proof you write has the same four parts, and each earns its own mark.

Part

What you write

Typical mark

Base case

substitute n=1n = 1 into both sides and show they are equal

B1

Assumption

"Assume the result is true for n=kn = k", with the formula written out with kk

M1

Inductive step

the working from n=kn = k to n=k+1n = k + 1, in place, ending in the target form

M1 (or dM1), A1, A1

Conclusion

"If the result is true for n=kn = k then it is true for n=k+1n = k + 1. It is true for n=1n = 1, so it is true for all positive integers nn."

A1

You need to know the kinds of statement induction is used for in this course: sums of series, such as showing that ∑r3=14n2(n+1)2\sum r^3 = \frac{1}{4}n^2(n + 1)^2 (summed from r=1r = 1 to nn) or that ∑r(r+1)=n(n+1)(n+2)3\sum r(r + 1) = \frac{n(n + 1)(n + 2)}{3}; divisibility, such as showing that 32n+113^{2n} + 11 is divisible by 4; and matrix products, such as finding a formula for the nthn\text{th} power of a 2×22 \times 2 matrix.

Sums and divisibility are taught here; matrix powers and the nthn\text{th} derivatives that recent papers have asked for are in the next section.

Sums of series

For a sum, the step is always the same move: add the (k+1)(k + 1)​th term to the sum of the first kk terms, which gives the sum of the first k+1k + 1 terms.

∑r=1k+1ur=∑r=1kur+uk+1\sum_{r=1}^{k+1} u_r = \sum_{r=1}^{k} u_r + u_{k+1}

Replace the first part by the assumed formula, then manipulate until you reach the formula with nn replaced by k+1k + 1.

Two habits make this short and safe.

  • Write the target first. Before starting the algebra, write down what the formula gives when n=k+1n = k + 1, and keep it in view. Working towards a stated target is fine, as long as the forward working really reaches it.
  • Take out the common factor before expanding. Both the assumed sum and the new term almost always share a factor (often k+1k + 1). Taking it out leaves a quadratic or cubic to tidy, not a quartic to expand and refactorise.

Divisibility

A statement such as "f(n)f(n) is divisible by 21 for all positive integers nn" means f(n)=21mf(n) = 21m for some integer mm.

The step is to write f(k+1)f(k + 1) in terms of f(k)f(k) plus something that is visibly a multiple of the divisor.

Two routes both work:

  • Rewrite f(k+1)f(k + 1) using index laws (4k+2=4×4k+14^{k+2} = 4 \times 4^{k+1}, 52k+1=25×52k−15^{2k+1} = 25 \times 5^{2k-1}), then split off a multiple of f(k)f(k).
  • Consider f(k+1)−f(k)f(k + 1) - f(k) (or f(k+1)−af(k)f(k + 1) - af(k) for a well-chosen aa) and show the difference is a multiple of the divisor.

Either way, finish by saying why the result is a multiple: "both terms are multiples of 21, so f(k+1)f(k + 1) is divisible by 21".

Key terms
  • Mathematical induction: construct proofs using mathematical induction. Contexts include sums of series, divisibility and powers of matrices.
  • Base case: the statement checked for the first value, n=1n = 1, by substituting into both sides.
  • Inductive step: a proof that if the statement is true for n=kn = k then it is true for n=k+1n = k + 1.
  • Conclusion of an induction proof: true for n=1n = 1; if true for n=kn = k then true for n=k+1n = k + 1; so true for all positive integers nn.
  • Divisible by dd: f(n)=dmf(n) = dm for some integer mm.
  • Sum of the first nn positive integers: ∑r=1nr=12n(n+1)\sum_{r=1}^{n} r = \frac{1}{2}n(n + 1). You need to know this formula by heart and use it without a reminder. It checks an induction answer quickly (and the unit on series, cp4-6, builds on it), but it never replaces the induction a question asks for.
How the marks work
  • Every mark is worth one. M1 is for a correct method applied to this problem; A1 is for an accurate line or answer and needs the M mark before it; B1 is an independent mark (a base case, a value, a reason).
  • dM1 depends on the M mark before it, and ddM1 on the two before it. A1* is the last mark of a "show that" or a proof whose result is printed: earned only with no errors and the printed result written out in full, with its subject.
  • cso means correct solution only; ft means a wrong earlier value carried forward correctly still earns marks; oe means any equivalent form; awrt means "answers which round to"; isw means ignore subsequent working; a special case (SC) gives partial credit for a recognised wrong route.
  • Under the calculator banner ("In this question you must show all stages of your working. Solutions relying entirely on calculator technology are not acceptable.") or a named method ("Prove by induction", "Hence", "By forming and solving a matrix equation"), a correct answer reached another way scores 0 or a special case.
  • Radians are the default in complex numbers: a method worked in degrees mode can earn the M mark but never the A mark.
  • The last mark of an induction proof needs every earlier mark: the base case, the step reaching the target form and the full conclusion.
  • If you make two attempts and cross neither out, the examiner marks the most complete final one: cross out the attempt you do not want.
Worked example 1: a sum with a common factor

Prove by induction that, for all positive integers nn,

∑r=1nr(3r+1)=n(n+1)2(6)\sum_{r=1}^{n} r(3r + 1) = n(n + 1)^2 \qquad (6)

When n=1n = 1: left side =1×(3+1)=4= 1 \times (3 + 1) = 4; right side =1×(1+1)2=4= 1 \times (1 + 1)^2 = 4.

So the result is true for n=1n = 1.

B1 (both sides worked with n=1n = 1 substituted)

Assume the result is true for n=kn = k, so ∑r=1kr(3r+1)=k(k+1)2\sum_{r=1}^{k} r(3r + 1) = k(k + 1)^2.

Then

∑r=1k+1r(3r+1)=k(k+1)2+(k+1)(3k+4)\sum_{r=1}^{k+1} r(3r + 1) = k(k + 1)^2 + (k + 1)(3k + 4)

M1 (assumed sum plus the (k+1)(k + 1)​th term)

Target: (k+1)(k+2)2(k + 1)(k + 2)^2.

=(k+1)[k(k+1)+3k+4]=(k+1)(k2+4k+4)= (k + 1)\left[k(k + 1) + 3k + 4\right] = (k + 1)(k^2 + 4k + 4) dM1 (the two terms combined, here by taking out the common factor k+1k + 1)

=(k+1)(k+2)2= (k + 1)(k + 2)^2 A1

=(k+1)((k+1)+1)2= (k + 1)\left((k + 1) + 1\right)^2, which is the result with n=k+1n = k + 1.

A1

If the result is true for n=kn = k then it is true for n=k+1n = k + 1.

It is true for n=1n = 1, so it is true for all positive integers nn.

A1 (needs all previous marks)

Answer: proved.

A candidate who expands k(k+1)2+(k+1)(3k+4)k(k + 1)^2 + (k + 1)(3k + 4) to k3+5k2+8k+4k^3 + 5k^2 + 8k + 4 and stops, without showing it equals (k+1)(k+2)2(k + 1)(k + 2)^2, scores B1 M1 dM1 A0 A0 A0.

Worked example 2: a sum of fractions

Prove by induction that, for n∈Nn \in \mathbb{N},

∑r=1n1r(r+1)(r+2)=n(n+3)4(n+1)(n+2)(6)\sum_{r=1}^{n} \frac{1}{r(r + 1)(r + 2)} = \frac{n(n + 3)}{4(n + 1)(n + 2)} \qquad (6)

When n=1n = 1: left side =11×2×3=16= \dfrac{1}{1 \times 2 \times 3} = \dfrac{1}{6}; right side =1×44×2×3=424=16= \dfrac{1 \times 4}{4 \times 2 \times 3} = \dfrac{4}{24} = \dfrac{1}{6}.

True for n=1n = 1.

B1

Assume true for n=kn = k.

Then

∑r=1k+11r(r+1)(r+2)=k(k+3)4(k+1)(k+2)+1(k+1)(k+2)(k+3)\sum_{r=1}^{k+1} \frac{1}{r(r + 1)(r + 2)} = \frac{k(k + 3)}{4(k + 1)(k + 2)} + \frac{1}{(k + 1)(k + 2)(k + 3)}

M1

=k(k+3)2+44(k+1)(k+2)(k+3)= \dfrac{k(k + 3)^2 + 4}{4(k + 1)(k + 2)(k + 3)} dM1 (one common denominator)

The numerator is k3+6k2+9k+4k^3 + 6k^2 + 9k + 4.

Putting k=−1k = -1 gives −1+6−9+4=0-1 + 6 - 9 + 4 = 0, so k+1k + 1 is a factor, and k3+6k2+9k+4=(k+1)2(k+4)k^3 + 6k^2 + 9k + 4 = (k + 1)^2(k + 4).

A1

=(k+1)2(k+4)4(k+1)(k+2)(k+3)=(k+1)(k+4)4(k+2)(k+3)=(k+1)((k+1)+3)4((k+1)+1)((k+1)+2)= \dfrac{(k + 1)^2(k + 4)}{4(k + 1)(k + 2)(k + 3)} = \dfrac{(k + 1)(k + 4)}{4(k + 2)(k + 3)} = \dfrac{(k + 1)\left((k + 1) + 3\right)}{4\left((k + 1) + 1\right)\left((k + 1) + 2\right)} A1 (the result with n=k+1n = k + 1)

If true for n=kn = k then true for n=k+1n = k + 1; true for n=1n = 1; so true for all n∈Nn \in \mathbb{N}.

A1

Answer: proved.

On these papers N={1,2,3,…}\mathbb{N} = \{1, 2, 3, \ldots\}, so "n∈Nn \in \mathbb{N}" means the same as "for all positive integers nn".

The factor theorem is the quick way to spot the factorisation the target needs: the target has k+1k + 1 on top, so k+1k + 1 must divide the numerator.

Worked example 3: divisibility by rewriting $f(k + 1)$

f(n)=4n+1+52n−1f(n) = 4^{n+1} + 5^{2n-1}

Prove by induction that, for all positive integers nn, f(n)f(n) is divisible by 21.

(6)

f(1)=42+51=16+5=21f(1) = 4^2 + 5^1 = 16 + 5 = 21, which is divisible by 21, so the result is true for n=1n = 1.

B1

Assume that f(k)f(k) is divisible by 21, so f(k)=21mf(k) = 21m for some integer mm.

M1 (assumption stated)

f(k+1)=4k+2+52k+1=4×4k+1+25×52k−1f(k + 1) = 4^{k+2} + 5^{2k+1} = 4 \times 4^{k+1} + 25 \times 5^{2k-1} M1 (index laws to bring in the parts of f(k)f(k))

=4(4k+1+52k−1)+21×52k−1=4f(k)+21×52k−1= 4\left(4^{k+1} + 5^{2k-1}\right) + 21 \times 5^{2k-1} = 4f(k) + 21 \times 5^{2k-1} A1

=84m+21×52k−1=21(4m+52k−1)= 84m + 21 \times 5^{2k-1} = 21\left(4m + 5^{2k-1}\right), which is divisible by 21.

A1

If f(k)f(k) is divisible by 21 then f(k+1)f(k + 1) is divisible by 21.

f(1)f(1) is divisible by 21, so f(n)f(n) is divisible by 21 for all positive integers nn.

A1

Alternative method: f(k+1)−f(k)=3×4k+1+24×52k−1=3f(k)+21×52k−1f(k + 1) - f(k) = 3 \times 4^{k+1} + 24 \times 5^{2k-1} = 3f(k) + 21 \times 5^{2k-1}, so f(k+1)=4f(k)+21×52k−1f(k + 1) = 4f(k) + 21 \times 5^{2k-1}, the same line.

Both routes earn full marks; the rewriting route is usually shorter.

Worked example 4: divisibility with a polynomial

Prove by induction that 5n3+7n5n^3 + 7n is divisible by 6 for all positive integers nn.

(6)

Let f(n)=5n3+7nf(n) = 5n^3 + 7n.

Then f(1)=5+7=12=6×2f(1) = 5 + 7 = 12 = 6 \times 2, so true for n=1n = 1.

B1

Assume f(k)=6mf(k) = 6m for some integer mm.

M1

f(k+1)−f(k)=5[(k+1)3−k3]+7=5(3k2+3k+1)+7f(k + 1) - f(k) = 5\left[(k + 1)^3 - k^3\right] + 7 = 5(3k^2 + 3k + 1) + 7 M1

=15k2+15k+12=15k(k+1)+12= 15k^2 + 15k + 12 = 15k(k + 1) + 12 A1

k(k+1)k(k + 1) is the product of two consecutive integers, so it is even, and 15k(k+1)15k(k + 1) is a multiple of 30, so a multiple of 6.

Then f(k+1)=6m+15k(k+1)+12f(k + 1) = 6m + 15k(k + 1) + 12 is a sum of multiples of 6.

A1 (the reason the difference is a multiple of 6 must be given)

If true for n=kn = k then true for n=k+1n = k + 1; true for n=1n = 1; so 5n3+7n5n^3 + 7n is divisible by 6 for all positive integers nn.

A1

Answer: proved.

Writing "15k2+15k+1215k^2 + 15k + 12 is a multiple of 6" with no reason loses the fifth mark: 15k2+15k15k^2 + 15k is not obviously a multiple of 6 until you factorise and use the evenness of k(k+1)k(k + 1).

Exam tip

The induction conclusion is a mark of its own and the one lost most often.

It needs all three ideas: "true for n=1n = 1", "if true for n=kn = k then true for n=k+1n = k + 1" and "true for all positive integers nn".

Writing "true for n=kn = k and n=k+1n = k + 1" or "true for all real numbers" loses it.

A narrative sentence that contains all three ideas is credited.

Common mistakes
  • A base case with no substitution shown. Writing "true for n=1n = 1" or "4=44 = 4" alone loses B1. Show n=1n = 1 put into both sides, because the mark is for checking the formula, not for asserting it.
  • Using summation formulae in place of induction. Evaluating ∑r(3r+1)\sum r(3r + 1) with ∑r2\sum r^2 and ∑r\sum r proves the formula, but a question that says "Prove by induction" gives no marks for it. The command names the method.
  • Expanding everything. Expanding the assumed sum and the new term to a quartic and then trying to factorise is long and error-prone. Take out the common factor first, as in Worked example 1; examiners report that spotting it is what separates quick, correct steps from stalled ones.
  • Side working. The step must be worked in place, line by line, with at least one line between the assumed form and the target. A jump to the n=k+1n = k + 1 form with the working in the margin is treated as unsupported.
  • Assuming what you want to prove. "Assume true for all nn" is circular. You assume only the case n=kn = k, then prove the next one.

Check your understanding

1. Prove by induction that, for all positive integers nn,

∑r=1nr×3r−1=(2n−1)3n+14(6)\sum_{r=1}^{n} r \times 3^{r-1} = \frac{(2n - 1)3^n + 1}{4} \qquad (6)

Total [6]

2. f(n)=32n+2−8n−9f(n) = 3^{2n+2} - 8n - 9 Prove by induction that, for n∈Nn \in \mathbb{N}, f(n)f(n) is divisible by 64. (6) Total [6]

3. A student ends an induction proof with the sentence "So the result is true for n=kn = k and for n=k+1n = k + 1, so it is true."
(a) State what is missing from this conclusion. (1)
(b) Write down a conclusion that would earn the final mark. (1) Total [2]

4. (a) Prove by induction that, for all positive integers nn,

∑r=1nr(r+1)(r+3)=112n(n+1)(n+2)(3n+13)(6)\sum_{r=1}^{n} r(r + 1)(r + 3) = \frac{1}{12}n(n + 1)(n + 2)(3n + 13) \qquad (6)

\

(b) Hence determine the value of ∑r=1120r(r+1)(r+3)\sum_{r=11}^{20} r(r + 1)(r + 3). (2) Total [8]

5. Prove by induction that 2n+2+32n+12^{n+2} + 3^{2n+1} is divisible by 7 for all positive integers nn. (5) Total [5]

6. A student is asked to prove by induction that ∑r=1n(6r2−2r)=2n2(n+1)\sum_{r=1}^{n} (6r^2 - 2r) = 2n^2(n + 1). The student writes ∑(6r2−2r)=6×16n(n+1)(2n+1)−2×12n(n+1)\sum (6r^2 - 2r) = 6 \times \frac{1}{6}n(n + 1)(2n + 1) - 2 \times \frac{1}{2}n(n + 1) and simplifies it correctly to 2n2(n+1)2n^2(n + 1). Explain why this answer scores no marks. (1) Total [1]

Answers

1. n=1n = 1: left side 1×30=11 \times 3^0 = 1; right side (2−1)×3+14=1\frac{(2 - 1) \times 3 + 1}{4} = 1, so true for n=1n = 1 B1 Assume true for n=kn = k; ∑r=1k+1r×3r−1=(2k−1)3k+14+(k+1)3k\sum_{r=1}^{k+1} r \times 3^{r-1} = \frac{(2k - 1)3^k + 1}{4} + (k + 1)3^k M1 =(2k−1)3k+4(k+1)3k+14=(6k+3)3k+14= \frac{(2k - 1)3^k + 4(k + 1)3^k + 1}{4} = \frac{(6k + 3)3^k + 1}{4} dM1 A1 =(2k+1)3k+1+14=(2(k+1)−1)3k+1+14= \frac{(2k + 1)3^{k+1} + 1}{4} = \frac{(2(k + 1) - 1)3^{k+1} + 1}{4} A1 (uses (6k+3)3k=3(2k+1)3k(6k + 3)3^k = 3(2k + 1)3^k) If true for n=kn = k then true for n=k+1n = k + 1; true for n=1n = 1; so true for all positive integers nn A1

2. f(1)=34−8−9=64f(1) = 3^4 - 8 - 9 = 64, divisible by 64 B1 Assume f(k)=64mf(k) = 64m; f(k+1)=32k+4−8(k+1)−9=9×32k+2−8k−17f(k + 1) = 3^{2k+4} - 8(k + 1) - 9 = 9 \times 3^{2k+2} - 8k - 17 M1 f(k+1)−9f(k)=−8k−17+72k+81=64k+64f(k + 1) - 9f(k) = -8k - 17 + 72k + 81 = 64k + 64 M1 A1 So f(k+1)=9f(k)+64(k+1)=64(9m+k+1)f(k + 1) = 9f(k) + 64(k + 1) = 64\left(9m + k + 1\right), divisible by 64 A1 If true for n=kn = k then true for n=k+1n = k + 1; true for n=1n = 1; so true for all n∈Nn \in \mathbb{N} A1

3. (a) It never says the result is true for n=1n = 1, and it does not say that truth for n=kn = k implies truth for n=k+1n = k + 1; it also does not say "for all positive integers nn" B1
(b) "If the result is true for n=kn = k then it is true for n=k+1n = k + 1. It is true for n=1n = 1, so it is true for all positive integers nn." B1

4. (a) n=1n = 1: left side 1×2×4=81 \times 2 \times 4 = 8; right side 112×1×2×3×16=8\frac{1}{12} \times 1 \times 2 \times 3 \times 16 = 8 B1 Assume true for n=kn = k; sum to k+1k + 1 =112k(k+1)(k+2)(3k+13)+(k+1)(k+2)(k+4)= \frac{1}{12}k(k + 1)(k + 2)(3k + 13) + (k + 1)(k + 2)(k + 4) M1 =112(k+1)(k+2)[k(3k+13)+12(k+4)]= \frac{1}{12}(k + 1)(k + 2)\left[k(3k + 13) + 12(k + 4)\right] dM1 =112(k+1)(k+2)(3k2+25k+48)= \frac{1}{12}(k + 1)(k + 2)(3k^2 + 25k + 48) A1 =112(k+1)(k+2)(k+3)(3k+16)=112(k+1)((k+1)+1)((k+1)+2)(3(k+1)+13)= \frac{1}{12}(k + 1)(k + 2)(k + 3)(3k + 16) = \frac{1}{12}(k + 1)\left((k + 1) + 1\right)\left((k + 1) + 2\right)\left(3(k + 1) + 13\right) A1 Conclusion with all three ideas A1
(b) ∑r=1120=f(20)−f(10)\sum_{r=11}^{20} = f(20) - f(10), where f(n)f(n) is the formula M1 =56 210−4730=51 480= 56\,210 - 4730 = 51\,480 A1

5. f(1)=23+33=35=7×5f(1) = 2^3 + 3^3 = 35 = 7 \times 5 B1 Assume f(k)=7mf(k) = 7m; f(k+1)=2k+3+32k+3=2×2k+2+9×32k+1f(k + 1) = 2^{k+3} + 3^{2k+3} = 2 \times 2^{k+2} + 9 \times 3^{2k+1} M1 =2f(k)+7×32k+1= 2f(k) + 7 \times 3^{2k+1} A1 =14m+7×32k+1=7(2m+32k+1)= 14m + 7 \times 3^{2k+1} = 7\left(2m + 3^{2k+1}\right), divisible by 7 A1 Conclusion with all three ideas A1

6. The question names the method: a direct use of the summation formulae is not a proof by induction, so it earns no marks however correct it is B1

Ready for the next section?

Create a free account to read the rest of this free unit, save highlights, track your confidence and plan your revision.

Your next step

Put this topic into practice.

These tools belong to this free unit. Create an account to open them and save your progress.

Practice paper · Sign up to open

Further Mathematics 9FM0 Topic cp1-3: Core Pure Mathematics: proof; complex numbers; matrices. Structured practice

5 questions · AS · Paper 1

Attempt the questions, check the mark scheme and record your own marks.

Create free account to open this practice

Other units and paper downloads depend on your plan. This unit has no Section A quiz; use its other practice and checklist.

Already have an account? Sign in →

Give your revision a routine.

Build a timetable, tick off daily tasks, catch up on missed work and opt in to weekly email reviews. Connect with your teacher when you want to share your progress.