Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 6 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.