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 $\displaystyle 6 | (7\cdot n - 1)$ which is obviously wrong (take n=2, for example).

However I guess you are trying to prove that $\displaystyle 6|(7^n-1)$, 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:

$\displaystyle 7^{k+1}-1 = 7\cdot 7^k - 1 = (6+1)7^k - 1 = 6 \cdot 7^k + (7^k-1)$

Now, by the induction hypothesis (that is, $\displaystyle 6|7^k -1$), we get:

$\displaystyle 6 \cdot 7^k + (7^k-1) = 6\cdot 7^k + 6m$ for some $\displaystyle m \in \mathbb{N}$.

But $\displaystyle 6\cdot 7^k + 6m = 6(7^k + m)$ which is divisible by 6, therefore P(k+1) holds and we are done.

If you want to follow your book's way:

$\displaystyle 7^{k+1}-1 = 7\cdot 7^k-1$

But, $\displaystyle 7\cdot 7^k -1 = 7\cdot 7^k -7 +7 -1 =7 \cdot 7^k + 7\cdot (-1) + 7 -1= 7 \cdot (7^k-1) + 7 - 1 = 7 \cdot (7^k -1)+6$

Now, by the induction hypothesis, $\displaystyle 6|(7^k-1)$ and therefore $\displaystyle 7^k-1 = 6m$ for some $\displaystyle m \in \mathbb{N}$. Substitute and get:

$\displaystyle 7 \cdot (7^k-1)+6 = 7 \cdot 6m + 6 = 6(7m + 1)$ and obviously $\displaystyle 6 | 6(7m+1)$ 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.