# 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...

-
That coefficient 6 is wrong. – Gerry Myerson Nov 4 '11 at 3:08
Before any proceeding I would put aside any of that powers of 3 which are obviously irrelevant for the answer of the question, and then only look at $\small 5^k - 2^k = (5-2) \cdot x_{k}$ resp $\small 5^{k+1} - 2^{k+1} = (5-2) \cdot x_{k+1}$ to make the induction... – Gottfried Helms Nov 4 '11 at 7:26

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.

-
Thanks, that clears up a lot, but I'm having trouble understanding how you knew to write 2 as (3-1), 3 as (4-1), and 5 as (6-1).. I can see how that works out now with each term being a factor of 3, but without seeing it first I would have never guessed it on my own.. – mathemagician11 Nov 4 '11 at 3:20
Let's try to make your method work: $P(k+1) - P(k) = 2^k + 2.3^k - 4.5^k = 2( 2^{k-1} + 3^{k} - 2.5^k) = 2((2^{k-1} + 3^{k-1} - 5^{k-1}) + (2.3^{k-1} - 9.5^{k-1}))$. Do you see how to make this work now, if you use strong induction? – Rankeya Nov 4 '11 at 3:31
As Gerry said you got your coefficient 6 wrong. That really was what threw you off guard I think. So, if you are uncomfortable with my answer, then you were on the right track. – Rankeya Nov 4 '11 at 3:41

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$.

-

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.

-

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$.

-