# 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
Commented Nov 29, 2013 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. Commented Nov 28, 2013 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. Commented Nov 28, 2013 at 16:33
• This is a proof by induction, regardless of your objection. Commented Nov 28, 2013 at 19:06
• @AndresCaicedo. I don't understand why you say I object. Is there something unclear in my previous comment? Commented Nov 28, 2013 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
Commented Nov 29, 2013 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
Commented Nov 29, 2013 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)=?$$ Commented Nov 28, 2013 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
Commented Nov 29, 2013 at 12:17
• @TMM, rectified, thanks for your observation Commented Nov 29, 2013 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


Base case

First, we verify the base case where $$n = 1$$.

LHS = $$2^3 - 1 = 8-1 = 7$$ wich is divisible by 7

So the base case holds

Inductive step

Assume true for $$n=k$$, so $$2^{3k} - 1 = 7m$$ for some $$m \in \mathbb{Z}^+$$

When $$n=k+1$$ $$2^{3(k+1)} - 1$$ $$2^{3k+3} - 1$$ $$(2^3)(2^{3k}) - 1$$ $$(8)(2^{3k}) - 1$$

By the inductive hypothesis $$2^{3k} = 7m +1$$, so

$$(8)(7m +1) - 1$$ $$(8)(7m) + 8 - 1$$ $$(8)(7m) + 7$$ $$7(8m+1)$$ which is divisible by 7

Since the statement was shown to be true for $$n=1$$ and it was also shown that if the statement is true for $$n=k$$, $$k \in \mathbb{Z}^+$$, it is also true for $$n=k+1$$, it follows by the principle of mathematical induction that the statement is true for all $$n \in \mathbb{Z}^+$$

If n= 1 $$2^{3n}- 1= 2^3- 1= 8- 1= 7$$ is divisible by 7. (Or start at n=0. $$2^{3n}- 1= 2^0- 1= 1- 1= 0$$ is divisible by 7.)

Now suppose that, for n= k, $$2^{3k}- 1$$ is divisible by 7: $$2^{3k}- 1= 7p$$ for some integer, p. Then $$2^{3(k+ 1)}= 2^{3k}2^3- 1= 8(2^{3k})- 1= 8(2^{3k}- 1+ 1)- 1= 8(2^{3k- 1}- 1)+ 8- 1= 8(7p)+ 7= 7(8p+ 1)$$ so is divisible by 7.