Practice: mathematical induction

Sequences and induction, grade 11 (5 units) Lesson 22 of 23Practice

Practice: mathematical induction

$\displaystyle {1+4+7+\ldots+(3n-2)}={\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 – 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

$\displaystyle {1\cdot2\cdot3+2\cdot3\cdot4+\ldots+n(n+1)(n+2)}={\frac{n(n+1)(n+2)(n+3)}{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

$\displaystyle {\frac{1}{1\cdot3}+\frac{1}{3\cdot5}+\ldots+\frac{1}{(2n-1)(2n+1)}}={\frac{n}{2n+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

A sequence is defined by the recursion rule $\displaystyle {a_1}={1}$ , $\displaystyle {a_{n+1}}={a_n+2^n}$ .
Prove by induction that $\displaystyle {a_n}={2^n-1}$ for every natural $\displaystyle n$ .

Base case

Inductive step

/ – 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

Prove by induction that $\displaystyle 6^n+4$ is divisible by 5 for every natural $\displaystyle n$ .

Inductive step

/ – 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

Prove by induction that $\displaystyle n^3-n$ is divisible by 3 for every natural $\displaystyle n$ .

Inductive step

/ – 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

Inbal wrote: “The claim: $\displaystyle {2+4+\ldots+2n}={n^2+n+5}$ . For $\displaystyle k+1$ : $\displaystyle {2+4+\ldots+2k+2(k+1)}={k^2+k+5+2k+2}={(k+1)^2+(k+1)+5}$ . Proved.”
What is missing in the proof? Is the claim true?

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}$