Practise › Questions › Proof by induction: sums and series

Proof by induction: sums and series questions

Proof by induction settles infinitely many statements with one argument. Check the base case, show that each case implies the next, and the result then holds for every n in the stated range.

7 original questions · 26 marks · the proof by induction: sums and series notes · Further proof

Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.

• 2 marks · state · warm-up

  State the two things a proof by induction must establish, and explain briefly why together they prove a statement for every positive integer n.

  Worked answer

  A base case (the statement holds at n = 1) and an inductive step (truth at n = k forces truth at n = k + 1). The base case starts the chain and the step passes truth along it, so every positive integer is eventually reached. B1 B1 for the base case and the inductive step.

• 2 marks · warm-up

  For the claim 1 + 3 + 5 + … + (2n − 1) = n², verify the base case and write down the inductive hypothesis.

  Worked answer

  At n = 1 the left side is 1 and the right side is 1² = 1, so the base case holds. Hypothesis: assume 1 + 3 + … + (2k − 1) = k² for some positive integer k. B1 for the base case, B1 for the hypothesis.

• 3 marks · complete

  Complete the inductive step for 1 + 3 + 5 + … + (2n − 1) = n², and state the conclusion.

  Worked answer

  Assuming the sum to k terms is k², adding the next odd number gives k² + (2k + 1) = (k + 1)². That is the claim at n = k + 1. With the base case established, the statement holds for all positive integers n by induction. M1 for adding the next odd number, A1 for (k + 1)², A1 for the conclusion.

• 5 marks · prove

  Prove by induction that the sum of the first n positive integers is n(n + 1)/2.

  Worked answer

  Base: n = 1 gives 1 = 1 × 2/2. Step: assume the sum to k is k(k + 1)/2; adding k + 1 gives k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, the formula at k + 1. Both parts hold, so the result is true for all n. B1 for the base case, M1 for adding k + 1 to the assumed sum, dM1 for taking out the common factor, A1 for (k + 1)(k + 2)/2, A1 for the conclusion. The common factor (k + 1) does the algebra, so take it out before expanding anything.

• 5 marks · prove

  Prove by induction that 2 + 4 + 8 + … + 2ⁿ = 2ⁿ⁺¹ − 2.

  Worked answer

  Base: n = 1 gives 2 = 2² − 2 = 2. Step: assume the sum to k is 2^k+1 − 2. Adding the next term 2^k+1 gives 2 × 2^k+1 − 2 = 2^k+2 − 2, which is the claim at k + 1. A spot check at n = 4: B1 for the base case, B1 for the hypothesis, M1 for adding 2^k+1, A1 for 2^k+2 − 2, A1 for the conclusion. 2 + 4 + 8 + 16 = 30 = 2⁵ − 2.

• 3 marks

  A student proves the inductive step for a formula but skips the base case. Explain why nothing has been proved, using the false claim 1 + 3 + … + (2n − 1) = n² + 1 as an illustration.

  Worked answer

  The step only passes truth along; without a first true case there is nothing to pass. The false formula n² + 1 also survives the inductive step, since adding 2k + 1 to k² + 1 gives (k + 1)² + 1. It fails only at the base case, 1 ≠ 2, which is exactly the part the student skipped. B1 for the step needing a first true case, M1 for the false formula surviving the step, A1 for its failure at n = 1.

• 6 marks · prove · stretch

  Prove by induction that the sum of r × 2^r from r = 1 to n equals (n − 1)2ⁿ⁺¹ + 2 for all positive integers n.

  Worked answer

  Base: at n = 1 the sum is 1 × 2 = 2, and the formula gives 0 × 4 + 2 = 2, so the two agree. Step: assume the sum to k terms is (k − 1)2^k+1 + 2. Adding the next term (k + 1)2^k+1 gives (k − 1)2^k+1 + (k + 1)2^k+1 + 2. Take out the common factor 2^k+1, leaving 2^k+1(k − 1 + k + 1) + 2 = 2^k+1(2k) + 2 = k2^k+2 + 2. The formula at n = k + 1 reads ((k + 1) − 1)2^k+2 + 2 = k2^k+2 + 2, which matches. True at n = 1 and inherited at every step, so true for all positive integers n by induction. B1 for the base case, M1 for adding (k + 1)2^k+1, dM1 for taking out 2^k+1, A1 for k2^k+2 + 2, A1 for matching the formula at k + 1, A1 for the conclusion. Factorising 2^k+1 out before combining is what keeps the algebra to one line; multiplying everything out in powers of 2 rarely closes.

The same practice on paper: the printable workbook for this topic, questions and a worked answer book.

Practise proof by induction: sums and series one question at a time

The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.