Results 1 to 10 of 10

Math Help - Mathematical Induction

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    75

    Prove

    Can someone please help me Prove: 3^n - 1 is divisible by 2, for all natural numbers n>=1??
    Last edited by matthayzon89; March 15th 2010 at 06:00 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by matthayzon89 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    Posts
    75
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2010
    Posts
    75
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,829
    Thanks
    1602
    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:
    1. 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.
    2. 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:

    1. The first domino will fall
    2. 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:

    1. Determine if the first lily pad will hold his weight.
    2. 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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    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.
    Last edited by Archie Meade; March 16th 2010 at 05:10 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Sep 2009
    Posts
    502
    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.
    Last edited by novice; March 16th 2010 at 09:10 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 01:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 01:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 12:30 PM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 04:21 PM

Search Tags


/mathhelpforum @mathhelpforum