Proofs of summation formulas | Year 12

01 / LEARN

Understand the idea.

Read a finite sum

In $\sum_{r = 1}^{n} a_{r}$ , the index $r$ names the terms and the upper bound $n$ fixes the endpoint. Moving from $k$ to $k + 1$ leaves every old term unchanged and adds exactly $a_{k + 1}$ .

Check a small case to confirm that the proposed formula uses the correct starting index. This can expose a false claim, but a proof still needs an implication for arbitrary $k$ .

Choose useful algebra

After substituting the hypothesis, choose algebra that reveals the next formula. In a square sum, take out a factor $k + 1$ ; in a rational sum, combine fractions before cancelling.

Keep the base, hypothesis and conclusion visible around the calculation. A correct simplification establishes the successor step only when its starting point is justified by the assumed $k$ case.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

Squares

Prove $\sum_{r = 1}^{n} r^{2} = n (n + 1) (2 n + 1) / 6$ for $n \geq 1$ .

Worked solution

1
Verify the base.
$n = 1 : \sum_{r = 1}^{1} r^{2} = 1 = \frac{1 \cdot 2 \cdot 3}{6} .$
The identity holds at the first permitted integer.
2
Assume the formula at an arbitrary integer.
$\sum_{r = 1}^{k} r^{2} = \frac{k (k + 1) (2 k + 1)}{6}, k \geq 1.$
The assumed case supplies a value only for the old sum.
3
Add the new square and substitute.
$\begin{aligned} \sum_{r = 1}^{k + 1} r^{2} & = \sum_{r = 1}^{k} r^{2} + {(k + 1)}^{2} \\ = \frac{k (k + 1) (2 k + 1)}{6} + {(k + 1)}^{2} . \end{aligned}$
The additional term is evaluated at $r = k + 1$ .
4
Factor into the next-case form.
$\begin{aligned} \sum_{r = 1}^{k + 1} r^{2} & = \frac{k + 1}{6} (k (2 k + 1) + 6 (k + 1)) \\ = \frac{k + 1}{6} (2 k^{2} + 7 k + 6) \\ = \frac{(k + 1) (k + 2) (2 k + 3)}{6} . \end{aligned}$
The quadratic factors as $(k + 2) (2 k + 3)$ , matching the formula with $n = k + 1$ .
5
Conclude for all positive integers.
$\sum_{r = 1}^{n} r^{2} = \frac{n (n + 1) (2 n + 1)}{6} (n \in ℤ, n \geq 1) .$
The base case and arbitrary successor implication complete the induction.

Answer

$\sum_{r = 1}^{n} r^{2} = n (n + 1) (2 n + 1) / 6$ is true throughout the stated domain.

EXAMPLE 02

A rational sum

Prove $\sum_{r = 1}^{n} 1 / [r (r + 1)] = n / (n + 1)$ for $n \geq 1$ .

Worked solution

1
Check the first term.
$n = 1 : \frac{1}{1 \cdot 2} = \frac{1}{2} = \frac{1}{1 + 1} .$
Both sides agree at the beginning of the domain.
2
Assume the old sum.
$\sum_{r = 1}^{k} \frac{1}{r (r + 1)} = \frac{k}{k + 1}, k \in ℤ, k \geq 1.$
This is the case used inside the successor argument.
3
Add the term with the new index.
$\begin{aligned} \sum_{r = 1}^{k + 1} \frac{1}{r (r + 1)} & = \sum_{r = 1}^{k} \frac{1}{r (r + 1)} + \frac{1}{(k + 1) (k + 2)} \\ = \frac{k}{k + 1} + \frac{1}{(k + 1) (k + 2)} . \end{aligned}$
The old sum may now be replaced by the hypothesis.
4
Combine and simplify the fractions.
$\begin{aligned} \sum_{r = 1}^{k + 1} \frac{1}{r (r + 1)} & = \frac{k (k + 2) + 1}{(k + 1) (k + 2)} \\ = \frac{{(k + 1)}^{2}}{(k + 1) (k + 2)} \\ = \frac{k + 1}{k + 2} . \end{aligned}$
Both denominator factors are positive, so the cancellation is valid.
5
Complete the proof.
$\sum_{r = 1}^{n} \frac{1}{r (r + 1)} = \frac{n}{n + 1} (n \in ℤ, n \geq 1) .$
The final fraction is the required next case, and the base starts the chain.

