For all natural numbers of $n$, prove by induction that $15 \mid (4^{2n+1} + 5^{2n+1} + 6^{2n+1})$.

Question

What I have so far:

We will prove by induction. Our induction predicate $P(n)$ is $15 \mid (4^{2n+1} + 5^{2n+1} + 6^{2n+1})$.

Base Case: $n = 0$: $P(0)$ is $15 \mid (4^{2(0)+1}+5^{2(0)+1}+6^{2(0)+1})$. $4+5+6 = 15$, so $P(0)$ is true.

Inductive Step: $n \geq 0$: Let the natural number of $n$ be arbitrary and assume $P(n)$ is true. Now we show $P(n+1)$ is true, where $P(n+1)$ is $15 \mid (4^{2(n+1)+1} + 5^{2(n+1)+1} + 6^{2(n+1)+1})$. $4^{2(n+1)+1} + 5^{2(n+1)+1} + 6^{2(n+1)+1} = 4^{2n+3} + 5^{2n+3} + 6^{2n+3}$.

That's all I have. I am unable to finish

Answer 1

Say $4^{2k+1} + 5^{2k+1} + 6^{2k+1} \equiv 0 \pmod {15}$ (1)

Let $4^{2(k+1)+1} + 5^{2(k+1)+1} + 6^{2(k+1)+1} \equiv x \pmod {15}$

Then $4^{2k+3} + 5^{2k+3} + 6^{2k+3} \equiv x \pmod {15}$

$16*4^{2k+1} + 25*5^{2k+1} + 36*6^{2k+1} \equiv x \pmod {15}$

$4^{2k+1} + 10*5^{2k+1} + 6*6^{2k+1} \equiv x \pmod {15}$ (2)

subtract (1) from (2) to get

$9*5^{2k+1} + 5*6^{2k+1} \equiv x \pmod {15}$, and since $9*5^{2k+1}$ has a factor of both $3$ and $5$, it makes $15$ a factor of $9*5^{2k+1}$, and this is also true for $5*6^{2k+1}$ , meaning $x=0$.

I doubt this is the most efficient solution but it is one.

Answer 2

You want to try to express $4^{2n+3}+ 5^{2n+3} + 6^{2n+3}$ in terms of $4^{2n+1}+ 5^{2n+1} + 6^{2n+1}$ so that you can bring in the induction hypothesis. One way is convert the indices back to $2n+1$: \begin{align} 4^{2n+3}+ 5^{2n+3} + 6^{2n+3} &= 16\times4^{2n+1}+ 25\times5^{2n+1} + 36 \times 6^{2n+1} \\ &= 16(4^{2n+1}+ 5^{2n+1} + 6^{2n+1}) + 9 \times 5^{2n+1} + 20 \times 6^{2n+1} \end{align} The first term is divisible by $15$ by the induction hypothesis, the second and third term are both divisible by $15$, so you are done.

Answer 3

There are already answers that use induction, so I will provide another answer using modular arithmetic.

First of all looking at the expression modulo $3$ we have $$4^{2n+1} + 5^{2n+1} + 6^{2n+1} \equiv 1^{2n+1} + (-1)^{2n+1} + 0^{2n+1} \equiv 1 - 1 + 0 \equiv 0\pmod 3$$

Then looking at the expression modulo $5$ we have $$4^{2n+1} + 5^{2n+1} + 6^{2n+1} \equiv (-1)^{2n+1} + 0^{2n+1} + 1^{2n+1} \equiv -1 + 0 + 1 \equiv 0\pmod 5$$

This shows that the expression is divisible by both $3$ and $5$, so it is also divisible by $15$.