Divisibility

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

Divisibility

What divisible means

A whole number $\displaystyle a$ is divisible by 6 if $\displaystyle {a}={6m}$ for a whole number $\displaystyle m$ .

The sum of two numbers divisible by 6 is divisible by 6: $\displaystyle {6m+6p}={6(m+p)}$ .
A number divisible by 6 times a whole number is divisible by 6.

A proof:

\displaystyle 7^n-1

is divisible by 6

$\displaystyle {7^1-1}={6}$ , $\displaystyle {7^2-1}={48}$ , $\displaystyle {7^3-1}={342}={6\cdot57}$ . The proof below proves by induction that $\displaystyle 7^n-1$ is divisible by 6 for every natural $\displaystyle n$ . In the step we write $\displaystyle 7^{k+1}-1$ with $\displaystyle 7^k-1$ :

	Claim	Reason
1	$\displaystyle {7^1-1}={6}$ is divisible by 6	Base case
2	$\displaystyle {7^k-1}={6m}$ , $\displaystyle m$ whole	The induction hypothesis
3	To prove: $\displaystyle 7^{k+1}-1$ is divisible by 6	The claim for $\displaystyle k+1$
4	$\displaystyle {7^{k+1}-1}={7\cdot7^k-1}={7(7^k-1)+6}$	The laws of powers; $\displaystyle {7\cdot(-1)+6}={-1}$
5	$\displaystyle {7(7^k-1)+6}={7\cdot6m+6}={6(7m+1)}$	By the induction hypothesis (2); $\displaystyle 7m+1$ is whole, and (3) is proved
6	$\displaystyle 7^n-1$ is divisible by 6 for every natural $\displaystyle n$	Conclusion: the principle of induction

A second way

The same claim without induction, from the sum of a geometric sequence ( $\displaystyle {a_1}={1}$ , $\displaystyle {q}={7}$ ):

1+7+7^2+\ldots+7^{n-1}=\frac{7^n-1}{7-1}

So $\displaystyle {7^n-1}={6\cdot(1+7+\ldots+7^{n-1})}$ , and the sum in brackets is whole. Induction is one way to prove; sometimes there are others.

Example:

\displaystyle n^3+2n

is divisible by 3

Base case: $\displaystyle {1+2}={3}$ .
Inductive step: assume that $\displaystyle {k^3+2k}={3m}$ . Then

(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3(k^2+k+1)=3m+3(k^2+k+1)=3(m+k^2+k+1)

Conclusion: by the principle of induction, $\displaystyle n^3+2n$ is divisible by 3 for every natural $\displaystyle n$ .

The idea of the step: find inside the expression for $\displaystyle k+1$ the expression for $\displaystyle k$ , and show that what is left is divisible by itself.

Exercise 1

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

Base case

Inductive step

Write $\displaystyle 5^{k+1}-1$ with $\displaystyle 5^k-1$ :

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

What follows from the last line, and what is the conclusion?

Exercise 2

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

Base case

Inductive step

Write $\displaystyle 4^{k+1}+2$ with $\displaystyle 4^k+2$ :

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

Exercise 3

Prove by induction that $\displaystyle 11^n-4^n$ is divisible by 7 for every natural $\displaystyle n$ . (A hint: $\displaystyle {11^{k+1}}={11\cdot11^k}$ , and $\displaystyle {4^{k+1}}={11\cdot4^k-7\cdot4^k}$ .)

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

Exercise 4

A sequence is defined by the recursion rule $\displaystyle {a_1}={6}$ , $\displaystyle {a_{n+1}}={a_n+2n^3+3n^2+n}$ .
Prove that every term of the sequence is divisible by 6.

Factorise $\displaystyle 2k^3+3k^2+k$ , and show – with the formula for the sum of the squares – that it is divisible by 6.

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

Write the proof by induction.

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