CP 1.1 - Induction for sums of series | Edexcel A-Level Further Mathematics

A sum can follow a pattern for thousands of terms without that pattern being proved. You will use mathematical induction to turn a promising formula into a proof for every positive integer, then make the algebra of the next term do the work.

Why one starting case can reach every integer

Why does adding cubes seem to give the square of a sum?

1^3+2^3=9=(1+2)^2 \qquad 1^3+2^3+3^3=36=(1+2+3)^2

The surprise continues: the first $100$ cubes add to $25\,502\,500=5050^2$ . We will prove the pattern for every positive integer, without adding every possible collection of cubes. Checking another case is encouraging; the proof needs a reason that covers the next case however far along the sequence you are.

You already know

From A-level Mathematics, a proof must cover the whole stated domain, and one counterexample disproves a universal claim. Sigma notation abbreviates a sum: $\sum_{r=1}^{n}u_r=u_1+u_2+\cdots+u_n$ ; the letter $r$ is the changing index and $n$ is the final index.

Write $P(n)$ for the whole proposed identity at the integer $n$ . Mathematical induction proves a starting case and then proves a reusable implication. The starting case sets the chain moving; the implication carries it as far as any chosen positive integer.

[DIAGRAM: asset_name: The two jobs in an induction proof; asset_slug: 9fm0-cp23-induction-chain; caption: The base case starts the chain and the same implication reaches each successive integer; description: Four pale blue boxes labelled P(1), P(2), P(3), P(4) run from left to right, followed by an ellipsis. Sage arrows join consecutive boxes. The first box is marked check P(1), and the arrows have a shared label prove P(k) implies P(k+1) for any integer k at least 1. The bottom line says each particular positive integer is reached after finitely many steps.]
The base case starts the chain and the same implication reaches each successive integer

Proof by mathematical induction

To prove $P(n)$ for every integer $n\ge n_0$ , verify the base case $P(n_0)$ . Then, for an arbitrary integer $k\ge n_0$ , make the inductive assumption that $P(k)$ is true and prove that $P(k+1)$ follows. For example, a base case at $3$ reaches $3,4,5,\ldots$ ; it does not establish $1$ or $2$ .

You are assuming one unspecified case temporarily, to prove an implication. You are not assuming that the formula already holds for every integer. Once the implication is proved, the checked starting case supplies its first input.

The induction principle

For an integer $n_0$ , if $P(n_0)$ is true and

P(k)\Longrightarrow P(k+1)

for every integer $k\ge n_0$ , then $P(n)$ is true for every integer $n\ge n_0$ .

Not in the formula booklet: learn it.

For sums starting at $1$ , the base case is usually $n=1$ . Evaluate both sides there. In the next step, keep all the old terms and add the new one: a sum to $k+1$ has one more term than the sum to $k$ .

Key idea

The proof needs both a starting case and the implication from an arbitrary case to its successor. A list of successful substitutions supplies neither a general implication nor a proof of all cases.

The difference between an implication and a second assumption is easy to miss. Locate it in this attempted proof.

Adding the next term to a product sum

For a sum formula, the connection between consecutive cases is already built into the notation: add exactly the term with index $k+1$ , then use the assumed formula for the rest.

For example, a sum whose general term is $r(r+1)$ starts $2+6+12+\cdots$ . Its next term after $k$ terms is $(k+1)(k+2)$ , because every occurrence of $r$ becomes $k+1$ . It is not $k(k+1)$ , which is already included.

The next-term identity

For a sequence $u_r$ and a positive integer $k$ :

\sum_{r=1}^{k+1}u_r=\sum_{r=1}^{k}u_r+u_{k+1}

If the proposed formula is $\sum_{r=1}^{n}u_r=F(n)$ , the inductive step must establish $F(k)+u_{k+1}=F(k+1)$ .

Not in the formula booklet: learn it.

Write the intended $k+1$ form in rough work before simplifying. It tells you which factors to look for, while the actual proof still runs forwards from the sum and its assumption.

Worked example 1: exposing a common factor

Question. Prove by induction that, for every positive integer $n$ ,

\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}{3}

Plan. Check $n=1$ , assume the formula for $k$ terms and add $(k+1)(k+2)$ ; the new term shares two factors with the assumed sum.

At $n=1$ ,

\text{LHS}=1(2)=2 \qquad \text{RHS}=\frac{1(2)(3)}{3}=2

so the result is true for $n=1$ .

