# Exponential problem

1. Jun 13, 2005

### quentinchin

hey guy help me to prove this question:

3^(2n+1) + 2^(n+2) is dividable by 7.

2. Jun 13, 2005

### Zurtex

What have you tried so far? And if nothing, may I suggest you try it with induction.

3. Jun 13, 2005

### quentinchin

Can u prove it ?

4. Jun 13, 2005

### LittleWolf

3^(2n+1)+2^(n+2)=3*9^n+4*2^n. To be divisible by 7, you must prove
(9^n mod 7) =(2^n mod 7).

5. Jun 13, 2005

### Zurtex

Yes (assuming it's true), but this forum isn't about doing your work for you. It's just about helping.

6. Jun 13, 2005

### quentinchin

sorry? can you clarify (9^n mod 7) =(2^n mod 7) and finish it?

7. Jun 13, 2005

### Zurtex

I'm a bit dubious about the logical jump there.

8. Jun 13, 2005

### shmoe

It's fine, you could then collect the common 2^n terms working mod 7, etc., but if you're already familiar with modular aritmetic, there shouldn't be much to prove.

It appears the quentinchin isn't familiar with modular arithmetic yet, so I offer the following hint: 9^n=(7+2)^n

9. Jun 13, 2005

### Zurtex

Well whether or not it's fine, as you mention it would appear that quentinchin doesn't appear too familiar with modular arithmetic. Which is why I suggested just a simple proof by induction at the start of the thread.

10. Jun 13, 2005

### shmoe

Which he seemed to ignore (sigh) so I offered another suggestion. Here's hoping he actually gives either way a try and posts his efforts.

11. Jun 13, 2005

### quentinchin

hehe i found it but a bit complex.
3^(2n+1) + 2^(n+2)
= 3(9^n) + 4(2^n)
= 3(9^n) - 3(2^n) + 7(2^n)
= 3(9-2)[9^(n-1) + 9^(n-2)*2 + ... + 9*2^(n-2) + 2^(n-1)] + 7(2^n)
= 7[3(9^(n-1) + 9^(n-2)*2 + ... + 9*2^(n-2) + 2^(n-1) + 2^n]
hence the equation 3^(2n+1) + 2^(n+2) is dividable by 7.

12. Jun 13, 2005

### quentinchin

shame to tell that i still do not understand what is modular arithmetic and induction.
Can give me an example?

13. Jun 13, 2005

### Zurtex

It may be because I'm very tired, but I don't see how you made that step.

Anyway, proof by induction. First of all you prove it for n = 1, then assuming it's true for n = k you prove it for n = k + 1. That proves it for all natural numbers.

Here is a nice page on it: http://en.wikipedia.org/wiki/Mathematical_induction

Really good for this exact sort of problem.

14. Jun 13, 2005

### quentinchin

I really appreciate it, but do you guys overlook the question? The question is to <PROVE> that 3^(2n+1) + 2^(n+2) is divisible by 7 but not using induction method.

15. Jun 13, 2005

### Zurtex

No, proof by induction here is clearly the easiest way to prove it. Even if you use some other method to reduce the problem, induction is probably the easiest way to prove what you have.

If you prove it for n = 1, i.e:

33 + 23 = 35

Then assume it's true for n = k, i.e:

32k + 1 + 2k + 2 = 7a (for some integer a)

With the above prove it for n = k + 1, i.e:

32(k + 1) + 1 + 2(k + 1) + 2 = 7b (for some integer b)

If you can do it for that, that proves it $\forall n \in \mathbb{N}$.

16. Jun 13, 2005

### Galileo

To prove $3^{2k+3}+2^{k+3}$ is divisible by 7 you have to use the induction hypothesis that $3^{2k+1}+2^{k+2}$ is divisible by 7.
If you want to use that equation, just try to massage the first one so you can get the expression of the induction hypothesis in there. After that, the rest is trivial.

17. Jun 13, 2005

### shmoe

Your orignial question put no restrictions on what techniques could be used. Besides, you've solved it already so what's the problem?

(By the way, my hint had nothing to do with induction, but the binomial theorem.)

18. Jun 13, 2005

### mathwonk

in my opinion, it is impossible to prove any statement true for all integers without somehow using induction. even defining addition for all integers needs induction.

19. Jun 13, 2005

### LittleWolf

I agree with Shmoe-BINOMIAL THEOREM. (7+2)^n=...?

20. Jun 14, 2005

### quentinchin

Maybe mathematic induction is the best way to prove this sort of question but if we too often using this kind of method, our mathematic level wouldn't go any further.

I really do not know how to solve this question and I just get the answer from my friend after I asked this question.

Is that
3*9^n + 4*2^n
=3(7+2)^n + 4*2^n
=3[7^n + n*7^(n-1)*2 + ... + n*7*2^(n-1) + 2^n] + 4*2^n
=3[7^n + n*7^(n-1)*2 + ... + n*7*2^(n-1)] + 7*2^n
=7{3[7^(n-1) + n*7^(n-2) + ... + n*2^(n-1)] + 2^n}

this is also another good method.