Proving $3^n + 4^n + 5^n$ is divisible by $12$ for all positive odd integers $n$ by induction I am trying to prove by induction that $\sum_{i=3}^{5} i^n$ is divisible by $12$ for all positive odd integers $n$. I heard that the solution might involve normal induction, where you assume that it works for the lowest positive odd number (in this case, $1$) and then try to deduce $P(n+2)$ for the next odd number.
I am not sure how to go about this, so any help would be greatly appreciated. I was thinking that if we define $n$ to be odd, then we could try to show that $n+2$ works using the fact that $n+2$ is also odd. However, I am not sure if this is the correct approach or how to proceed.
Could someone please help me with this problem?
Thank you!
 A: We set $n = 2k - 1$ and carry an induction over $k$. For the base case, $k = 1$, $n = 1$ and $3 + 4 + 5 = 12$, which is clearly divisible by 12.  Assume true for $k$, and consider the case for $k + 1$. We have.
\begin{align*}
3^{2k + 1} + 4^{2k + 1} + 5^{2k + 1} & = 9\cdot 3^{2k-1} + 16\cdot 4^{2k-1} + 25\cdot 5^{2k-1}\\
& = 8\cdot 3^{2k-1} + 15\cdot 4^{2k-1} + 24\cdot 5^{2k-1} + (3^{2k-1} +  4^{2k-1} + 5^{2k-1}).
\end{align*}
From our induction hypothesis, we know $3^{2k-1} +  4^{2k-1} + 5^{2k-1}  \equiv 0 \ \ \ (\text{ mod } 12 \ )$. Also, $8\cdot 3^{2k-1}$, $15\cdot 4^{2k-1}$ and $24\cdot 5^{2k-1}$ are all $\equiv 0 \ \ \ (\text{ mod } 12 \ )$ implying $3^{2k + 1} + 4^{2k + 1} + 5^{2k + 1}$ is divisible by 12.
A: Here is a stronger theorem which is easier to prove.
Suppose that we have $a + b + c \equiv 0 \mod 12$, with the criterion that $a$ is divisible by 3 and $b$ is divisible by 4. This is true for $a=3$, $b=4$, and $c=5$, for instance, but also many other things.
We then want to show that $9a + 16b + 25c \equiv 0 \mod 12$ as well. If $a, b,$ and $c$ are odd powers $3, 4,$ and $5$, then these would be the next odd powers, but we've left it open for $a, b, $ and $c$ to be anything such that they sum to $0 \mod 12$ and with $a$ divisible by $3$ and $b$ divisible by $4$.
Then via elementary algebra $\mod 12$, we can show the following:
$$
9a + 16b + 25c \mod 12 \\
= 9a + 4b + c \mod 12 \\
$$
Now, since $a + b + c \equiv 0 \mod 12$, we can subtract $a + b + c$ from the above to get
$$
8a + 3b \mod 12
$$
But now we are done, because we know that $a$ is divisible by $3$ and $b$ is divisible by $4$. If we make the variable substitution that $a = 3a'$ and $b = 4b'$, we get
$$
8\cdot 3a' + 3 \cdot 4b' \mod 12 \\
= 24 a' + 12 b' \mod 12 \\
= 0 a' + 0 b' \mod 12 \\
= 0 \mod 12
$$
So we have proven that for any $a, b, c$ which sum to $0$ mod 12 and for which $a$ and $b$ are divisible by 3 and 4, respectively, that we also have $9a + 16b + 25c \equiv \mod 12$.
Since $a, b, c = 3, 4, 5$ is the base case which fits these criteria, and we know that $9a + 16b + 25c$ also fits these criteria - which are also the next odd powers of $3, 4$ and $5$, we thus have that every sum of odd powers of $3, 4$ and $5$ fits these criteria.
But we also have that this is true for other triples of numbers satisfying the original properties. For instance, we have $a = 15, b = 8, c = 1$ sum to $0 \mod 12$, and so do $9\cdot 15, 16 \cdot 8, $ and $25 \cdot 1$. Anyway, that proves the theorem.
A: The base case is easy enough, so we can try to rewrite $P(n+2)$ as you suggest. Assuming $P(n)$ we have
$$3^{n+2}+4^{n+2}+5^{n+2} = 25(3^n +4^n +5^n) -  12(4\cdot 3^{n-1} + 3\cdot 4^{n-1})$$
By the inductive hypothesis the term on the left is a multiple of $12$ so the entire expression must be a multiple of $12$.
A: Proof 1 with Induction :
We know $X=3^{1}+4^{1}+5^{1}=12$ is Divisible by $12=3 \times 4$.
Let $Y=3^{n}+4^{n}+5^{n}$ be Divisible by $12$.
Let $Z=3^{n+2}+4^{n+2}+5^{n+2}$ , where we want to check Divisibility by $12$ , starting with $3$.
$Z=3^{2} \times 3^{n}+4^{2} \times 4^{n}+5^{2} \times 5^{n}$
$Z=9 \times 3^{n}+16 \times 4^{n}+25 \times 5^{n}$
$Z=(8+1) \times 3^{n}+(15+1) \times 4^{n}+(24+1) \times 5^{n}$
$Z=(8+1) \times 3^{n}+(15+1) \times 4^{n}+(24+1) \times 5^{n} = 3^{n}+4^{n}+5^{n}+3c=Y+3c$ , which must be Divisible by $3$
Continuing with $Z=3^{n+2}+4^{n+2}+5^{n+2}$ , where we want to check Divisibility by $12$ , which contains $4$.
$Z=3^{2} \times 3^{n}+4^{2} \times 4^{n}+5^{2} \times 5^{n}$
$Z=9 \times 3^{n}+16 \times 4^{n}+25 \times 5^{n}$
$Z=(8+1) \times 3^{n}+(15+1) \times 4^{n}+(24+1) \times 5^{n}$
$Z=(8+1) \times 3^{n}+(15+1) \times 4^{n}+(24+1) \times 5^{n} = 3^{n}+4^{n}+5^{n}+4k=Y+4k$ , which must be Divisible by $4$
Hence overall, $Z$ must be Divisible by $3 \times 4 = 12$.
With $X$ , $Y$ & $Z$ being Divisible by $12$ , we can see that the Induction Proof works here.
More generally , we can see that $(W-1,W,W+1)$ with $W$ a multiple of $4$ will have that Property.
With $W=4$ we get $(3,4,5)$ here.
With $W=8$ we get $(7,8,9)$ which will have that Property.
Proof 2 without Induction :
$(W-1)^n+(W)^n+(W+1)^n$ has 3 consecutive numbers where we must have a multiple of $3$ , the others must have "1 less than a multiple of $3$" & "1 more than a multiple of $3$".
Evaluating each Power will give terms with multiples of $3$ except the last terms which will be $(-1)^{ODD}$ & $(+1)^{ODD}$ which will give $-1+1=0$ hence the whole must be Divisible by $3$.
$(W-1)^n+(W)^n+(W+1)^n$ with $W=4w$ gives :
$(4w-1)^n+(4w)^n+(4w+1)^n$ with $W=4w$
When we evaluate each Power , we will get multiples of $4$ throughout , except for the last terms which will be $(-1)^{ODD}$ & $(+1)^{ODD}$ which will give $-1+1=0$ , hence the whole will be Divisible by 4.
In general , the whole must be Divisible by $3 \times 4 = 12$
In Particular , $W=4$ gives $3^n+4^4+5^n$ Divisible by $12$ when $n$ is ODD.
