Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $P(n) = 2^n + 3^n - 5^n $.

I want to prove that $P(n)$ is true 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|improve this question
1  
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
add comment

3 Answers

up vote 4 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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.