Assume that $\sum_{r=1}^{k}r(r+1)=\dfrac{k(k+1)(k+2)}{3}$ for an arbitrary positive integer $k$ . Then

\begin{aligned} \sum_{r=1}^{k+1}r(r+1) &=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2) &&\text{add the next term}\\ &=\frac{(k+1)(k+2)}{3}(k+3) &&\text{factorise}\\ &=\frac{(k+1)((k+1)+1)((k+1)+2)}{3} &&\text{the required next form} \end{aligned}

Why this step? Keeping $(k+1)(k+2)$ intact avoids expanding a cubic that would only need factorising again.

Answer. If the formula is true for $n=k$ , it is true for $n=k+1$ . It is true for $n=1$ , so it is true for all positive integers $n$ , by induction.

Check. At $n=3$ , the sum is $2+6+12=20$ , and the formula gives $3(4)(5)/3=20$ .

Worked example 2 changes just the second factor in the summand, from $r+1$ to $r+2$ . One common factor remains, and the bracket you must factorise becomes a quadratic.

Worked example 2: a quadratic inside the factorisation

Question. Prove by induction that, for every positive integer $n$ ,

\sum_{r=1}^{n}r(r+2)=\frac{n(n+1)(2n+7)}{6}

Plan. Check the first case, add $(k+1)(k+3)$ to the assumed sum and take out $(k+1)/6$ .

At $n=1$ ,

\text{LHS}=1(3)=3 \qquad \text{RHS}=\frac{1(2)(9)}{6}=3

so the result is true for $n=1$ .

Assume that $\sum_{r=1}^{k}r(r+2)=\dfrac{k(k+1)(2k+7)}{6}$ for an arbitrary positive integer $k$ . Then

\begin{aligned} \sum_{r=1}^{k+1}r(r+2) &=\frac{k(k+1)(2k+7)}{6}+(k+1)(k+3) &&\text{use the assumption}\\ &=\frac{k+1}{6}\bigl[k(2k+7)+6(k+3)\bigr] &&\text{take out the common factor}\\ &=\frac{k+1}{6}(2k^2+13k+18) &&\text{collect terms}\\ &=\frac{(k+1)(k+2)(2k+9)}{6} &&\text{factorise the quadratic}\\ &=\frac{(k+1)((k+1)+1)(2(k+1)+7)}{6} &&\text{the required next form} \end{aligned}

Why this step? The target must contain $k+2$ . Factoring the quadratic as $(k+2)(2k+9)$ makes that factor appear through valid algebra.

Answer. Truth for $n=k$ implies truth for $n=k+1$ . Since the result is true for $n=1$ , it holds for all positive integers $n$ , by induction.

Check. At $n=2$ , $1(3)+2(4)=11$ , and $2(3)(11)/6=11$ .

These two product-sum formulae are not in the formula booklet: derive them when asked. The useful skill is organising the extra term so that its factors help you.

Watch out

Wrong: add $k(k+2)$ to $\sum_{r=1}^{k}r(r+2)$ . That repeats the last old term. Right: add $(k+1)(k+3)$ , replacing both occurrences of the index before simplifying.

Pearson's induction schemes reward a visible use of the assumed sum. Even a correct direct calculation from other summation formulae does not answer an instruction to prove by induction.

Exam tip

Show the first substitution explicitly and finish with the three connected claims: true at the base case; true at $k$ implies true at $k+1$ ; therefore true on the stated integer domain. “True at $1$ , $k$ and $k+1$ ” misses the implication.

The next sum changes the second factor once more. Keep the factor shared by the old sum and the new term.

Proving sums of squares and cubes

When the new term is a power, leave its natural factor $k+1$ visible: it is also a factor in the next-case formula.

The formula booklet supplies the sums of squares and cubes shown below. That is useful for calculation, but a printed formula does not replace the requested induction proof. You must connect the $k$ -term sum to the $(k+1)$ -term sum.

Sums of squares and cubes

For every positive integer $n$ :

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

In the formula booklet.

In a proof, your job is to explain why the supplied expression continues to work, rather than use it on both sides without justification.

Worked example 3: the sum of squares

Question. Prove by induction that $\sum_{r=1}^{n}r^2=\dfrac{n(n+1)(2n+1)}{6}$ for all positive integers $n$ .

Plan. Verify the first case, assume the sum to $k$ , add $(k+1)^2$ and factor out $k+1$ .

