# Thread: Prove divisibility by 7 (using induction)

1. ## Prove divisibility by 7 (using induction)

Hi,

I'm trying to show that 4*6^(2n) + 3*2^(3n) is divisible by 7 for any positive integer n.

This works for n = 1. I then suppose it holds for n = k, and subsequently try to manipulate n = k+1 to have factors 7 and n = k, but I don't seem to get anywhere.

For n = k we have

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

Assume this is divisible by 7. Then for n = k + 1 we have

4*6^(2(k+1)) + 3*2^(3(k+1)

= 4*6^(2k+2) + 3*2^(3k+3)

= 4*36*6^(2k) + 3*8*2^(3k)

This is as far as I get I'm afraid Any help at all would be much appreciated

2. ## solution

Nevermind, I got there in the end! Continuing from my previous post:

4*36*6^(2k) + 3*8*2^(3k)

= 144*6^(2k) + 24*2^(3k)

= 4*6^(2k) + 3*2^(3k) + 140*6^(2k) + 21*2^(3k)

where the first two sections resemble the sum when n = k, which was assumed to be divisible by 7, and where the last two sections have factors 140 and 21, respectively, and are hence also divisible by 7. Therefore the whole sum is divisible by 7.

Then we know that the original sum is divisible by 7 when n = 1, and when n = k+1 given that it is divisible by 7 when n = k, hence it has been shown by induction that it is divisible by 7 for all positive integers n.