Answer

$\sum_{r = 1}^{n} 1 / [r (r + 1)] = n / (n + 1)$ is true throughout the stated domain.

03 / YOUR TURN

Try it yourself.

Check your understanding

Which new term extends a cube sum?

Show answer & reasoning

${(k + 1)}^{3}$ .

A cube sum gains the cube at the new endpoint, ${(k + 1)}^{3}$ . The term $k^{3}$ is already included in the assumed sum.

Keep practising

6 worksheet questions · 36 marks

Open worksheet Worked solutions

Read the questions online

Prove $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $1 + 3 + \dots + (2 n - 1) = n^{2}$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $\sum_{r = 1}^{n} r^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $\sum_{r = 1}^{n} r^{3} = {[\frac{n (n + 1)}{2}]}^{2}$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $\sum_{r = 1}^{n} \frac{1}{r (r + 1)} = \frac{n}{n + 1}$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks
Prove $\sum_{r = 1}^{n} r (r + 1) = \frac{n (n + 1) (n + 2)}{3}$ for all integers $n \geq 1$ .
6 marks
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
2. (b)
  Prove the next case and conclude.
  4 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

Prove $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , both sides are $1$ .
(a) Assume the sum to arbitrary integer $k \geq 1$ is $\frac{k (k + 1)}{2}$ .
(b) Add the next term $k + 1$ .
(b) The next sum is $\frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1) (k + 2)}{2}$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , both sides are $1$ .
  Assume the sum to arbitrary integer $k \geq 1$ is $\frac{k (k + 1)}{2}$ .
  At $n = 1$ , both sides are $1$ . Assume the sum to arbitrary integer $k \geq 1$ is $\frac{k (k + 1)}{2}$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add the next term $k + 1$ .
  The next sum is $\frac{k (k + 1)}{2} + (k + 1) = \frac{(k + 1) (k + 2)}{2}$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , both sides are $1$ . Assume the sum to arbitrary integer $k \geq 1$ is $\frac{k (k + 1)}{2}$ . (b) The statement holds for all positive integers.
Prove $1 + 3 + \dots + (2 n - 1) = n^{2}$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , $1 = 1^{2}$ .
(a) Assume the first $k$ odd numbers sum to $k^{2}$ .
(b) Add the next odd term $2 k + 1$ .
(b) The result is $k^{2} + 2 k + 1 = {(k + 1)}^{2}$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , $1 = 1^{2}$ .
  Assume the first $k$ odd numbers sum to $k^{2}$ .
  At $n = 1$ , $1 = 1^{2}$ . Assume the first $k$ odd numbers sum to $k^{2}$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add the next odd term $2 k + 1$ .
  The result is $k^{2} + 2 k + 1 = {(k + 1)}^{2}$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , $1 = 1^{2}$ . Assume the first $k$ odd numbers sum to $k^{2}$ . (b) The statement holds for all positive integers.
Prove $\sum_{r = 1}^{n} r^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , $1 = \frac{1 (2) (3)}{6}$ .
(a) Assume the formula holds at arbitrary $n = k$ .
(b) Add ${(k + 1)}^{2}$ and factor $\frac{k + 1}{6}$ .
(b) The remaining factor is $k (2 k + 1) + 6 (k + 1) = 2 k^{2} + 7 k + 6$ .
(b) Factor it as $(k + 2) (2 k + 3)$ , giving the required formula at $k + 1$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , $1 = \frac{1 (2) (3)}{6}$ .
  Assume the formula holds at arbitrary $n = k$ .
  At $n = 1$ , $1 = \frac{1 (2) (3)}{6}$ . Assume the formula holds at arbitrary $n = k$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add ${(k + 1)}^{2}$ and factor $\frac{k + 1}{6}$ .
  The remaining factor is $k (2 k + 1) + 6 (k + 1) = 2 k^{2} + 7 k + 6$ .
  Factor it as $(k + 2) (2 k + 3)$ , giving the required formula at $k + 1$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , $1 = \frac{1 (2) (3)}{6}$ . Assume the formula holds at arbitrary $n = k$ . (b) The statement holds for all positive integers.
