Maths › Further proof › Proof by induction: sums and series

Proof by induction: sums and series

To prove P(n) for every integer n ≥ 1, verify P(1), assume P(k) for an arbitrary positive integer k, and use that assumption to derive P(k + 1). Apply the method to sums and series, including questions that give the first few cases and require a formula to be conjectured before it is proved.

Year FMEDEXCEL 9FM0 CP1 1.1

Builds on The structure of proof and Sequences and sigma notation.

IN THIS TOPIC

Say why the base case and the inductive step are both required, and what a proof missing either one establishes.
Prove a sum formula by induction, showing plainly where the assumption is used.
Conjecture a formula from the first few cases, then prove the conjecture by induction.
Close a proof with the required conclusion sentence.

COMMON MISCONCEPTION

Checking a formula for n = 1, 2 and 3 amounts to a proof by induction.

Induction has two parts: P(1) verified with both sides evaluated, and P(k) shown to force P(k + 1) for an arbitrary positive integer k. Verifying n = 1, 2 and 3 establishes those three cases and says nothing about n = 4. Three values are enough to conjecture a formula, and until the inductive step is supplied the conjecture is supported by evidence only.

The principle of induction

To prove P(n) for every integer n ≥ 1, verify P(1), assume P(k) for an arbitrary positive integer k, and use that assumption to derive P(k + 1). Checking several individual values is evidence only; it does not prove the general statement.

FIG. 1The base case establishes P(1); the inductive step establishes that P(k) implies P(k + 1) for every k.

The two parts have names. The base case verifies P(1) directly, with both sides evaluated. The inductive step assumes P(k) for some positive integer k, the inductive hypothesis, and derives P(k + 1) from it. Both are required.

The standard sum proof

For a sum, begin the k + 1 case by adding the next term to the assumed k-term result. Substitute the inductive hypothesis, simplify to the required formula with k + 1, and state the conclusion.

Columns of squares rising one, two, three, four, five: fifteen blocks in a staircase, matching the closed formula n times n plus one over two at n equals five. — FIG. 2The staircase picture of 1 + 2 + 3 + 4 + 5: fifteen blocks, and n(n + 1)/2 counts them.

WORKED EXAMPLE

The sum of the first n odd numbers

Prove by induction that 1 + 3 + 5 + … + (2n − 1) = n² for all positive integers n.

Base case, n = 1. The left side is 1 and the right side is 1² = 1. True.

Assume true for n = k, so 1 + 3 + … + (2k − 1) = k².

Then for n = k + 1 the sum is k² + (2k + 1) by the assumption, and k² + 2k + 1 = (k + 1)², which is the formula with k + 1 in place of k.

True for n = 1, and true for k + 1 whenever true for k, so true for all positive integers n by induction. ∎

The inductive hypothesis is used at the point where the k-term sum is replaced by k². An inductive step that does not use the hypothesis proves nothing; make the line where it is applied explicit.

Conjecture, then prove

Some questions do not supply the formula. They give the first few totals, or a rule for building each term from the previous one, and require the pattern to be identified first. Finding it is arithmetic; the proof that follows is the same induction, with the conjecture as P(n). Write the conjecture as an equation in n before starting the proof, so that it can be assumed at n = k and derived at n = k + 1.

WORKED EXAMPLE

A sum you have to guess first

Let S(n) = 1/(1 × 2) + 1/(2 × 3) + … + 1/(n(n + 1)). Find S(1), S(2) and S(3), conjecture a formula for S(n), and prove it.

S(1) = 1/2. S(2) = 1/2 + 1/6 = 2/3. S(3) = 2/3 + 1/12 = 3/4.

Numerators 1, 2, 3 over denominators 2, 3, 4, so the conjecture is S(n) = n/(n + 1).

Base case, n = 1. S(1) = 1/2 and the formula gives 1/2. True.

Assume S(k) = k/(k + 1). Then S(k + 1) = k/(k + 1) + 1/((k + 1)(k + 2)) = (k(k + 2) + 1)/((k + 1)(k + 2)) = (k + 1)²/((k + 1)(k + 2)) = (k + 1)/(k + 2).

That is the conjecture with k + 1 in place of k. True for n = 1, and true for k + 1 whenever true for k, so S(n) = n/(n + 1) for all positive integers n by induction. ∎

Three cases are enough to identify the pattern but do not prove it. State the conjecture as an equation and check that the base case agrees with it.

Writing it up

A complete induction proof has four visible parts: the base case with both sides evaluated; the assumption stated in full for n = k; the derivation of the n = k + 1 statement, using that assumption explicitly; and the closing sentence:

\text{true for } n = 1, \text{ and true for } k + 1 \text{ whenever true for } k

followed by 'so the statement is true for all positive integers n by induction'. Include the conclusion, and derive P(k + 1) rather than asserting it: writing down the k + 1 statement is not a proof of it.

GUIDED PRACTICE

A sum with a product formula

Prove by induction that Σr(r + 1), for r from 1 to n, equals n(n + 1)(n + 2)/3.

Show the working

Base case, n = 1. Left side 1 × 2 = 2; right side 1 × 2 × 3/3 = 2. True.

Assume the result for n = k, then add the (k + 1)th term. k(k + 1)(k + 2)/3 + (k + 1)(k + 2) = (k + 1)(k + 2)(k/3 + 1) = (k + 1)(k + 2)(k + 3)/3.

That is the formula at n = k + 1. True for n = 1 and inherited from k to k + 1, so true for all positive integers n by induction. ∎ Factorising out (k + 1)(k + 2) early keeps the algebra to one line.

ASSESSMENT FOCUS

Evaluate both sides at the base case. Writing 'true for n = 1' without numbers verifies nothing.
State the assumption in full: write 'assume 1 + 3 + … + (2k − 1) = k²' rather than 'assume true for k'.
Finish with the standard conclusion sentence naming n = 1, the k to k + 1 inheritance, and 'by induction'.
When the formula has to be conjectured, write it out as an equation in n first. The proof that follows is the ordinary one.

CHECK YOURSELF

Prove by induction that 1 + 2 + 3 + … + n = n(n + 1)/2 for all positive integers n.

Show a hint

In the inductive step, add the (k + 1)th term, k + 1, to the assumed sum and factorise.

Show the answer

Base case, n = 1. Left side 1, right side 1 × 2/2 = 1, true. Assume 1 + 2 + … + k = k(k + 1)/2. Adding k + 1 gives k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2, the formula at n = k + 1. True for n = 1, and true for k + 1 whenever true for k, so true for all positive integers n by induction.

Verify P(1), then show P(k) forces P(k + 1). Both, every time.

For sums, the step is always the same. Add the next term to the assumed total, then tidy.

Write out the conclusion sentence in full: the proof is not complete without it.

WORKBOOK

Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.

Or read them with their worked answers on the proof by induction: sums and series questions page.

USED LATER IN

CHECK YOUR PROGRESS

Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.

Say why the base case and the inductive step are both required, and what a proof missing either one establishes.
Prove a sum formula by induction, showing plainly where the assumption is used.
Conjecture a formula from the first few cases, then prove the conjecture by induction.
Close a proof with the required conclusion sentence.

Open the full revision checklist to see every objective in the course in one place.