# Proove by Induction

• Mar 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)
• Mar 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)

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

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

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

Therefore,

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

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

which is divisible by 35.

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

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

Thanks!
• Mar 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

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

Thanks!

Distributive law.

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