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?
 A: Hint
Like Prove that $3^{2n-1} + 2^{n+1}$ is divisible by $7$ for all values of $n$
If $f(m)=4^{2m+1}+5^{2m+1}+6^{2m+1},$
$$f(n+1)-4^2f(n)=5^{2n+1}(5^2-4^2)+6^{2n+1}(6^2-4^2)$$ will be clearly divisible by $15$ if $n\ge0$
So, if $15$ divides $f(n),15$ will divide $f(n+1)$
Now establish the base case i.e., $m=0$
A: You could go mod $3$ and mod $5$ and conclude, an alternate proof is by induction : of course $4^n + 5^n + 6^n$ is divisible by $15$ when $n=1$. However, note that if $n \geq 3$:
$$
4^n + 5^n + 6^n - 4^{n-2} - 5^{n-2} - 6^{n-2} \\=\color{blue}{(4^n - 4^{n-2})} + \color{green}{(5^n - 5^{n-2})} + \color{red}{(6^n - 6^{n-2})} \\= \color{blue}{15(4^{n-2})} +\color{green}{ 15(8 \times 5^{n-3})} + \color{red}{ 15(14 \times 6^{n-3})}
$$
where terms of same colour are equal by factorization. Thus, the claim follows since the sum of two multiples of $15$ is also a multiple of $15$.
A: Hint for proof by induction:
$4^{2k+1}+5^{2k+1}+6^{2k+1}=16(4^{2k-1}+5^{2k-1}+6^{2k-1})+9\times5^{2k-1}+20\times6^{2k-1}$

As I said in a comment to the question, it's easy to prove with modular arithmetic, 
because mod $3$ it's $1+(-1)+0$, and mod $5$ it's $(-1)+0+1$.
A: 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?
A: $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

By factoring one more power out...
$4^{2k+1}+5^{2k+1}+6^{2k+1}=(4)4^{2k}+(5)5^{2k}+(6)6^{2k}=(16)4^{2k-1} + (25)5^{2k-1} + (36)5^{2k-1}$
So this is $[16(4^{2k-1} + 5^{2k-1}+6^{2k-1})] + 9*5^{2k-1} + 20*6^{2k-1}$.
And it's easy to finish:
$=[16*15N] + 3*15*5^{2k-2} + 4*15*2*6^{2k-2}$.
====
But if you know modulo arithmetic this is CUTE!
$4^{n} + 5^n + 6^n = (3+1)^n + (6-1)^n + 6^n \equiv 1^n+(-1)^n + 0^n \equiv 0 \pmod 3$ so $3|4^n + 5^n +6^n$.
And $4^n + 5^n + 6^n = (5-1)^n + 5^n + (5+1)^n\equiv (-1)^n + 0^n + 1^n \equiv 0 \pmod 5$ so $5|4^n + 5^n +6^n$.
So $15|4^n + 5^n +6^n$.
....
If you don't know modulo arithmetic the you can use binomial theorem.
$4^n + 5^n + 6^n =(5-1)^n + 5^n + (5+1)^n =$
$(5^n - n*5^{n-1}+ C_{n,2} 5^{n-2} -..... +n*5 - 1) + 5^n +(5^n - n*5^{n-1}+ C_{n,2} 5^{n-2} -..... -n*5 + 1)=$
$(5^n - n*5^{n-1}+ C_{n,2} 5^{n-2} -..... +n*5) + 5^n +(5^n - n*5^{n-1}+ C_{n,2} 5^{n-2} -..... -n*5)$
Which is divisible by $5$.
Do the same for $4^n + 5^n + 6^n = (3+1)^n + (6-1)^n + 6^n$ to show it is divisible by $3$.
A: Hint :
\begin{eqnarray*}
31(4^n+5^n+6^n)= 4^{n+2}+5^{n+2}+6^{n+2} +15 \times 4^n+ 6 \times 5^n - 5 \times 6^n. 
\end{eqnarray*}
