# Math Help - Divisible by 9

1. ## Divisible by 9

Using mathematical induction, prove

$10^n + 3\cdot4^{n+2} + 5$ is div. by $9$ $\forall \ \mathbb{Z} \ \ n \geq 1$

2. Originally Posted by Ideasman
Using mathematical induction, prove

$10^n + 3\cdot4^{n+2} + 5$ is div. by $9$ $\forall \ \mathbb{Z} \ \ n \geq 1$
okie dokie, let's see where we get with this. i suppose you know the method of induction, so i won't explain it. let's just jump in

Let $P(n)$: " $9|(10^n + 3 \cdot 4^{n + 2} + 5)$ for all $n \in \mathbb{N}$"

Clearly $P(1)$ is true, since $10 + 3 \cdot 4^3 + 5 = 207 = 9(23)$

So assume $P(n)$ holds for some $n \ge 1$. That is, we can write $P(n) = 9k$ for some $k \in \mathbb{Z}$. We show $P(n + 1)$

Now $P(n + 1)$ is $10^{n + 1} + 3 \cdot 4^{n + 3} + 5$. We must show that this is divisible by 9, provided $P(n)$ is.

Note that:

$10^{n + 1} + 3 \cdot 4^{n + 3} + 5 = 10^{n + 1} ~\underbrace{+ 10 \cdot 3 \cdot 4^{n + 2} + 10 \cdot 5 - 10 \cdot 3 \cdot 4^{n + 2} - 10 \cdot 5}_{\mbox{Note that this is zero}}~+ 3 \cdot 4^{n + 3} + 5$

$= 10( \underbrace{10^n + 3 \cdot 4^{n + 2} + 5}_{\mbox{This is } P(n)}) - 18 \cdot 4^{n + 2} - 45$

$= 10 \cdot 9k - 9(2 \cdot 4^{n + 2} + 5)$

$= 9(10k - 2 \cdot 4^{n + 2} - 5)$

Since $(10k - 2 \cdot 4^{n + 2} - 5)$ is an integer, we have that $9 | P(n + 1)$, as desired.

Thus, $P(n)$ holds for all $n \in \mathbb{N}$ by induction.

QED

3. Hello, Ideasman!

Another approach . . .

Using mathematical induction, prove:

. . $10^n + 3\cdot4^{n+2} + 5$ is divisible by $9,\quad \forall\:n \in \mathbb{N}$
Verify $S(1)\!:\;\;10 + 3\!\cdot\!4^3 + 5 \:=\:207 \:=\:9(23)$ . . . true!

Assume $S(k)$ is true: . $10^k + 3\!\cdot\!4^{k+2} + 5 \;=\;9a\;\text{ for some integer }a$

Add $9\!\cdot\!10^k + 9\!\cdot\!4^{k+2}$ to both sides:

. . $10^k \:{\color{blue}+\: 9\!\cdot\!10^k} + 3\!\cdot\!4^{k+2} \:{\color{blue}+\: 9\!\cdot\!4^{k+2}} + 5 \;=\;9a \:{\color{blue}+ \:9\!\cdot\!10^k + 9\!\cdot\!4^{k+2}}$

. . . . $10^k(1 + 9) + 3\!\cdot\!4^{k+2}(1 + 3) + 5 \;=\;9\underbrace{(a + 10^k + 4^{k+2})}_{\text{some integer }b}$
. . . . . . . . . . . $10^{k+1} + 3\!\cdot\!4^{k+3} + 5 \;=\;9b$

We have proved $S(k\!+\!1)$ . . . The inductive proof is complete.