Is 7^n-1 Divisible by 6 for All Non-Negative Integers n? Prove with Induction

[jonroberts74]

prove (induction) $$6|7^{n}-1; \forall n \ge 0$$






P(0)

$$6|7^0 -1$$

6|0

P(k)


$$6|7^k-1$$


what I want to show: $$6|7^{k+1}-1$$




I know I'll kick myself but this one isn't jumping out at me.

$$7 \cdot 7^k-1$$

maybe something with $$(6+1)^k(6+1)-1$$

 

[micromass]

You undoubtly know the formulas $x^2 - a^2 = (x-a)(x+a)$ and $x^3 - a^3 = (x-a)(a^2 + ax+ x^2)$. Do you know how it generalizes to $x^n - a^n$?

 

[jonroberts74]

$$x^n−a^n=(x−a)(x^{n−1}+x^{n−2}a+x^{n−3}a^2+…+xa^{n−2}+a^{n−1})$$

so

replace x with 7 and a with 1??

 

[micromass]

$$x^n−a^n=(x−a)(x^{n−1}+x^{n−2}a+x^{n−3}a^2+…+xa^{n−2}+a^{n−1})$$

so

replace x with 7 and a with 1??

Yep!

 

[jonroberts74]

$$7^{k+1}−1^{k+1}=(7−1)(x^{k}+7^{k−1}1+7^{k−2}1^2+…+(7)1^{k−1}+1^{k})$$

I had to alter it cause its k+1, correct?

 

[micromass]

$$7^{k+1}−1^{k+1}=(7−1)(x^{k}+7^{k−1}1+7^{k−2}1^2+…+(7)1^{k−1}+1^{k})$$

I had to alter it cause its k+1, correct?

Sure, this is correct. Notice that you don't really need induction for this!

 

[jonroberts74]

thanks!

 

[HallsofIvy]

With induction you don't really need that long sum:
If $7^k- 1$ is a multiple of 6 then $7^k- 1= 6m$ for some integer m so that $7^k= 6m+ 1$.

$$7^{k+1}- 1= 7(7^k)- 1= 7(6m+1)- 1= 6(7m)+ 7- 1= 6(7m)+ 6= 6(7m+1)$$

 

[Quesadilla]

With induction you don't really need that long sum:
Is $7^k- 1$ is a multiple of 6 then $7^k- 1= 6m$ for some integer m so that $7^k= 6m+ 1$.

$$7^{k+1}- 1= 7(7^k)- 1= 7(6m+1)- 1= 6(7m)+ 7- 1= 6(7m)+ 6= 6(7m+1)$$

Yes. If you were told to use induction this seems to be more like what they wanted you to do.