Maths › Further proof › Proof by induction: sums and series
Proof by induction: sums and series
One argument that proves infinitely many statements at once: check the first, show each one forces the next, and every case falls.
Builds on The structure of proof and Sequences and sigma notation.
IN THIS TOPIC
- State the principle of induction and its two obligations, base case and inductive step.
- Prove a sum formula by induction, showing where the assumption is used.
- Close a proof with the conclusion sentence that earns the final mark.
WHAT YOU PROBABLY THINK
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, and 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, and the opening claim founders on the first: checks at n = 1, 2, 3 are three dominoes knocked over by hand, with nothing to say the fourth will follow.
The standard sum proof
Sum formulae are induction's home ground, because adding one more term is precisely the move from P(k) to P(k + 1): 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: 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: 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 is not an inductive step, and examiners look for the moment 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 that visibly uses the assumption, and the closing sentence. The close is a fixed formula worth learning word for word:
followed by 'so the statement is true for all positive integers n by induction'. Missing the conclusion, or asserting P(k + 1) without deriving it, are the two places these proofs shed marks.
YOUR TURN
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.
THE EXAM BIT
- Evaluate both sides at the base case; writing 'true for n = 1' without numbers scores nothing.
- State the assumption in full: 'assume 1 + 3 + … + (2k − 1) = k².'; a bare 'assume true for k' scores nothing.
- In the step, point at the moment the assumption is used; that substitution carries the method mark.
- 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
B
a
s
e
c
a
s
e
,
n
=
1
:
l
e
f
t
s
i
d
e
1
,
r
i
g
h
t
s
i
d
e
1
×
2
/
2
=
1
,
t
r
u
e
.
A
s
s
u
m
e
1
+
2
+
…
+
k
=
k
(
k
+
1
)
/
2
.
A
d
d
i
n
g
k
+
1
:
k
(
k
+
1
)
/
2
+
(
k
+
1
)
=
(
k
+
1
)
(
k
/
2
+
1
)
=
(
k
+
1
)
(
k
+
2
)
/
2
,
t
h
e
f
o
r
m
u
l
a
a
t
n
=
k
+
1
.
T
r
u
e
f
o
r
n
=
1
,
a
n
d
t
r
u
e
f
o
r
k
+
1
w
h
e
n
e
v
e
r
t
r
u
e
f
o
r
k
,
s
o
t
r
u
e
f
o
r
a
l
l
p
o
s
i
t
i
v
e
i
n
t
e
g
e
r
s
n
b
y
i
n
d
u
c
t
i
o
n
.
Base case plus inductive step: verify P(1), then show P(k) forces P(k + 1).
For sums, the step is always: add the next term to the assumed total, then tidy.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- State the principle of induction and its two obligations, base case and inductive step.
- Prove a sum formula by induction, showing 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.
No animated video for this topic yet; these notes stand alone.