Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$ Let $P(n) =
2^n + 3^n - 5^n
$.
I want to prove that $P(n)$ is divisible by $3$ for all integers $n\geq 1$.
The basis step for this proof is easy enough: $P(1)$ is divisible by $3$.
For the inductive step, I let $k$ be an arbitrary integer, then assume $P(k)$ is divisible by $3$, and set out to prove that $P(k+1)$ is divisible by $3$.
$$
P(k) = 2^k + 3^k - 5^k
$$
$$\begin{align*}
P(k + 1) &= 2^{k+1} + 3^{k+1} - 5^{k+1}\\
 &= 2*2^k + 3*3^k - 5*5^k
\end{align*}
$$
I'm guessing that the best way to do this is to prove $P(k+1) - P(k)$ is divisible by $3$, but I'm not sure on that so this could be where I start to approach this wrong.. I'm not sure what else to try though.. $P(k+1) * P(k)$?  But that wouldn't distribute very well would it?
So what I did is write out P(k+1) - P(k):
$$
P(k+1) - P(k) = 2^k + 2*3^k - 6*5^k
$$
At this point, I know that the second and third terms are divisible by 3, but I know that $2^k$ is not necessarily divisible by 3, so here I am stuck...
 A: So note that $2^{k+1} + 3^{k+1} -5^{k+1} = (3-1)2^k + (4-1)3^k -(6-1).5^k = (3.2^k + 4.3^k -6.5^k) - (2^k + 3^k - 5^k)$. The rest should be clear.
A: As an alternative to Rankeya's answer, you have:
$$P(k+1) = 2^{k+1} + 3^{k+1} - 5^{k+1}.$$
Then, proceeding as you do, we have:
$$P(k+1) = 2\cdot 2^k + 3\cdot 3^k - 5\cdot 5^k.$$
At this point, you want to use your induction hypothesis. Notice that you have enough $2^k$s, $3^k$s and $5^k$s for two $2^k+3^k-5^k$, with some stuff left over. That is:
$$P(k+1) = 2(2^k + 3^k - 5^k) + 3^k - 3\cdot 5^k.$$
But $3^k$ is of course a multiple of $3$, and $3\cdot 5^k$ is a multiple of $3$. And $2(2^k+3^k-5^k)$ is a multiple of $3$ by the induction hypothesis. So $P(k+1)$ is a sum of multiples of $3$, hence is a multiple of $3$.
A: An outline of another method, if you are willing to use moduli.  Note that $P(1) = 2 + 0 - 2 \mod{3}~~$
For the induction hypothesis, see that :
$2^k = 5^k = 2 \mod{3} \implies2^{k+1} = 5^{k+1} = 1 \mod{3}$
 $2^{k} = 5^{k} = 1 \mod{3} \implies2^{k+1} = 5^{k+1} = 2 \mod{3}$
Although, if you can use modular arithmetic, its easy enough to prove directly.
A: Another approach:
$$2^n - 5^n = (2 - 5)\cdot (2^{n-1} + 2^{n-2} \cdot 5 + \cdots + 2^{n - j - 1}5^j + \cdots + 5^{n - 1})$$
This is the difference of nth powers formula, which you can prove by induction if you like.
Then it's clear that $2^n - 5^n$ is divisible by $2 - 5 = -3$, so divisible by $3$. Therefore $2^n + 3^n - 5^n$ is also divisible by $3$.
