PROOF BY INDUCTION · HL
Divisibility
Prove an expression is always divisible by a fixed number.
Section 1 of 13
The method
Every proof by induction follows the same four lines.
Prove for $n = 1$
Assume for $n = k$
Prove for $n = k+1$
Conclusion: Since true for $n = 1$ and $n = k+1$ then true for all $n$.
Section 2 of 13
$5^{n} - 1$ is divisible by 4
Prove $5^{n} - 1$ is divisible by 4. $n \in \mathbb{N}$.
Prove for $n = 1$:
$5 - 1 = 4$, $4 \div 4 = 1$ True
Assume for $n = k$:
$5^{k} - 1$ is divisible by 4 (assumption)
Prove for $n = k+1$:
$5^{k+1} - 1$
$5(5^{k}) - 1$
$(4+1)5^{k} - 1$
$4(5^{k}) + 5^{k} - 1$
$4(5^{k})$ is true because of 4.
$5^{k} - 1$ true from assumption.
Since true for $n = 1$ and $n = k+1$ then true for all $n$.
Splitting the base: $5 = 2+3$, $5 = 4+1$, $5 = 5$, $5 = 6-1$. And $a^{p+2} = a^{p} \cdot a^{2}$.
Section 3 of 13
$7^{n} - 2^{n}$ is divisible by 5
Prove $7^{n} - 2^{n}$ is divisible by 5. $n \in \mathbb{N}$.
$n = 1$:
$7 - 2 = 5$
$n = k$:
$7^{k} - 2^{k}$ (assumption)
$n = k+1$:
$7^{k+1} - 2^{k+1}$
$7(7^{k}) - 2(2^{k})$
$(5+2)(7^{k}) - 2(2^{k})$
$5(7^{k}) + 2(7^{k}) - 2(2^{k})$
$5(7^{k}) + 2(7^{k} - 2^{k})$
Section 4 of 13
$4^{n} - 1$ is divisible by 3
Prove $4^{n} - 1$ is divisible by 3. $n \in \mathbb{N}$.
$n = 1$:
$4 - 1 = 3$, $3 \div 3 = 1$ True
$n = k$:
$4^{k} - 1$ is divisible by 3. (assumption)
$n = k+1$:
$4^{k+1} - 1$ No change
$4(4^{k}) - 1$ $4 = 3+1$
$(3+1)(4^{k}) - 1$
$3(4^{k}) + 4^{k} - 1$
$3(4^{k})$ True (÷3); $4^{k} - 1$ = assumption.
Section 5 of 13
$5^{n} - 2^{n}$ is divisible by 3
$5^{n} - 2^{n}$ divisible by 3.
$n = 1$:
$5 - 2 = 3$ — true
$n = k$:
$5^{k} - 2^{k}$ (assumption)
$n = k+1$:
$5^{k+1} - 2^{k+1}$
$5(5^{k}) - 2(2^{k})$
$(3+2)5^{k} - 2(2^{k})$
$3(5^{k}) + 2(5^{k}) - 2(2^{k})$
$3(5^{k}) + 2(5^{k} - 2^{k})$
$3(5^{k}) \to 3$ $2(5^{k} - 2^{k}) \to$ Ass
Section 6 of 13
$3^{2n} - 1$ is divisible by 8
Prove $3^{2n} - 1$ divisible by 8.
$n = 1$:
$3^{2} - 1 = 8$
$n = k$:
$3^{2k} - 1$ (assumption)
$n = k+1$:
$3^{2(k+1)} - 1$
$3^{2k+2} - 1$
$3^{2}(3^{2k}) - 1$
$9(3^{2k}) - 1$
$(8+1)\,3^{2k} - 1$
$8(3^{2k}) + 3^{2k} - 1$
Section 7 of 13
$2^{3n-1} + 3$ is divisible by 7
Prove $2^{3n-1} + 3$ divisible by 7.
$n = 1$:
$2^{2} + 3 = 7$
$n = k$:
$2^{3k-1} + 3$ $\div$ 7 (assumption)
$n = k+1$:
$2^{3(k+1)-1} + 3$
$2^{3k+3-1} + 3$
$2^{3k+2} + 3$
$2^{(3k-1)+3} + 3$ (Ass)
$2^{3}(2^{3k-1}) + 3$
$8(2^{3k-1}) + 3$
$(7+1)(2^{3k-1}) + 3$
$7(2^{3k-1}) + 2^{3k-1} + 3$
Exponent rule: $f(x) = 3x - 1$, so $f(k+1) = 3(k+1) - 1$. And $a^{p+q} = a^{p} \cdot a^{q}$.
Section 8 of 13
$9^{n} + 3$ is divisible by 4
Prove $9^{n} + 3$ is divisible by 4 for $n \in \mathbb{N}$.
Prove for $n = 1$:
$9 + 3 = 12$, $12 \div 4 = 3$ true
Assume for $n = k$:
$9^{k} + 3$ is divisible by 4 (assumption)
Prove for $n = k+1$:
$9^{(k+1)} + 3$
$9^{k+1} + 3$
$9(9^{k}) + 3$
$(8+1)\,9^{k} + 3$
$8(9^{k}) + 9^{k} + 3$
$8(9^{k})$ is divisible because 4 is a factor of 8.
$9^{k} + 3$ is true from assumption.
Conclusion: Since true for $n = 1$ and $n = k+1$ then true for all $n$.
Splitting the base: $9 = 8+1$, $7+2$, $6+3$, $5+4$. And $a^{p+q} = a^{p} \cdot a^{q}$.
Section 9 of 13
$5^{2n} - 3^{2n}$ is divisible by 8
Prove $5^{2n} - 3^{2n}$ divisible by 8.
$n = 1$:
$5^{2} - 3^{2}$
$25 - 9 = 16$
$n = k$:
$5^{2k} - 3^{2k}$ (assumption)
$n = k+1$:
$5^{2(k+1)} - 3^{2(k+1)}$
$5^{2k+2} - 3^{2k+2}$
$5^{2}(5^{2k}) - 3^{2}(3^{2k})$
$25(5^{2k}) - 9(3^{2k})$
$(16+9)(5^{2k}) - 9(3^{2k})$
$16(5^{2k}) + 9(5^{2k}) - 9(3^{2k})$
$16(5^{2k}) + 9(5^{2k} - 3^{2k})$
Or, splitting both: $(24+1)5^{2k} - (8+1)3^{2k}$
$24(5^{2k}) + 5^{2k} - 8(3^{2k}) - 3^{2k}$
Section 10 of 13
$n^{2} + 3n + 2$ is divisible by 2
Prove $n^{2} + 3n + 2$ is divisible by 2.
$n = 1$:
$1 + 3 + 2$
$n = k$:
$k^{2} + 3k + 2$ (assumption)
$n = k+1$:
$(k+1)^{2} + 3(k+1) + 2$
$k^{2} + 2k + 1 + 3k + 3 + 2$
$k^{2} + 3k + 2 + 2k + 4$
$k^{2} + 3k + 2$ ass
$2k + 4 = 2(k+2)$
Section 11 of 13
$n(n+1)(2n+1)$ is divisible by 6
Prove $n(n+1)(2n+1)$ is divisible by 6.
$n = 1$: ✓
$n = k$:
$k(k+1)(2k+1)$ is divisible by 6 (assumption)
$n = k+1$:
$(k+1)(k+2)(2k+3)$
$k(k+1)(2k+1)$
$k(\,2k^{2} + k + 2k + 1\,) = 2k^{3} + 3k^{2} + k$
$(k+1)(k+2)$
$(2k+3)(k^{2} + 3k + 2)$
$2k^{3} + 6k^{2} + 4k + 3k^{2} + 9k + 6$
$2k^{3} + 3k^{2} + k + 6k^{2} + 12k + 6$
$2k^{3} + 3k^{2} + k$ true ass
$6(k^{2} + 2k + 1)$ because of 6.
Section 12 of 13
$5^{n} - 4n + 3$ is divisible by 4
Prove $5^{n} - 4n + 3$ is divisible by 4.
$n = 1$
$n = k$:
$5^{k} - 4k + 3$ (assumption)
$n = k+1$:
$5^{k+1} - 4(k+1) + 3$
$5 \cdot 5^{k} - 4k - 4 + 3$
$(4+1)5^{k} - 4k - 4 + 3$
$4 \cdot 5^{k} + 5^{k} - 4k + 3 - 4$
$4 \cdot 5^{k} - 4$
$5^{k} - 4k + 3$
Section 13 of 13
$n^{3} + 6n^{2} + 8n$ is divisible by 3
Prove $n^{3} + 6n^{2} + 8n$ is divisible by 3.
$n = 1$:
$1 + 6 + 8 = 15$
$n = k$:
$k^{3} + 6k^{2} + 8k$ (assumption)
$n = k+1$:
$(k+1)^{3} + 6(k+1)^{2} + 8(k+1)$
$k^{3} + 3k^{2} + 3k + 1 + 6(k^{2} + 2k + 1) + 8k + 8$
$k^{3} + 3k^{2} + 3k + 1 + 6k^{2} + 12k + 6 + 8k + 8$
$k^{3} + 6k^{2} + 8k + 3k^{2} + 15k + 15$
$k^{3} + 6k^{2} + 8k + 3(k^{2} + 5k + 5)$
SUM
The lot in one box
The four steps
1.Prove for $n = 1$.
2.Assume for $n = k$.
3.Prove for $n = k+1$.
4.Conclusion: Since true for $n = 1$ and $n = k+1$ then true for all $n$.
5.Trick: split the base — $5 = 4+1$, $\;9 = 8+1$ — to pull out the divisor. And $a^{p+q} = a^{p} \cdot a^{q}$.
End of lesson
Induction — Divisibility · HL · Mathslive.ie