Maths › Further proof › Proof by induction: sums and series
Proof by induction: sums and series
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.
Builds on The structure of proof and Sequences and sigma notation.
IN THIS TOPIC
- Prove a sum formula by induction, showing plainly where the assumption is used.
- Close a proof with the conclusion sentence that earns the final mark.
COMMON MISCONCEPTION
Checking a formula for n = 1, 2 and 3 amounts to a proof by induction.
One argument, infinitely many claims
Ordinary proof handles one statement at a time. Induction proves a statement P(n) for every positive integer n in one go, and it needs exactly two facts. That P(1) is true. That whenever P(k) is true, P(k + 1) must be true as well. Grant both and no case can fail, because a first failure at some n would need the case before it to have failed first.
The two obligations have names. The base case verifies P(1) directly, both sides computed. The inductive step assumes P(k) for some positive integer k, the inductive hypothesis, and derives P(k + 1) from it. Neither is optional. Checking n = 1, 2, 3 does not meet the second obligation: those are three dominoes knocked over by hand, and they say nothing whatever about the fourth.
The standard sum proof
Sum formulae are induction's home ground. Adding one more term is precisely the move from P(k) to P(k + 1), so you take the sum you assumed, add the (k + 1)th term, and tidy the algebra until the formula reappears with k + 1 in place of k.
WORKED EXAMPLE
The sum of the first n odd numbers
Prove by induction that 1 + 3 + 5 + … + (2n − 1) = n2 for all positive integers n.
Base case, n = 1. The left side is 1 and the right side is 12 = 1. True.
Assume true for n = k, so 1 + 3 + … + (2k − 1) = k2.
Then for n = k + 1 the sum is k2 + (2k + 1) by the assumption, and k2 + 2k + 1 = (k + 1)2, 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. ∎
Watch where the assumption earned its keep. The step replaced a k-term sum by k2 in one move. An inductive step that never uses the hypothesis has proved nothing, and examiners hunt for the exact line where it is applied.
Writing it up
A full-marks 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, visibly using that assumption. Then the closing sentence, which is a fixed formula worth learning word for word:
followed by 'so the statement is true for all positive integers n by induction'. Two habits cost marks every summer. Skipping the conclusion, and writing down P(k + 1) as though asserting it were the same as deriving 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. A bare 'assume true for k' is not worth a mark; 'assume 1 + 3 + … + (2k − 1) = k²' is.
- Finish with the standard conclusion sentence naming n = 1, the k to k + 1 inheritance, and 'by induction'.
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.
The conclusion sentence is a mark. Learn it and write it out.
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.
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.
- Prove a sum formula by induction, showing plainly where the assumption is used.
- Close a proof with the conclusion sentence that earns the final mark.
Open the full revision checklist to see every objective in the course in one place.