Induction

Jun 2010
69
0
Is the the correct approach to work through this problem

23n – 1 is divisible by 7 for all n>=1
n(1)
23(1) – 1 = (2*2*2) – 1
= 7

23n – 1 = 7m
n(k+1)
23(k+1) – 1 = 2.23k-1
= 2 * (7m+1) – 1
= 14m + 2 -1
= 14m-1
=7(2m-1)
Where (2m-1) is an int.
So 23n – 1 is divisible by 7.
Therefore, by P.M.I 23n – 1 is divisible by 7 for n>=1.
 

Prove It

MHF Helper
Aug 2008
12,897
5,001
First, this is extremely difficult to read. Please learn some LaTeX.

You are trying to prove \(\displaystyle 2^{3n} - 1\) is divisible by \(\displaystyle 7\) for all \(\displaystyle n \geq 1\) (I assume \(\displaystyle n\) is also an integer)...


Base Step: \(\displaystyle n = 1\).

Then \(\displaystyle 2^{3\cdot 1} - 1 = 8 - 1\)

\(\displaystyle =7\) which is divisible by \(\displaystyle 7\).


Inductive Step: Assume this statement is true for \(\displaystyle n = k\).

Then \(\displaystyle 2^{3k} - 1 = 7m\) where \(\displaystyle m\) is an integer.

Now let \(\displaystyle n = k + 1\) we have

\(\displaystyle 2^{3(k + 1)} - 1 = 2^{3k + 3} - 1\)

\(\displaystyle = 2^{3k}\cdot 2^3 - 1\)

\(\displaystyle = 8\cdot 2^{3k} + 8 - 7\)

\(\displaystyle = 8(2^{3k} + 1) - 7\)

\(\displaystyle = 8\cdot 7m - 7\)

\(\displaystyle = 7(8m - 1)\)

which is divisible by \(\displaystyle 7\).


Therefore \(\displaystyle 2^{3n}- 1\) is divisible by \(\displaystyle 7\) for all integer \(\displaystyle n \geq 1\).
 
  • Like
Reactions: dunsta
Jun 2010
69
0
Thanks ProveIt, I completely forgot about Latex for a minute and just pasted in the equation I was working on in word, so sorry!

How does the negative 1 in this line \(\displaystyle = 2^{3k}\cdot 2^3 - 1\)

change to negative 7?

\(\displaystyle =8\cdot 2^{3k} + 8 - 7\)
 

Prove It

MHF Helper
Aug 2008
12,897
5,001
Sorry, that should actually read

\(\displaystyle 8\cdot 2^{3k} - 8 + 7\)

\(\displaystyle = 8(2^{3k} - 1) + 7\).

The rest follows.
 
Jun 2010
69
0
ok, thanks
But how/where does the seven come from?
 

Prove It

MHF Helper
Aug 2008
12,897
5,001
\(\displaystyle -8 + 7 = -1\).

It just takes a bit of practice, I knew I needed to create a \(\displaystyle 7\) in order to have this value be divisible by \(\displaystyle 7\).
 
Jun 2010
69
0
Please excuse my ignorance, as mathematical Induction and I just aren't getting along.
But did you just place the "7" in the equation because you needed it. It didn't come from any other part of the equation?
 

Prove It

MHF Helper
Aug 2008
12,897
5,001
That's correct. And I also realised I'd need to take out a common factor of \(\displaystyle 8\).

Like I said, it just comes from experience.
 
  • Like
Reactions: dunsta