A brief induction question if no-one minds.

"Prove by induction, 7n - 1 is divisible by 6 for all n >= 1."

n = 1 -> 7 - 1 /6 = 1 so the first condition of induction is satisfied, but I honestly can't work out where to go next...

Printable View

- Dec 7th 2009, 11:30 AMSkeithInduction question
A brief induction question if no-one minds.

"Prove by induction, 7n - 1 is divisible by 6 for all n >= 1."

n = 1 -> 7 - 1 /6 = 1 so the first condition of induction is satisfied, but I honestly can't work out where to go next... - Dec 7th 2009, 12:00 PMAlso sprach ZarathustraIt is not true.
n=10

7*10-1=69!=k*6 when k is natural. - Dec 7th 2009, 12:07 PMSkeith
sorry - accidental double post.

- Dec 7th 2009, 12:08 PMSkeith
Not true... hmm, I'll include what the book says.

"In the case n = 1, 7n - 1 is divisible by 6 so P(1) is true.

Assume now the 7k - 1 is divisible by 6 for some k >= 1.

Then,

7k + 1 = 7(7k) - 1

= 7(7k - 1) + 7 -1

= 7)7k - 1) + 6

Since 7k - 1 is divisible by 6 it follows that 7(7k - 1) + 6 is also divisible by 6." - Dec 7th 2009, 12:16 PMAlso sprach Zarathustrabut if...
you need to prove:

6|7^n - 1 for n>=1

so

we suppose that its true for some n and we prove for n+1.

7^(n+1) - 1 = 7^n*7 - 1 = 7^n(6+1) - 1 = 7^n*6 +7^n - 1

7^n-1 divides by 6 by the step of induction, 6*7^6 divides also by 6. - Dec 7th 2009, 12:38 PMDefunkt
Make your post clearer next time and you will get a proper answer. As you can see, from your first post it looks like you are trying to prove that which is obviously wrong (take n=2, for example).

However I guess you are trying to prove that , which is correct. If this is the case, you have shown P(1) holds. Assume P(k), and now we need to prove that P(k+1) follows.

Note that:

Now, by the induction hypothesis (that is, ), we get:

for some .

But which is divisible by 6, therefore P(k+1) holds and we are done.

If you want to follow your book's way:

But,

Now, by the induction hypothesis, and therefore for some . Substitute and get:

and obviously therefore P(k+1) holds and we are done. - Dec 7th 2009, 12:44 PMSkeith
I'll be sure to do that in future Def. Thankyou all once again for your help, I understand the problem now.