Prove $4^n+5^n+6^n$ is divisible by 15

Question

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 1

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?

Answer 2

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$

Answer 3

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*}

Answer 4

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$.

Answer 5

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$.

Answer 6

$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$.