6
$\begingroup$

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

  • 0
    $(2+3)^n=2^n+n.2^{n-1}.3+\cdots+n.2.3^{n-1}+3^n$ Hence for $n\ge2,$ $6|(5^n-2^n-3^n).$2017-08-28

4 Answers 4

6

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.

  • 0
    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.2011-11-04
6

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

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.

2

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