<s>[INST] Show that $\displaystyle{\frac{1}{9}(10^n+3 \cdot 4^n + 5)}$ is an integer for all $n \geq 1$ Show that $\displaystyle{\frac{1}{9}(10^n+3 \cdot 4^n + 5)}$ is an integer for all $n \geq 1$
Use proof by induction. I tried for $n=1$ and got $\frac{27}{9}=3$, but if I assume for $n$ and show it for $n+1$, I don't know what method to use. 
 [/INST] You don't need to use induction here. Just reduce everything modulo 9:  
$10 \equiv 1 \mod 9$, so $10^n \equiv 1 \mod 9$, so $10^n+5 \equiv 6 \mod 9$.  
To find the possible values of $4^n \mod 9$, note that $4^3 \equiv 1 \mod 9$, so $4^n$ must be $1, 4,$ or $7 \mod 9$. Thus $3 \cdot 4^n$ is equal to $3 \mod 9$.  
Hence $10^n + 3 \cdot 4^m + 5 \equiv 0 \mod 9$ for any positive integers $m, n$, not only when $n = m$.
</s>