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…
Best Answer
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.