# Math Help - Mathematical induction

1. ## Mathematical induction

Use mathematical induction to prove that

4 x 6^(2n) + 3 x 2^(3n) is divisible by 7 for n=1,2,3...

I roughly know the method but I can't seem to get there with this. Please could someone take the time to post a detailed answer? Thank you

2. ## Re: Mathematical induction

Just out of interest, why did you post this in the Geometry forum?

Anyway, can you at least prove the base case?

3. ## Re: Mathematical induction

I wasn't sure which forum it should be in...where would you suggest I post it?
And yes, I have proved the base case, and I know I have to assume that p(k) is true and use this to prove p(k+1) but I am unsure of how to proceed from there on.

4. ## Re: Mathematical induction

Well what is your P(k) statement?

What are you trying to prove in your P(k+1) statement? Can you use P(k) to help you?

Actually show us what you have done and we can give you some guidance.

5. ## Re: Mathematical induction

I have p(k) is 4 x 6^(2k) + 3 x 2^(3k) = 7m where m is an integer.

And I have to use that to show that p(k+1) is divisible by 7.

So I have 4 x 6^2(k+1) + 3 x 2^3(k+1)

So far I have written it as 4 x 6^(2k+2) + 3 x 2^(3k+3)

And from there I have split the powers to get

4 x 6 x 6^(2k+1) +3 x 4 x 2^(3k+1) ... this is the line that I am unsure of and I don't know if it's right or not. If it is, I may need some guidance as to where to go from here.

6. ## Re: Mathematical induction

The final step is wrong, you should have

\displaystyle \begin{align*} 4 \times 6^{2k + 2} + 3\times 2^{3k + 3} &= 4 \times 6^2 \times 6^{2k} + 3 \times 2^3 \times 2^{3k} \end{align*}

7. ## Re: Mathematical induction

Ok thanks, I understand that.
So do I know multiply out the 4x6^2 and the 3x2^3 ?

8. ## Re: Mathematical induction

No, you need to somehow get \displaystyle \begin{align*} 4 \times 6^{2k} + 3\times 2^{3k} \end{align*} so that you can replace it with 7m.

9. ## Re: Mathematical induction

I know I somehow have to get it into the form of p(k) to show it is divisible by 7, but I'm playing around with it and I can't see how it works?

10. ## Re: Mathematical induction

Yes I know that but I can't see how?!

11. ## Re: Mathematical induction

Originally Posted by alexlbrown59
Yes I know that but I can't see how?!
We are trying to reduce the expression for the case of k + 1 to either the case for k or a combination of the cases for 1 and k.

I have found that it helps sometimes in finding a proof to actually work out the cases for n = 1, n = 2, n = 3. You have to do that for n = 1 to do a proof by induction anyway.

$4 * 6^{(2 * 1)} + 3 * 2^{(3 * 1)} = 4 * 36 + 3 * 8 = 144 + 24 = 168 = 7 * 24.$

$4 * 6^{(2 * 2)} + 3 * 2^{(3 * 2)} = 4 * 6^4 + 3 * 2^6 = 4 * 1296 + 3 * 64 = 5284 + 192 = 5376 = 7 * 768.$

$4 * 6^{(2 * 3)} + 3 * 2^{(3 * 3)} = 4 * 6^6 + 3 * 2^9 = 4 * 46656 + 3 * 512 = 186624 + 1536 = 188160 = 7 * 26680.$

Now that is initially disappointing because I at least do not see an obvious relationship between the various multiples of 7. But I now have some confidence that what I am trying to prove may actually be true.

Now I play around a bit 5376 - 168 = 5208 = 7 * 744. And 188160 - 5376 = 182784 = 7 * 26112. Well of course, the difference between two multiples of 7 is itself a multiple of 7. Maybe that will give me a proof.

$k \in \mathbb Z\ and\ k > 0\ and\ 4 * 6^{2k} + 3 * 2^{3k} = 7m_k,\ where\ m_k \in \mathbb Z\ and\ m_k > 0.$

$4 * 6^{2(k + 1)} + 3 * 2^{3(k + 1)} = 4 * 6^{2k} * 6^2 + 3 * 2^{3k} * 2^3 = 36(4 * 6^{2k}) + 8(3 * 2^{3k}) .$

$So\ 4 * 6^{2(k + 1)} + 3 * 2^{3(k + 1)} - (4 * 6^{2k} + 3 * 2^{3k}) =$

$36(4 * 6^{2k}) + 8(3 * 2^{3k}) - (4 * 6^{2k} + 3 * 2^{3k}) =$

$35(4 * 6^{2k}) + 7(3 * 2^{3k}) = 7(20 * 6^{2k} + 3 * 2^{3k}).$

$But\ obviously\ 20 * 6^{2k} + 3 * 2^{3k}\ is\ an\ integer > 0\ because\ k\ is\ a\ positive\ integer.$

$So\ \exists\ j_{k + 1} \in \mathbb Z\ such\ that\ j_{k + 1} = 20 * 6^{2k} + 3 * 2^{3k} > 0.$

$\therefore 4 * 6^{2(k + 1)} + 3 * 2^{3(k + 1)} - (4 * 6^{2k} + 3 * 2^{3k}) = 7j_{k + 1} \implies$

$4 * 6^{2(k + 1)} + 3 * 2^{3(k + 1)} = 7j_{k + 1} + 4 * 6^{2k} + 3 * 2^{3k} = 7j_{k + 1} + 7m_k = 7(j_{k + 1} + m_k).$

There is no guaranteed route to a proof. You just have to try various things.

12. ## Re: Mathematical induction

Wow Jeff! Many thanks for such a clear and detailed answer. I would never have thought about doing it that way but it does make sense, and I reckon with a bit more practice I'll get the hang of it. You're a life saver

13. ## Re: Mathematical induction

I'm reviewing this topic and worked out your problem, hope this helps

14. ## Re: Mathematical induction

4×6^2×6^(2k)+3×2^3×2^(3k)

Man it's so close if you do it using modulus 7.

Then 4×6^2×6^(2k)+3×2^3×2^(3k) mod 7 = 4*1*6^(2k) + 3*1*2^(3k) mod 7 = 4*6^(2k)+3*2^(3k) mod 7 = (according to inductive hypothesis) 0