Prove $\sum_{r = 1}^{n} r^{3} = {[\frac{n (n + 1)}{2}]}^{2}$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , both sides are $1$ .
(a) Assume the sum to $k$ is $\frac{k^{2} {(k + 1)}^{2}}{4}$ .
(b) Add ${(k + 1)}^{3}$ and factor $\frac{{(k + 1)}^{2}}{4}$ .
(b) The remaining factor is $k^{2} + 4 k + 4 = {(k + 2)}^{2}$ .
(b) The result is ${[\frac{(k + 1) (k + 2)}{2}]}^{2}$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , both sides are $1$ .
  Assume the sum to $k$ is $\frac{k^{2} {(k + 1)}^{2}}{4}$ .
  At $n = 1$ , both sides are $1$ . Assume the sum to $k$ is $\frac{k^{2} {(k + 1)}^{2}}{4}$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add ${(k + 1)}^{3}$ and factor $\frac{{(k + 1)}^{2}}{4}$ .
  The remaining factor is $k^{2} + 4 k + 4 = {(k + 2)}^{2}$ .
  The result is ${[\frac{(k + 1) (k + 2)}{2}]}^{2}$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , both sides are $1$ . Assume the sum to $k$ is $\frac{k^{2} {(k + 1)}^{2}}{4}$ . (b) The statement holds for all positive integers.
Prove $\sum_{r = 1}^{n} \frac{1}{r (r + 1)} = \frac{n}{n + 1}$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , both sides are $\frac{1}{2}$ .
(a) Assume the sum to $k$ is $\frac{k}{k + 1}$ .
(b) Add $\frac{1}{(k + 1) (k + 2)}$ .
(b) The numerator over the common denominator is $k (k + 2) + 1 = {(k + 1)}^{2}$ .
(b) Cancellation gives $\frac{k + 1}{k + 2}$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , both sides are $\frac{1}{2}$ .
  Assume the sum to $k$ is $\frac{k}{k + 1}$ .
  At $n = 1$ , both sides are $\frac{1}{2}$ . Assume the sum to $k$ is $\frac{k}{k + 1}$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add $\frac{1}{(k + 1) (k + 2)}$ .
  The numerator over the common denominator is $k (k + 2) + 1 = {(k + 1)}^{2}$ .
  Cancellation gives $\frac{k + 1}{k + 2}$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , both sides are $\frac{1}{2}$ . Assume the sum to $k$ is $\frac{k}{k + 1}$ . (b) The statement holds for all positive integers.
Prove $\sum_{r = 1}^{n} r (r + 1) = \frac{n (n + 1) (n + 2)}{3}$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , $2 = \frac{1 (2) (3)}{3}$ .
(a) Assume the formula holds at $n = k$ .
(b) Add $(k + 1) (k + 2)$ .
(b) Factoring gives $\frac{(k + 1) (k + 2) (k + 3)}{3}$ .
(b) The true first case and successor implication establish the full domain by mathematical induction.
1. (a)
  Verify the first case and state the induction hypothesis.
  2 marks
  At $n = 1$ , $2 = \frac{1 (2) (3)}{3}$ .
  Assume the formula holds at $n = k$ .
  At $n = 1$ , $2 = \frac{1 (2) (3)}{3}$ . Assume the formula holds at $n = k$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add $(k + 1) (k + 2)$ .
  Factoring gives $\frac{(k + 1) (k + 2) (k + 3)}{3}$ .
  The true first case and successor implication establish the full domain by mathematical induction.
  The statement holds for all positive integers.
(a) At $n = 1$ , $2 = \frac{1 (2) (3)}{3}$ . Assume the formula holds at $n = k$ . (b) The statement holds for all positive integers.

Checking saved progress…

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 2 Specialist mathematical induction. Explicit summation, power and divisibility identities; induction of inequalities or recursive formulae is not required.

Official curriculum source ↗

In this lesson

Understand the idea.

Read a finite sum

Choose useful algebra

See the method in action.

Squares

Verify the base.

Assume the formula at an arbitrary integer.

Add the new square and substitute.

Factor into the next-case form.

Conclude for all positive integers.

A rational sum

Check the first term.

Assume the old sum.

Add the term with the new index.

Combine and simplify the fractions.

Complete the proof.

Try it yourself.

Check your understanding

Keep practising