Mathematical Induction

**matthayzon89** · March 15th 2010, 04:41 PM

Can someone please help me Prove: 3^n - 1 is divisible by 2, for all natural numbers n>=1??

**Plato** · March 15th 2010, 05:16 PM

Originally Posted by matthayzon89

Can someone please help me Prove: 3^n - 1 is divisible by 2, for all natural numbers n>=1??

May be you can get another free ride.

**matthayzon89** · March 15th 2010, 05:19 PM

nvm, ill just not do it... it is impossble for me to learn this and study for everything I need to know for tomorrow... ill just take a zero for this assignment, I understand your not suppose to be doing other peoples h.w.

thankz anywayz

**Archie Meade** · March 15th 2010, 06:01 PM

Is $3^n-1$ divisible by 2?

The idea with induction is that you attempt to use the above to show the following...

$3^{n+1}-1$ is divisible by 2

To use it, we need to write $3^{n+1}-1$ with $3^n-1$ in it

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

If $3^n-1$ is divisible by 2,

what can we now say about the above?

Do you follow so far?

**matthayzon89** · March 15th 2010, 07:44 PM

Is this a pretty good proof? this is what I came up with so far....

Thank you Archie Meade

Prrof: Let P(n): 3^n-1
then let n=1 3^1=2 2 is divisible by 2.

Suppose P(k): 3^(k-1)=2m for some integer m.

Multiply by 3... 3^(k+1)-3=2*3=6m

subtract 2 from each side... 3^k+(1-1)=6m-2= **2(3m-1)**

since 3m-1 is an integer then 3^(k+1)-1 is 2 times an integer, therefore it is divisible by 2.

Thus by PMI 3^n-1 is divisible by 2.
[]

I dont really get it

**Archie Meade** · March 15th 2010, 08:15 PM

You took some steps, so you can only get better.

$3^n-1=2m$

$3^{n+1}-1=(3)3^n-1=(2)3^n+\left(3^n-1\right)=(2)3^n+2m=2\left(3^n+m\right)$

which is definately divisible by 2 if $3^n-1$ is.

Learning how proof by induction works can take time.
Textbook methods are not always clear.

If you want, i can try explaining it more tomorrow.

**Prove It** · March 15th 2010, 09:50 PM

The simplest and most common form of mathematical induction proves that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

The basis (base case): showing that the statement holds when n is equal to the lowest value that n is given in the question. Usually, n = 0 or n = 1.
The inductive step: showing that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n.

The assumption in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.
The choice between n = 0 and n = 1 in the base case is specific to the context of the proof: If 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic, then n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if one is presented with a long row of dominoes standing on end, one can be sure that:

The first domino will fall
Whenever a domino falls, its next neighbor will also fall,

so it is concluded that all of the dominoes will fall, and that this fact is inevitable.
Another analogy can be to consider a set of identical lily pads, all equally spaced in a line across a pond, with the first and last lily pads adjacent to the two sides of the pond. If a frog wishes to traverse the pond, he must:

Determine if the first lily pad will hold his weight.
Prove that he can jump from one lily pad to another.

Thus, he can conclude that he can jump to all of the lily pads, however many lily pads there are, and cross the pond.

Mathematical induction - Wikipedia, the free encyclopedia

**Archie Meade** · March 16th 2010, 02:28 AM

hi matthayzon89,

Is $3^n-1$ divisible by 2 ?

$3^1-1=3-1=2$ is divisible by 2

$3^2-1=9-1=8$ is divisible by 2

$3^3-1=27-1=26$ is divisible by 2

so it looks as though it may be true.

What Proof By Induction attempts to do is show whether the following is true or not...

Being divisible by 2 for a first value of n causes $3^n-1$ to be divisible by 2 for the next n, the 2nd one.
Being divisible by 2 for the 2nd value of n causes $3^n-1$ to be divisible by 2 for the 3rd value of n.
Being divisible by 2 for the 3rd n causes divisibility by 2 for the 4th n.
Being divisible by 2 for the 4th n causes divisibility by 2 for the 5th n.

We want to prove whether or not this keeps going as n goes to infinity.
That would take a long time!
We are trying to establish an infinite chain of cause and effect.

We can do this by showing that $3^n-1$ being divisible by 2 causes $3^{n+1}-1$ to be divisible by 2.

If you think about this, by proving the previous statement "in terms of n"
we are in fact proving the following....

True for n=1 causes the statement to be true for n=2.
True for n=2 causes true for n=3.
True for n=3 causes true for n=4.
True for n=4 causes true for n=5................

$3^n-1$ is the value for any natural number $n\ge\ 1$

$3^{n+1}-1$ is the value for the next n.

We want to see whether or not $3^n-1$ being divisible by 2 will cause $3^{n+1}-1$ to be divisible by 2 also.

Proof

$3^{n+1}-1=3^13^n-1=(2+1)3^n-1=(2)3^n+\left(3^n-1\right)$

Now we can see that since $(2)3^n$ is a multiple of 2

$3^n-1$ being divisible by 2 does cause $3^{n+1}-1$ to be divisible by 2.

Since, we have already checked this for the first value of n,
then the formula is true for all natural n.

**emakarov** · March 16th 2010, 06:39 AM

Prrof: Let P(n): 3^n-1
then let n=1 3^1=2 2 is divisible by 2.

Suppose P(k): 3^(k-1)=2m for some integer m.

I would only add this. Identifying induction statement P(n) (it also is the induction hypothesis) is the most crucial step. The rest is done with little thinking and some algebra. But! P(n) is a proposition, not a number! P(n) can be true or false, but it cannot be 3^n-1.

Here P(n) is "3^n - 1 is even". Writing the induction hypothesis P(n) and the claim to prove P(n + 1) is crucial for doing the induction step right.

**novice** · March 16th 2010, 07:10 AM

We are to prove $(3^n-1)$ being divisible by 2 for every positive integer $n$ .

Proof:
We proceed by induction.
Basis step: When $n=1$ , the result $2|(3^n-1)$ holds since $2|2$ .

Inductive step:
Assume that $2|(3^k-1)$ for every positive integer $k$ . Then $3^k-1 = 2x$ for some integer x. We show that $2|(3^{k+1}-1).$

From the assumption $3^k = (2x+1)^*$ . We must begin with

$3^k-1$ . Multiplying through by 3,

$3^{k+1}-3=3 \cdot 3^k -1-2=3(2x+1)^*-1 -2=6x+2-2=2(3x)$ . For last step, we add 2 to bothsides.

$3^{k+1}-1=2(3x)+2=2(3x+1)$
Since $3x+1$ is an integer, $2|(3^{k+1}-1)$

Therefore, by induction, $2|(3^n-1)$ for every positive integer $n$ .

Thread: Mathematical Induction

LinkBack

Thread Tools

Display

Prove

Similar Math Help Forum Discussions

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

Mathematical Induction

Mathematical Induction

Mathematical Induction

Mathematical Induction

Search Tags