Induction

**dunsta** · July 26th 2010, 10:53 PM

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** · July 26th 2010, 11:10 PM

First, this is extremely difficult to read. Please learn some LaTeX.

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

Base Step: $n = 1$ .

Then $2^{3\cdot 1} - 1 = 8 - 1$

$=7$ which is divisible by $7$ .

Inductive Step: Assume this statement is true for $n = k$ .

Then $2^{3k} - 1 = 7m$ where $m$ is an integer.

Now let $n = k + 1$ we have

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

$= 2^{3k}\cdot 2^3 - 1$

$= 8\cdot 2^{3k} + 8 - 7$

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

$= 8\cdot 7m - 7$

$= 7(8m - 1)$

which is divisible by $7$ .

Therefore $2^{3n}- 1$ is divisible by $7$ for all integer $n \geq 1$ .

**dunsta** · July 26th 2010, 11:24 PM

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 $= 2^{3k}\cdot 2^3 - 1$

change to negative 7?

$=8\cdot 2^{3k} + 8 - 7$

**Prove It** · July 27th 2010, 12:14 AM

Sorry, that should actually read

$8\cdot 2^{3k} - 8 + 7$

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

The rest follows.

**dunsta** · July 27th 2010, 01:07 AM

ok, thanks
But how/where does the seven come from?

**Prove It** · July 27th 2010, 01:23 AM

$-8 + 7 = -1$ .

It just takes a bit of practice, I knew I needed to create a $7$ in order to have this value be divisible by $7$ .

**dunsta** · July 27th 2010, 03:45 AM

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** · July 27th 2010, 04:53 AM

That's correct. And I also realised I'd need to take out a common factor of $8$ .

Like I said, it just comes from experience.

Thread: Induction

LinkBack

Thread Tools

Display

Induction

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Induction

Rigorously prove the principle of complete induction from mathematical induction??

Mathemtical Induction Proof (Stuck on induction)

induction

Search Tags