elementary number theory - Prove $4^n+5^n+6^n$ is divisible by 15

Prove by induction:

$4^n+5^n+6^n$ is divisible by 15 for positive odd integers

For $n=2k-1,n≥1$ (odd integer)

$4^{2k-1}+5^{2k-1}+6^{2k-1}=15N$

To prove $n=2k+1$, (consecutive odd integer)

$4^{2k+1}+5^{2k+1}+6^{2k+1}=(4)4^{2k}+(5)5^{2k}+(6)6^{2k}$,

How do I substitute the statement where $n=2k-1$ to the above, to factor out 15 in order to prove divisibility? Would it be easier to assume $n=k$ is odd and prove $n=k+2$ is divisible by 15?

Answer

As you suggested, it's notationally simpler to suppose $4^k+5^k+6^k$ is divisible by $15$ and consider

$$4^{k+2}+5^{k+2}+6^{k+2} = 16\cdot 4^k + 25\cdot 5^k + 36\cdot 6^k.$$
Subtracting the original expression, we get $15\cdot 4^k + 24\cdot 5^k + 35\cdot 6^k$. The first term is divisible by $15$. Now note that
$$24\cdot 5^k +35\cdot 6^k = 15\cdot 8\cdot 5^{k-1} + 15\cdot 14\cdot 6^{k-1}$$
is likewise divisible by $15$. Thus, $4^{k+2}+5^{k+2}+6^{k+2}$ is indeed divisible by $15$.

Query: Where did we use that $k$ is odd? Well, obviously to start the induction. But where else?