<s>[INST] 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$.
 [/INST] 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)$.
</s>