Prove by induction: $10^n+3\times4^{n+2}+5$ is divisible by $9$ I dealt with this problem but I couldn't resolve.
Prove by induction that $10^n+3\times4^{n+2}+5$ is divisible by $9$ for all non-negative integers $n$.
 A: Let P(n) be the statement that $10^n+3\times 4^{n+2}+5$ is divisible by $9$. When $n=0$, $10^n+3\times 4^{n+2}+5=54$ is divisible by $9$, so we have $P(0)$.
Suppose we have $P(k)$ for some nonnegative integer $k$. Then $10^k+3\times 4^{k+2}+5$ is divisible by $9$. Now
$(10^{k+1}+3\times 4^{k+3}+5)-(10^k+3\times 4^{k+2}+5)$
$=10^{k+1}-10^k+3\times (4^{k+3}-4^{k+2})$
$=9\times 10^k+9\times 4^{k+2}$
is divisible by $9$. It follows that $10^{k+1}+3\times 4^{k+3}+5$ is divisble by $9$, and we have $P(k+1)$.
A: Base case ($n=0$): $10^0 + 3 (4^2)+5 = 54$ is divisible by 9.
Inductive step: Suppose $10^n + 3(4^{n+2})+5$ is divisible by 9. Can you show $10^{n+1} + 3(4^{n+3})+5$ is divisible by 9 as well? Hint: take the difference.
A: Hint $\ \  \color{#c00}9\mid 10^n\color{#c00}{(10\!-\!1)}+ \color{#c00}{3\, (4\!-\!1)}\, 4^{n+2}\!= \color{#0a0}{f_{n+1}\!-\!f_n}\ \,$ so $\,\ 9\mid \color{purple}{f_n}\,\Rightarrow\ 9\mid \color{#0a0}{f_{n+1}\!-\!f_n} +\color{purple}{f_n} = f_{n+1}$
Remark $\ $ The same simple method handles many inductions - see prior answers on telescopy.
A: Hint:
$$10^{n+1}+3\cdot4^{n+3}+5 = 9\cdot10^n+10^n + 3\cdot\left(3\cdot4^{n+2}+4^{n+2}\right)+5$$
