Prove using mathematical induction that $2^{3n}-1$ is divisible by $7$

So, i wanna prove $2^{3n}-1$ is divisible by $7$, so i made this:

$2^{3n}-1 = 7\cdot k$ -> for some $k$ value

$2^{3n+1} = 1+2\cdot1 - 2\cdot1$

$2^{3n+1} - 1-2\cdot1 + 2\cdot1$

$2^{3n}\cdot2 - 1-2\cdot1 + 2\cdot1$

$2(2^{3n}-1) -1 +2$

$2\cdot7k+1$ -> made this using the hypothesis.

so, i dont know if its right, or if its wrong, i dont know how to keep going from this, or if its the end.

Thanks.

• except first two lines i am sure the rest does not mean so much.... You might want to look at the way you have written and you may like to edit that...
– user87543
Nov 29 '13 at 12:23

(Without induction)

There is a very useful identity $a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + \dots + a b^{n-2} + b^{n-1})$.

If you take $a = 2^{3} = 8$ and $b=1$, the result becomes obvious.

• This identity is indeed the way I'd prove the result, but I wouldn't say "without induction", because a proof of the identity will involve induction. Nov 28 '13 at 16:06
• @AndreasBlass: It is a tricky question whether a proof necessarily involves "induction" or not. Here the identity can be reduced to $\sum_{k=0}^n 0 = 0$. I think it is reasonable to admit the latter in this proof (as an axiom). I would be surprise if that was the kind of induction that the original poster had in mind. Nov 28 '13 at 16:33
• This is a proof by induction, regardless of your objection. Nov 28 '13 at 19:06
• @AndresCaicedo. I don't understand why you say I object. Is there something unclear in my previous comment? Nov 28 '13 at 20:28

Assume $2^{3k}-1=7m$

Consider $2^{3(k+1)}-1=2^{3k}.2^3-1=(7m+1)8-1=7(8m+1)=7n$

$f(n) = 2^{3n}-1$

$f(0) = 0$ and $7|0$

Suppose that $7|f(n)$, let's say $f(n) = 7k$, $\Rightarrow f(n+1) = 2^{3n+3}-1 = 8\cdot2^{3n}-1 = 8\cdot2^{3n}-1 + 8 - 8 = 8(2^{3n}-1) - 7 = 8\cdot(7k) - 7 = 7\cdot(8k-1)$

• Your notation is wrong; it should be $7 | 0$ and $7 | f(n)$.
– TMM
Nov 29 '13 at 12:14
• Yes, you are right, I wrote it quickly and I did not notice that error, now I've corrected it, thanks!
– Ikki
Nov 29 '13 at 13:55

If $\displaystyle f(m)=2^{3m}-1$

$\displaystyle f(m+1)=2^{3(m+1)}-1$ and not $2^{3m+1}-1$

So, $2^{3(m+1)}-1=2^3\cdot2^{3m}-1=2^3(2^{3m}-1)-1+2^3$

• @MatheusSilva, $$f(x)=x^x,f(x+h)=?$$ Nov 28 '13 at 15:52
• $2^{3(m+1)} \neq 2^3 \cdot 2^m$ and $2^3\cdot2^{3m}-1 \neq 2^3(2^{3m}-1)+1-8$
– TMM
Nov 29 '13 at 12:17
• @TMM, rectified, thanks for your observation Nov 29 '13 at 12:28

$2^{3n}-1=8^n-1=(7+1)^n-1$. Now note that all terms in the expansion of $(7+1)^n$ are multiples of $7$, except the last, which cancels with $-1$. Hence $2^{3n}-1$ is a multiple of $7$.

P(n) = (2^3n)-1

p(1) = (2^3x1)-1 = 8-1 = 7 is divisible by 7

Let n =k then p(k) =( 2^3k)-1 = 7x [assume it is divisible by 7]

therefore 2^3k = 7x +1

Let n =k+1 then p(k+1) = (2^3(k+1))-1 = (2^3k+3)-1

= (2^3k x 2^3)-1

= ((7x +1)2^3 ) -1

= ((7x +1)8 ) -1

= (56x +8) -1

= 56x +8 -1

=56x +7

= 7(8x +1)

therefore it is divisible by 7