Proofs of summation formulas | Year 12

01 / LEARN

The idea, step by step

Read a finite sum

The running index is a dummy variable, while the upper bound determines the final term. Increasing that upper bound by one leaves every old term unchanged. Separating the new term makes the induction step visible.

Small numerical checks help catch a false conjecture or copying error. They do not replace the general implication.

Choose useful algebra

For square and cube sums, factor common powers of k+1 before expanding. For rational terms, use a common denominator and look for cancellation. Every endpoint must equal the proposed formula at k+1.

Even when the calculation is long, include the base case and hypothesis. An isolated factorisation is only part of a proof.

A common trap

Adding the old final term again.

Instead: The new term is evaluated at the new index k+1.

02 / WORKED EXAMPLES

See the thinking

Example 1

Squares

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

At $n = 1$ , $1 = 1 (2) (3) / 6$ .
Assume the formula holds at arbitrary $n = k$ .
Add ${(k + 1)}^{2}$ and factor $(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$ .
Conclude all positive integers by induction.

\sum_{r = 1}^{n} r^{2} = n (n + 1) (2 n + 1) / 6

is true throughout the stated domain.

Example 2

A rational sum

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

At $n = 1$ , both sides are $1 / 2$ .
Assume the sum to $k$ is $k / (k + 1)$ .
Add $1 / [(k + 1) (k + 2)]$ .
The numerator over the common denominator is $k (k + 2) + 1 = {(k + 1)}^{2}$ .
Cancellation gives $(k + 1) / (k + 2)$ .
Conclude all positive integers by induction.

\sum_{r = 1}^{n} 1 / [r (r + 1)] = n / (n + 1)

is true throughout the stated domain.

Check your understanding

Which new term extends a cube sum?

Show answer

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

The upper index has increased by one.

03 / WORKSHEET

Your turn

6 questions · 36 marks · Work at your own pace.

Worksheet PDF Worked solutions

Read the questions online

Prove $1 + 2 + \dots + n = 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} = 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} = {[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} 1 / [r (r + 1)] = 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) = 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 = 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 $k (k + 1) / 2$ .
(b) Add the next term $k + 1$ .
(b) The next sum is $k (k + 1) / 2 + (k + 1) = (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 $k (k + 1) / 2$ .
  At $n = 1$ , both sides are $1$ . Assume the sum to arbitrary integer $k \geq 1$ is $k (k + 1) / 2$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add the next term $k + 1$ .
  The next sum is $k (k + 1) / 2 + (k + 1) = (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 $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} = n (n + 1) (2 n + 1) / 6$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , $1 = 1 (2) (3) / 6$ .
(a) Assume the formula holds at arbitrary $n = k$ .
(b) Add ${(k + 1)}^{2}$ and factor $(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 = 1 (2) (3) / 6$ .
  Assume the formula holds at arbitrary $n = k$ .
  At $n = 1$ , $1 = 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 $(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 = 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} = {[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 $k^{2} {(k + 1)}^{2} / 4$ .
(b) Add ${(k + 1)}^{3}$ and factor ${(k + 1)}^{2} / 4$ .
(b) The remaining factor is $k^{2} + 4 k + 4 = {(k + 2)}^{2}$ .
(b) The result is ${[(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 $k^{2} {(k + 1)}^{2} / 4$ .
  At $n = 1$ , both sides are $1$ . Assume the sum to $k$ is $k^{2} {(k + 1)}^{2} / 4$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add ${(k + 1)}^{3}$ and factor ${(k + 1)}^{2} / 4$ .
  The remaining factor is $k^{2} + 4 k + 4 = {(k + 2)}^{2}$ .
  The result is ${[(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 $k^{2} {(k + 1)}^{2} / 4$ . (b) The statement holds for all positive integers.
Prove $\sum_{r = 1}^{n} 1 / [r (r + 1)] = n / (n + 1)$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , both sides are $1 / 2$ .
(a) Assume the sum to $k$ is $k / (k + 1)$ .
(b) Add $1 / [(k + 1) (k + 2)]$ .
(b) The numerator over the common denominator is $k (k + 2) + 1 = {(k + 1)}^{2}$ .
(b) Cancellation gives $(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 $1 / 2$ .
  Assume the sum to $k$ is $k / (k + 1)$ .
  At $n = 1$ , both sides are $1 / 2$ . Assume the sum to $k$ is $k / (k + 1)$ .
2. (b)
  Prove the next case and conclude.
  4 marks
  Add $1 / [(k + 1) (k + 2)]$ .
  The numerator over the common denominator is $k (k + 2) + 1 = {(k + 1)}^{2}$ .
  Cancellation gives $(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 $1 / 2$ . Assume the sum to $k$ is $k / (k + 1)$ . (b) The statement holds for all positive integers.
Prove $\sum_{r = 1}^{n} r (r + 1) = n (n + 1) (n + 2) / 3$ for all integers $n \geq 1$ .
6 marks
(a) At $n = 1$ , $2 = 1 (2) (3) / 3$ .
(a) Assume the formula holds at $n = k$ .
(b) Add $(k + 1) (k + 2)$ .
(b) Factoring gives $(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 = 1 (2) (3) / 3$ .
  Assume the formula holds at $n = k$ .
  At $n = 1$ , $2 = 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 $(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 = 1 (2) (3) / 3$ . Assume the formula holds at $n = k$ . (b) The statement holds for all positive integers.

Checking saved progress…

Continue learning

Divisibility proofs

Next lesson

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 ↗

Back to Mathematical induction