Mathematical Induction.?

Question

6^(2n-1) + 1 prove its divisible by 7. (please note that the +1 is not in the power (2n-1) )

Base case (n=1) 6^(2(1)-1) +1 = 7/7 = 1
since its an integer the base is satisfied.
Now assume the property holds for n=k such that 7 divides 6^(2k-1) +1.
Now let n=k+1

6^(2(k+1)-1) +1 ---->
6^(2k+2-1) + 1 = ?? im lost here...

what about the 36? do i distribute it to the stuff in the parenthesis.?

Answer 1

So far so good. You have the inductive step at

6^(2k + 2 - 1) + 1

Rewrite this as

( 6^2 ) ( 6^(2k - 1) ) + 1

36 ( 6^(2k - 1)) + 1

Now we will add and subtract a factor of 36...

( 36 ) ( 6^(2k - 1) + 1 ) + 1 - 36

See what I did? The extra + 1 in the parenthesis adds 36, and I subtract the 36 back off at the end.

( 36 ) ( 6^(2k - 1) ) + 1 - 35
( 36 ) ( 6^(2k - 1) ) - 35

The leading term contains the factor ( 6^(2k - 1) + 1) so it is divisible by 7 from the basis case. The second term is -35, which is also divisible by 7. Therefore, the entire expression is divisible by 7.

Answer 2

I think jgou... has it pretty close; he just has some carelessness at lines 5 and 6 from the bottom; but the eureka insight is his.

You've shown that the theorem is true for n=1, then from the assumption that it's true for n=k, you must show it's true for n=k+1:
---------------------
YOUR WORDS:
Now assume the property holds for n=k such that 7 divides
6^(2k-1) +1.

If the above is divisible by 7 then an integer multiple of it is divisible by 7: (multiply by 6^2. Why? ...because you're seeking to get the theorem as if (k+1) had been plugged in for n).

6^2 [6^(2k-1) +1] = 6^(2k+1) + 36 = 6^(2k+1) +1 + 35, grouped to call attention to certain components =

[6^(2k+1) +1] + 35

Seven clearly divides the last term; and it must also divide the bracketed term (remember this is an integer multiple of something assumed to be divisible by 7). And that 7 divides the bracketed term is what you were after. Therefore the theorem is true for all integers n > = 1.

(jgouda... essentially did this first.)

Answer 3

From about where you left off...

Let integer m = [6^(2k-1) + 1]/7.

Now let n=k+1

6^(2(k+1)-1) + 1 = 6^(2k+2-1) + 1
6^(2(k+1)-1) + 1 = 6^(2k-1+2) + 1
6^(2(k+1)-1) + 1 = 6^(2k-1)*(6^2) + 1
6^(2(k+1)-1) + 1 = 6^(2k-1)*(6^2) + 1 + [(6^2) – (6^2)]
6^(2(k+1)-1) + 1 = 6^(2k-1)*(6^2) + (6^2) - (6^2) + 1
6^(2(k+1)-1) + 1 = [6^(2k-1) + 1]*(6^2) - (6^2) + 1
6^(2(k+1)-1) + 1 = [6^(2k-1) + 1]*36 - 36 + 1
6^(2(k+1)-1) + 1 = [6^(2k-1) + 1]*36 - 35
6^(2(k+1)-1) + 1 = [7m]*36 - 35
6^(2(k+1)-1) + 1 = 36m*7 - 5*7
6^(2(k+1)-1) + 1 = (36m – 5)*7 which is divisible by 7.

Answer 4

Noninductive proof: 6 = -1 mod 7. Plug that in,

(-1)^(2n-1) + 1 = 0 mod 7. Therefore 7 | 6^(2n-1) + 1

Another proof: 6^(2n-1) + 1 has the factor 6 + 1 since
a+b divides a^n + b^n for odd n.

Answer 5

Note: Actually, you have to check that the inductive step is valid for the base case, or you can fall into the trap exemplified by the famous (invalid) proof that all horses are the same color.

Answer 6

NOTE : "jgoulden" dropped the " +1" between the ) ) in the terms on 5th & 6th lines from the bottom