# Thread: 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 $\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.

7. I'll be sure to do that in future Def. Thankyou all once again for your help, I understand the problem now.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}