<s>[INST] Prove by induction that $4^n+5^n+6^n$ is divisible by $15$ for all odd $n\in \mathbb{N}$. 
Prove by induction that $4^n+5^n+6^n$ is divisible by $15$ for all odd $n\in \mathbb{N}$.

My proof :
I'm straight going to the induction hypothesis part.
Let for some odd $m(\gt2)\in \mathbb{N}, 15 | 4^m+5^m+6^m$.
Then, $$ 4^m+5^m+6^m = 15q$$ for some $q\in \mathbb{Z}$.
Now, $$4^m = 15q-5^m-6^m$$
Since $m$ is odd then the next odd number is $m+2$.
Now, $$ 4^{m+2} + 5^{m+2} + 6^{m+2} \\
= 4^m \cdot 16 + 5^m \cdot 25 + 6^m \cdot 36 \\
= (15q-5^m-6^m) \cdot 16 + 5^m \cdot 25 + 6^m \cdot 36 \\
= 15 \cdot 16q + 9 \cdot 5^m + 20 \cdot 6^m \\
= 15 \cdot 16q + 9 \cdot 5 \cdot 5^{m-1} + 20 \cdot 6 \cdot 6^{m-1} \\
= 15\big( 16q + 3 \cdot 5^{m-1} + 8 \cdot 6^{m-1} \big) \\
\\
\implies  15 | 4^{m+2} + 5^{m+2} + 6^{m+2} $$
Thus from induction the statement is true for every odd $n\in \mathbb{N}$
Is my proof correct?
 [/INST] If you know about linear recurrence: Let $f(n)=4^n+5^n+6^n,$ then you get the recurrence $$\begin{align} 
f(n+3)&=(4+5+6)f(n+2)-(4\cdot 5+4\cdot 6+5\cdot 6)f(n+1)+4\cdot 5\cdot 6 f(n)\\
&=15f(n+2)-74f(n+1)+240f(n)\\&\equiv f(n+1)\pmod{15}
\end{align} $$ So not only is $$f(2k+1)\equiv f(1)=15\equiv 0\pmod {15},$$ but $$f(2k)\equiv f(2)=77\equiv 2\pmod{15},$$ for $k\geq 1.$

If $a,b,c$ are integers, and $g(n)=a4^n+b5^n+c6^n,$ you will get the same congruence, $g(n+3)\equiv g(n+1)\pmod {15}.$

Even more generally, if $a,b,c,d$ are integers and $3\not\mid d,$ and $h(n)=a(d-1)^n+bd^n+c(d+1)^n,$ you also get:
$$h(n+3)\equiv h(n+1)\pmod {3d}$$
</s>