# Proove by Induction

• March 21st 2009, 07:38 PM
meg0529
Proove by Induction
I need to Prove that 6^(2n) -1 is divisible by 35. Using mathematical induction.

Hint given : use the equality 6^2n = 36^n = ( 35+1)^n

So step one is to verify if this works for 1, and so I did 6^(2*1) - 1 = 36-1=35 so it works.

In step two I need to assume that this is true for an arbitrary n,

Finally in the deductive proof I need to show that this holds for n+1.

So I set it up as follows (35+1)^(n+1) - 1 = 35k, where k is some constant.
I don't know where to go from here. (Doh)
• March 21st 2009, 07:51 PM
Prove It
Quote:

Originally Posted by meg0529
I need to Prove that 6^(2n) -1 is divisible by 35. Using mathematical induction.

Hint given : use the equality 6^2n = 36^n = ( 35+1)^n

So step one is to verify if this works for 1, and so I did 6^(2*1) - 1 = 36-1=35 so it works.

In step two I need to assume that this is true for an arbitrary n,

Finally in the deductive proof I need to show that this holds for n+1.

So I set it up as follows (35+1)^(n+1) - 1 = 35k, where k is some constant.
I don't know where to go from here. (Doh)

$(35 + 1)^{n + 1} - 1 = (35 + 1)(35 + 1)^n - 1$

$= 35(35 + 1)^n + (35 + 1)^n - 1$

Keeping in mind that you've assumed $(35 + 1)^n - 1$ is divisible by 35. So we can say it equals $35k$, where k is some other whole number.

Therefore,

$(35 + 1)^{n + 1} - 1 = 35(35 + 1)^n + 35k$

$= 35[(35 + 1)^n + k]$

which is divisible by 35.

QED.
• March 21st 2009, 08:20 PM
meg0529
Ok the second half makes sense, I don't follow how you got this

$= 35(35 + 1)^n + (35 + 1)^n - 1$

Thanks!
• March 21st 2009, 08:32 PM
Prove It
Quote:

Originally Posted by meg0529
Ok the second half makes sense, I don't follow how you got this

$= 35(35 + 1)^n + (35 + 1)^n - 1$

Thanks!

Distributive law.

$(35 + 1)(35 + 1)^n - 1 = 35(35 + 1)^n + 1(35 + 1)^n - 1$.
• March 22nd 2009, 10:50 AM
meg0529
O doh! of course thanks so much.