5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – user87543
    Commented Nov 29, 2013 at 12:23

8 Answers 8

3
$\begingroup$

(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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Commented Nov 28, 2013 at 16:06
  • $\begingroup$ @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. $\endgroup$
    – Siméon
    Commented Nov 28, 2013 at 16:33
  • $\begingroup$ This is a proof by induction, regardless of your objection. $\endgroup$ Commented Nov 28, 2013 at 19:06
  • $\begingroup$ @AndresCaicedo. I don't understand why you say I object. Is there something unclear in my previous comment? $\endgroup$
    – Siméon
    Commented Nov 28, 2013 at 20:28
3
$\begingroup$

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

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

$\endgroup$
2
$\begingroup$

$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)$

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

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$

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

$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$.

$\endgroup$
0
$\begingroup$

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
$\endgroup$
1
  • 1
    $\begingroup$ Please, type your answers using MathJax. $\endgroup$
    – Gibbs
    Commented Oct 13, 2018 at 12:49
0
$\begingroup$

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}^+$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .