Proving sum formulas

Sequences and induction, grade 11 (5 units) Lesson 18 of 23Learning

Proving sum formulas

The sum of the natural numbers

The proof below proves by induction that $\displaystyle {1+2+\ldots+n}={\frac{n(n+1)}{2}}$ for every natural $\displaystyle n$ . Going from $\displaystyle k$ to $\displaystyle k+1$ adds exactly one term to the sum, $\displaystyle k+1$ :

	Claim	Reason
1	For $\displaystyle {n}={1}$ : $\displaystyle {1}={\frac{1\cdot2}{2}}$	Base case
2	$\displaystyle {1+2+\ldots+k}={\frac{k(k+1)}{2}}$	The induction hypothesis
3	To prove: $\displaystyle {1+2+\ldots+k+(k+1)}={\frac{(k+1)(k+2)}{2}}$	The claim for $\displaystyle k+1$
4	$\displaystyle {1+2+\ldots+k+(k+1)}={\frac{k(k+1)}{2}+(k+1)}$	By the induction hypothesis (2)
5	$\displaystyle {\frac{k(k+1)}{2}+(k+1)}={\frac{k(k+1)+2(k+1)}{2}}$	A common denominator
6	$\displaystyle {\frac{k(k+1)+2(k+1)}{2}}={\frac{(k+1)(k+2)}{2}}$	Taking out the common factor $\displaystyle k+1$ ; (3) is proved
7	$\displaystyle {1+2+\ldots+n}={\frac{n(n+1)}{2}}$ for every natural $\displaystyle n$	Conclusion: the principle of induction

How to write the step

First write what must be proved – the claim for $\displaystyle k+1$ . That way you know where to arrive.
Start from the left side for $\displaystyle k+1$ , and find in it the left side for $\displaystyle k$ : it is everything but the last term.
Put the right side of the hypothesis in its place.
Take out the common factor (here $\displaystyle k+1$ ) instead of expanding all the brackets: that is how the right side for $\displaystyle k+1$ shows up.

The sum of the squares

The claim: $\displaystyle {1^2+2^2+\ldots+n^2}={\frac{n(n+1)(2n+1)}{6}}$ for every natural $\displaystyle n$ .

Base case: $\displaystyle {1^2}={1}$ and $\displaystyle {\frac{1\cdot2\cdot3}{6}}={1}$ .
Inductive step: assume that $\displaystyle {1^2+\ldots+k^2}={\frac{k(k+1)(2k+1)}{6}}$ . We must prove that $\displaystyle {1^2+\ldots+k^2+(k+1)^2}={\frac{(k+1)(k+2)(2k+3)}{6}}$ :

\begin{aligned}1^2+\ldots+k^2+(k+1)^2&=\frac{k(k+1)(2k+1)}{6}+(k+1)^2\\&=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}\\&=\frac{(k+1)(2k^2+7k+6)}{6}\\&=\frac{(k+1)(k+2)(2k+3)}{6}\end{aligned}

Conclusion: by the principle of induction, the formula holds for every natural $\displaystyle n$ .

A geometric sum

The claim: $\displaystyle {1+2+4+\ldots+2^{n-1}}={2^n-1}$ for every natural $\displaystyle n$ .

Base case: $\displaystyle {1}={2^1-1}$ .
Inductive step: assume that $\displaystyle {1+2+\ldots+2^{k-1}}={2^k-1}$ . Then $\displaystyle {1+2+\ldots+2^{k-1}+2^k}={(2^k-1)+2^k}={2\cdot2^k-1}={2^{k+1}-1}$ – the claim for $\displaystyle k+1$ .
Conclusion: by the principle of induction, the claim holds for every natural $\displaystyle n$ .

This is a second proof of the geometric sum formula, for $\displaystyle {a_1}={1}$ , $\displaystyle {q}={2}$ .

Exercise 1

$\displaystyle {1\cdot2+2\cdot3+\ldots+n(n+1)}={\frac{n(n+1)(n+2)}{3}}$
Prove by induction that the claim holds for every natural $\displaystyle n$ .

Base case

Check the claim for $\displaystyle {n}={1}$ .

Inductive step

Write the induction hypothesis – the claim for some natural $\displaystyle k$ – and what must be proved for $\displaystyle k+1$ .

The working: start from the expression you got after putting in the hypothesis, and reach what must be proved.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – check and a new line · * – times · ^ – power, ↓ – end of the power

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Conclusion

Exercise 2

$\displaystyle {1^3+2^3+\ldots+n^3}={\frac{n^2(n+1)^2}{4}}$
Prove by induction that the claim holds for every natural $\displaystyle n$ .

Base case

Check the claim for $\displaystyle {n}={1}$ .

Inductive step

Write the induction hypothesis – the claim for some natural $\displaystyle k$ – and what must be proved for $\displaystyle k+1$ .

The working: start from the expression you got after putting in the hypothesis, and reach what must be proved.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Conclusion

Exercise 3

$\displaystyle {\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\ldots+\frac{1}{n(n+1)}}={\frac{n}{n+1}}$
Prove by induction that the claim holds for every natural $\displaystyle n$ .

Base case

Check the claim for $\displaystyle {n}={1}$ .

Inductive step

Write the induction hypothesis – the claim for some natural $\displaystyle k$ – and what must be proved for $\displaystyle k+1$ .

The working: start from the expression you got after putting in the hypothesis, and reach what must be proved.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Conclusion

Exercise 4

$\displaystyle {1+3+9+\ldots+3^{n-1}}={\frac{3^n-1}{2}}$
Prove by induction that the claim holds for every natural $\displaystyle n$ .

Base case

Check the claim for $\displaystyle {n}={1}$ .

Inductive step

Write the induction hypothesis – the claim for some natural $\displaystyle k$ – and what must be proved for $\displaystyle k+1$ .

The working: start from the expression you got after putting in the hypothesis, and reach what must be proved.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Conclusion

Exercise 5

$\displaystyle {2+5+8+\ldots+(3n-1)}={\frac{n(3n+1)}{2}}$
Prove by induction that the claim holds for every natural $\displaystyle n$ .

Base case

Check the claim for $\displaystyle {n}={1}$ .

Inductive step

Write the induction hypothesis – the claim for some natural $\displaystyle k$ – and what must be proved for $\displaystyle k+1$ .

The working: start from the expression you got after putting in the hypothesis, and reach what must be proved.

/ – fraction bar · Tab or the arrows – between numerator and denominator, then a note above or below · Enter – a new line · * – times · ^ – power, ↓ – end of the power

Conclusion

Formulas: sequences and induction, grade 11 (5 units)

Open as a page

A sequence and the sum of its first terms

The term from the sum – $\displaystyle S_n$ the sum of the first $\displaystyle n$ terms
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle S_n-S_{n-1}$ $\displaystyle n\geq2$
The first term is the sum of one term
$\displaystyle a_1$ $\displaystyle =$ $\displaystyle S_1$

The arithmetic sequence

The recursion rule – $\displaystyle d$ the common difference
$\displaystyle a_{n+1}=a_n+d$
The general term
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle a_1+(n-1)d$
The arithmetic mean of the neighbours
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle \frac{a_{n-1}+a_{n+1}}{2}$ $\displaystyle n\geq2$
The sum of the first $\displaystyle n$ terms
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{n(a_1+a_n)}{2}$
The sum without the last term
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{n\left[2a_1+(n-1)d\right]}{2}$

The geometric sequence

The recursion rule – $\displaystyle q$ the common ratio
$\displaystyle a_{n+1}=a_n\cdot q$
The general term
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle a_1\cdot q^{n-1}$
The geometric mean: a term’s square is the product of its neighbours
$\displaystyle a_n^2$ $\displaystyle =$ $\displaystyle a_{n-1}\cdot a_{n+1}$ $\displaystyle n\geq2$
The sum of the first $\displaystyle n$ terms
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{a_1(q^n-1)}{q-1}$ $\displaystyle q\neq1$

The infinite geometric sequence

The sum of a convergent sequence
$\displaystyle S$ $\displaystyle =$ $\displaystyle \frac{a_1}{1-q}$ $\displaystyle -1<q<1,\ q\neq0$

The laws of powers

A product of powers of one base
$\displaystyle a^m\cdot a^n$ $\displaystyle =$ $\displaystyle a^{m+n}$
A quotient of powers of one base
$\displaystyle \frac{a^m}{a^n}$ $\displaystyle =$ $\displaystyle a^{m-n}$ $\displaystyle a\neq0$
A power of a power
$\displaystyle \left(a^m\right)^n$ $\displaystyle =$ $\displaystyle a^{mn}$
A power with exponent 0
$\displaystyle a^0$ $\displaystyle =$ $\displaystyle 1$ $\displaystyle a\neq0$
A power with a negative exponent
$\displaystyle a^{-n}$ $\displaystyle =$ $\displaystyle \frac{1}{a^n}$ $\displaystyle a\neq0$

Sums proved by induction

The sum of the natural numbers
$\displaystyle 1+2+3+\ldots+n$ $\displaystyle =$ $\displaystyle \frac{n(n+1)}{2}$
The sum of the odd numbers
$\displaystyle 1+3+5+\ldots+(2n-1)$ $\displaystyle =$ $\displaystyle n^2$
The sum of the squares
$\displaystyle 1^2+2^2+3^2+\ldots+n^2$ $\displaystyle =$ $\displaystyle \frac{n(n+1)(2n+1)}{6}$
The sum of the cubes
$\displaystyle 1^3+2^3+3^3+\ldots+n^3$ $\displaystyle =$ $\displaystyle \frac{n^2(n+1)^2}{4}$