# Math Help - Induction question

1. ## Induction 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...

2. ## It is not true.

n=10
7*10-1=69!=k*6 when k is natural.

3. sorry - accidental double post.

4. 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."

5. ## but 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.

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

However I guess you are trying to prove that $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:

$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, $6|7^k -1$), we get:

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

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

$7^{k+1}-1 = 7\cdot 7^k-1$
But, $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, $6|(7^k-1)$ and therefore $7^k-1 = 6m$ for some $m \in \mathbb{N}$. Substitute and get:
$7 \cdot (7^k-1)+6 = 7 \cdot 6m + 6 = 6(7m + 1)$ and obviously $6 | 6(7m+1)$ therefore P(k+1) holds and we are done.