At $n=1$ ,

\text{LHS}=1^2=1 \qquad \text{RHS}=\frac{1(2)(3)}{6}=1

so the result is true for $n=1$ .

Assume $\sum_{r=1}^{k}r^2=\dfrac{k(k+1)(2k+1)}{6}$ for an arbitrary positive integer $k$ . Then

\begin{aligned} \sum_{r=1}^{k+1}r^2 &=\frac{k(k+1)(2k+1)}{6}+(k+1)^2 &&\text{use the assumption}\\ &=\frac{k+1}{6}\bigl[k(2k+1)+6(k+1)\bigr] &&\text{factor out }k+1\\ &=\frac{k+1}{6}(2k^2+7k+6) &&\text{expand the bracket}\\ &=\frac{(k+1)(k+2)(2k+3)}{6} &&\text{factorise}\\ &=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} &&\text{the required next form} \end{aligned}

Why this step? The factor $k+1$ is already present in both terms. Taking it out reduces the remaining task to factoring a quadratic.

Answer. Truth for $n=k$ implies truth for $n=k+1$ . The result is true for $n=1$ , so it holds for all positive integers $n$ , by induction.

Check. At $n=4$ , $1+4+9+16=30=4(5)(9)/6$ .

Worked example 4 changes the exponent from $2$ to $3$ . The new term now shares $(k+1)^2$ with the assumed expression, making the key factorisation especially short.

Worked example 4: the sum of cubes

Question. Prove by induction that $\sum_{r=1}^{n}r^3=\dfrac{n^2(n+1)^2}{4}$ for all positive integers $n$ .

Plan. Verify $n=1$ , then add $(k+1)^3$ to the assumed sum and take out $(k+1)^2/4$ .

At $n=1$ ,

\text{LHS}=1^3=1 \qquad \text{RHS}=\frac{1^2(2^2)}{4}=1

so the result is true for $n=1$ .

Assume $\sum_{r=1}^{k}r^3=\dfrac{k^2(k+1)^2}{4}$ for an arbitrary positive integer $k$ . Then

\begin{aligned} \sum_{r=1}^{k+1}r^3 &=\frac{k^2(k+1)^2}{4}+(k+1)^3 &&\text{add the new cube}\\ &=\frac{(k+1)^2}{4}\bigl[k^2+4(k+1)\bigr] &&\text{take out the shared square}\\ &=\frac{(k+1)^2}{4}(k^2+4k+4) &&\text{expand the bracket}\\ &=\frac{(k+1)^2(k+2)^2}{4} &&\text{recognise a perfect square}\\ &=\frac{(k+1)^2((k+1)+1)^2}{4} &&\text{the required next form} \end{aligned}

Why this step? The next case needs a squared factor $(k+2)^2$ . The bracket becomes exactly that square when the shared $(k+1)^2$ is removed first.

Answer. If the formula is true for $n=k$ , it is true for $n=k+1$ . It is true for $n=1$ , so it is true for every positive integer $n$ , by induction.

Check. At $n=4$ , $1+8+27+64=100=4^2(5^2)/4$ .

The opening puzzle is now answered. From A-level Mathematics, $1+2+\cdots+n=n(n+1)/2$ , so its square is $n^2(n+1)^2/4$ , exactly the sum of cubes. The arithmetic-series formula is also in the formula booklet. This identity says that a sum built from cubes always lands on a perfect square.

Watch out

Wrong: $\sum_{r=1}^{k+1}r^3=\dfrac{(k+1)^2(k+2)^2}{4}$ “by the formula”. That is the next case you are trying to establish. Right: start with the assumed $k$ -term sum plus $(k+1)^3$ , and reach the next form through the displayed factorisation.

You can change the summand without changing the induction structure. For odd squares, the extra term is $(2(k+1)-1)^2=(2k+1)^2$ ; write it carefully before simplifying.

Quick Recap

Verify the starting case, assume one arbitrary case and use it to prove the next.
A sum to $k+1$ is the assumed sum to $k$ plus its new term with index $k+1$ .
Keep common factors such as $k+1$ or $(k+1)^2$ visible while simplifying.
Finish by linking the implication and the base case to every integer in the stated domain.

The cubes puzzle holds for every positive integer: $1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2$ .

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

CP 1.1 - Induction for sums of series

Why one starting case can reach every integer

Adding the next term to a product sum

Proving sums of squares and cubes

Quick Recap

Learn faster with Nova