<s>[INST] 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...
 [/INST] 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$.
</s>