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

Printable View

- Mar 15th 2010, 04:41 PMmatthayzon89Prove
Can someone please help me Prove: 3^n - 1 is divisible by 2, for all natural numbers n>=1??

- Mar 15th 2010, 05:16 PMPlato
May be you can get another free ride.

- Mar 15th 2010, 05:19 PMmatthayzon89
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 - Mar 15th 2010, 06:01 PMArchie Meade
Is $\displaystyle 3^n-1$ divisible by 2?

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

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

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

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

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

what can we now say about the above?

Do you follow so far? - Mar 15th 2010, 07:44 PMmatthayzon89
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:( - Mar 15th 2010, 08:15 PMArchie Meade
You took some steps, so you can only get better.

$\displaystyle 3^n-1=2m$

$\displaystyle 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__$\displaystyle 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. - Mar 15th 2010, 09:50 PMProve It
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 thatthe statement holds for some**if***n*,the statement also holds when**then***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 - The
- Mar 16th 2010, 02:28 AMArchie Meade
hi matthayzon89,

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

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

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

$\displaystyle 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__$\displaystyle 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__$\displaystyle 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 $\displaystyle 3^n-1$ being divisible by 2__causes__$\displaystyle 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................

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

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

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

Proof

$\displaystyle 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 $\displaystyle (2)3^n$ is a multiple of 2

$\displaystyle 3^n-1$ being divisible by 2__does cause__$\displaystyle 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. - Mar 16th 2010, 06:39 AMemakarovQuote:

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.

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. - Mar 16th 2010, 07:10 AMnovice
We are to prove $\displaystyle (3^n-1)$ being divisible by 2 for every positive integer $\displaystyle n$.

*Proof*:

We proceed by induction.

Basis step: When $\displaystyle n=1$, the result $\displaystyle 2|(3^n-1)$ holds since $\displaystyle 2|2$.

Inductive step:

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

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

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

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

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

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

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