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?
 A: 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}$$
A: Just a small detail. You proved the induction step $P(m) \implies P(m+2)$ with the hypothesis $m$ odd, $m>2$. If you prove the induction base $m=1$, your proof will be, strictly speaking, incomplete. Because you would have proved

*

*$P(1)$

*$P(m) \implies P(m+2)$ for odd $m > 2$
which translate in proving:

*

*$P(1)$

*$P(3) \implies P(5)$

*$P(5) \implies P(7)$

*...

As you see, you would had missed a link in the chain of implications: $P(1) \implies P(3)$.
You should drop the constraint $m>2$ (that you actually didn't use in your proof).
If you had proved $P(m-2) \implies P(m)$ then the constraint $m > 2$ would be necessary.
A: Alternatively, let $f(n)=4^n+5^n+6^n$. Then
$$
f(n+2)-f(n)=15 \cdot 4^n + 24 \cdot 5^n + 35 \cdot 6^n = 15 \cdot 4^n + 15 \cdot 8 \cdot 5^{n-1} + 15 \cdot 14 \cdot 6^{n-1}
$$
So if $15$ divides $f(n)$, then $15$ divides $f(n+2)$. Note that $n+2$ is the next odd number if $n$ is odd.
