1. ## divide by 3?

hi folks,

I hope this is the right place to post this! I have no idea how to proceeed with the following question:

Show that for all positive integral values of n

[HTML]7 <sup>n</sup> + 2 <sup>2n+1</sup>[/HTML]

is divisible by 3.

I tried a few terms as follows:

n = 1. 7 ^ 1 + 2 ^ 3 = 7 + 8 = 15
n = 2. 7
^ 2 + 2 ^ 5 = 49 + 32 = 81
n = 3. 7
^ 3 + 2 ^ 7 = 343 + 128 = 471

and these are all divisible by 3 but how do I handle the general case?

I thought of expanding the expression i.e.

2.2 ^ n. 2 ^ n - (1 - 8) ^ n

and using a binomial on the second term but it doesn't get me anywhere. I guess I am trying to calculate the sum of a series and show that it has a factor of 3 but I can't see how to do it. Any ideas?

regards and thanks
Simon

p.s. sorry about the formating. the HTML stuff doesn't seem to come out so I resorted to the ^ symbol which is pretty unpretty!

2. Hi,
Originally Posted by s_ingram

I thought of expanding the expression i.e.

2.2 ^ n. 2 ^ n - (1 - 8) ^ n

and using a binomial on the second term but it doesn't get me anywhere. I guess I am trying to calculate the sum of a series and show that it has a factor of 3 but I can't see how to do it. Any ideas?
I suggest writing $7^n+2^{2n+1}=(2^2+3)^n+2^{2n+1}$ and then using the binomial theorem to expand $(2^2+3)^n$.

Originally Posted by s_ingram
p.s. sorry about the formating. the HTML stuff doesn't seem to come out so I resorted to the ^ symbol which is pretty unpretty!
To enter math. equations you can use LaTeX. (see http://www.mathhelpforum.com/math-help/latex-help/)

3. $(2^{2}+3)^{n} = 2^{2n} + \binom{n}{1}2^{2(n-1)}3^{1} + ... + \binom{n}{k}2^{2(n-k)}3^{k} + ... + 3^{n} =$

$= 2^{2n} + 3[\binom{n}{1}2^{2(n-1)} + ... + \binom{n}{k}2^{2(n-k)}3^{k-1} + ... + 3^{n-1}]$

So we can write:

$3[\binom{n}{1}2^{2(n-1)} + ... + \binom{n}{k}2^{2(n-k)}3^{k-1} + ... + 3^{n-1}] + 2^{2n}(1+2) =$ $3[\binom{n}{1}2^{2(n-1)} + ... + \binom{n}{k}2^{2(n-k)}3^{k-1} + ... + 3^{n-1}] + 2^{2n}(3)$

Now factor out a 3 from both terms.

$3[(\binom{n}{1}2^{2(n-1)} + ... + \binom{n}{k}2^{2(n-k)}3^{k-1} + ... + 3^{n-1}) + 2^{2n} ]$

And because we have a number times 3, the result is divisible by 3.

Note: If there aint a careless mistake somewhere in this mess, I am surprised.

4. thanks to Twig and flyingsquirrel. You guys make it look so easy!

5. If you do it by induction here is the last step.
$\begin{array}{rcl}
{7^{n + 1} + 2^{2n + 3} } & = & {7^{n + 1} + 7 \cdot 2^{2n + 1} - 7 \cdot 2^{2n + 1} + 2^{2n + 3} } \\
{} & {} & {7\left( {7^n + 2^{2n + 1} } \right) - 2^{2n + 1} \left( {7 - 2^2 } \right)} \\
{} & {} & {7\left( {7^n + 2^{2n + 1} } \right) - 2^{2n + 1} \left( 3 \right)} \\ \end{array}$

6. Hello, s_ingram!

Show that for any positive integer $n \!:\;\;7^n + 2^{2n+1}$ is divisible by 3.

Verify $S(1)\!:\;\;7^1 + 2^3 \:=\:7+8 \:=\:15$ ...
divisible by 3.

Assume $S(k)\!:\;\;7^k + 2^{2k+1} \:=\:3a\;\text{ for some integer }a.$

Add $6\!\cdot\!7^k + 3\!\cdot\!2^{2k+1}$ to both sides:

. . $7^k + {\color{blue}6\!\cdot\!7^k} + 2^{2k+1} + {\color{blue}3\!\cdot\!2^{2k+1}} \;=\;3a + {\color{blue}6\!\cdot\!7^k + 3\!\cdot\!2^{2k+1}}$

. . $(1 + 6)\!\cdot\!7^k + (1 + 3)\!\cdot\!2^{2k+1} \;=\;3\left(2a + 2\!\cdot\!7^k + 2^{2k+1}\right)$ .
a multiple of 3

. . . . . . . . $7\!\cdot\!7^k + 2^2\!\cdot2^{2k+1} \;=\;3b\;\;\text{ for some integer }b$

Therefore: . . $7^{k+1} + 2^{2k+3} \;=\;3b$

We have proved $S(k+1).$
. . The inductive proof is complete.

7. Hi Soroban, now that is a smart proof. Too smart! How did you think adding those two terms? Once you see them it all fits but finding them is the real trick! I have never really been impressed with proofs by induction, but I am now! Usually I just try to add the next term in the series and ensure that it has a corresponding impact on the expression fo the sum but with 7 sup k+1 + 2 sup 2k+1 I couldn't even imagine what the next term would be!

8. Or you can just note that

$7^n\equiv 1^n \equiv 1 \mod 3$,

$2^{2n+1} \equiv (-1)^{2n+1} \equiv -1 \mod 3$,

so that $7^n+2^{2n+1} \equiv 0 \mod 3$.

9. Originally Posted by s_ingram
Hi Soroban, now that is a smart proof. Too smart! How did you think adding those two terms? Once you see them it all fits but finding them is the real trick! I have never really been impressed with proofs by induction, but I am now! Usually I just try to add the next term in the series and ensure that it has a corresponding impact on the expression fo the sum but with 7 sup k+1 + 2 sup 2k+1 I couldn't even imagine what the next term would be!
Hi

$7^{n+1} + 2^{2n+3} = 7(7^{n} + 2^{2n+1})-7 \cdot 2^{2n+1} + 2^{2n+3} = 7 \cdot 3a + 2^{2n+1}(-7+2^2) = 7 \cdot 3a -3 \cdot 2^{2n+1}$

Therefore
$7^{n+1} + 2^{2n+3} = 3(7a-2^{2n+1})$