# Thread: Divisible by 9

1. ## Divisible by 9

Using mathematical induction, prove

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

2. Originally Posted by Ideasman
Using mathematical induction, prove

$\displaystyle 10^n + 3\cdot4^{n+2} + 5$ is div. by $\displaystyle 9$ $\displaystyle \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 $\displaystyle P(n)$: "$\displaystyle 9|(10^n + 3 \cdot 4^{n + 2} + 5)$ for all $\displaystyle n \in \mathbb{N}$"

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

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

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

Note that:

$\displaystyle 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$

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

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

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

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

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

QED

3. Hello, Ideasman!

Another approach . . .

Using mathematical induction, prove:

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

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

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

. . $\displaystyle 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}}$

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

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