Mathematical induction

Discussion in 'General Off-Topic Chat' started by dark_angel, Jul 22, 2008.

Jul 22, 2008

Mathematical induction by dark_angel at 11:46 AM (1,144 Views / 0 Likes) 11 replies

  1. dark_angel
    OP

    Newcomer dark_angel Advanced Member

    Joined:
    Jul 14, 2006
    Messages:
    67
    Location:
    Queensland
    Country:
    Australia
    hi guys,

    can u guys help me with a question on my homework, its really been bugging me for a few hours now
    the question is, using mathematical induction show that:
    2^n < 3^n for any integer n≥1
     
  2. The Teej

    Former Staff The Teej Also known as The Tjalian

    Joined:
    Jun 27, 2004
    Messages:
    4,210
    Location:
    England
    Country:
    United Kingdom
    where n = 1

    2^1 = 2
    3^1 = 3

    where n = 2

    2^2 = 4
    3^2 = 9

    ...or am I not doing it right?
     
  3. elenar

    Member elenar GBAtemp Regular

    Joined:
    Aug 10, 2007
    Messages:
    106
    Country:
    United States
    (2^n)^(1/n)
     
  4. dark_angel
    OP

    Newcomer dark_angel Advanced Member

    Joined:
    Jul 14, 2006
    Messages:
    67
    Location:
    Queensland
    Country:
    Australia
    here's an example if it helps its extremely hard to follow because microsoft word wont paste it properly so i apologise for the messiness

    P(n): 1^3+2^3+3^3+ …….+n^3=[n(n+1)/2]^2
    assume P(n)is true
    therefore need to prove P(n+1) is true by making P(n+1)=P(n)
    P(n+1): 1^3+2^3+3^3+ …….+n^3+(n+1)^3=[((n+1)(n+1+1))/2]^2
    1^3+2^3+3^3+ …….+n^3+(n+1)^3-(n+1)^3=[((n+1)(n+1+1))/2]^2-(n+1)^3
    1^3+2^3+3^3+ …….+n^3=(n+1)^2 [((n+2)^2)/4-(4n+4)/4]
    1^3+2^3+3^3+ …….+n^3=(n+1)^2 [(n^2+4n+4)/4-(4n+4)/4]
    1^3+2^3+3^3+ …….+n^3=(n+1)^2 [(n^2+4n+4-4n-4)/4]
    1^3+2^3+3^3+ …….+n^3=(n+1)^2 [n^2/4]
    1^3+2^3+3^3+ …….+n^3=(n^2 (n+1)^2)/4
    1^3+2^3+3^3+ …….+n^3=[n(n+1)/2]^2
    Therefore for every value of n:
    1^3+2^3+3^3+ …….+n^3=[n(n+1)/2]^2
     
  5. BigX

    Member BigX GBAtemp Regular

    Joined:
    Aug 29, 2007
    Messages:
    292
    Location:
    over there
    Country:
    Canada
    2^n < 3^n for any n equal or larger than 1

    2^1 < 3^n => 2^2 < 3^n =>...=> 2^x < 3^x
    get the xth root on both sides makes (you can get the xth root for any x except 0)
    => 2
     
  6. dark_angel
    OP

    Newcomer dark_angel Advanced Member

    Joined:
    Jul 14, 2006
    Messages:
    67
    Location:
    Queensland
    Country:
    Australia
    its just to show that certain patterns that go on forever will always be correct if you keep going down further
    instead of becoming incorrect as it goes along
     
  7. Joey90

    Member Joey90 Not around any more

    Joined:
    Apr 21, 2007
    Messages:
    703
    Location:
    UK
    Country:
    United Kingdom
    Induction eh?

    Well...

    when n=1, 2 < 3 so true for n=1

    if we assume it is true for n, take the next case:

    (2^n)*2 =? (3^n)*3

    2^(n+1) =? 3^(n+1)

    and because it's true for n, its true for n=n+1

    2^(n+1) < 3^(n+1)

    now you can induct yourself all the way to infinity.

    P.S. It's a kinda retarded thing to do by induction, but if that's what it says...
     
  8. kazumi213

    Member kazumi213 GBAtemp Regular

    Joined:
    Oct 16, 2006
    Messages:
    293
    Country:
    Spain
    2^n < 3^n for any integer n≥1

    log(2^n) < log(3^n)

    n * log(2) < n * log(3)

    log(2) < log(3)

    which is true.
     
  9. PizzaPasta

    Member PizzaPasta Son of p1ngpong

    Joined:
    Jan 2, 2008
    Messages:
    530
    Location:
    Akron, Ohio
    Country:
    United States
    This thread = YUCK!

    All of you are communicating in bee language. I'm appalled!
     
  10. Elfish

    Member Elfish GBAtemp Fan

    Joined:
    Sep 20, 2004
    Messages:
    447
    Country:
    Germany
    pwned ^^
     
  11. CockroachMan

    Member CockroachMan Scribbling around GBATemp's kitchen.

    Joined:
    Jan 14, 2006
    Messages:
    3,889
    Location:
    Brazil
    Country:
    Brazil
    ( 2^n < 3^n )

    for n = 1: 2 < 3 OK!
    for n = 2: 4 < 9 OK!
    ...
    for n = k: 2^k < 3^k
     
  12. deathfisaro

    Member deathfisaro Narcistic Deathfisaro Fan

    Joined:
    Mar 16, 2007
    Messages:
    2,053
    Location:
    Vancouver, BC
    Country:
    Canada
    Base case: n=1
    2^1 < 3^1, we confirmed that 2^n < 3^n holds for the base case n=1.

    Induction:
    If 2^n < 3^n, then 2^(n+1) < 3^(n+1), for positive integer n

    2^(n+1) = 2^n * 2, 3^(n+1) = 3^n * 3
    2^n < 3^n, therefore 2^n * 2 < 3^n * 2

    3^n * 3 can be re-written as 3^n * 2 + 3^n.
    We know 3^n > 0, and 2^n * 2 < 3^n * 2.
    So 2^n * 2 < 3^n * 2 + 3^n still holds true.


    Because we proved that 2^n < 3^n with our base case n=1.
    We also proved If 2^n < 3^n, then 2^(n+1) < 3^(n+1).
    Therefore, 2^n < 3^n is true for any integer n >= 1.

    You need to have both the base case and induction.
    The base case determines the lower limit of your answer (if you picked n=2 as your base case, your answer becomes 2^n < 3^n is true for any integer n >= 2, even though it's very easy to prove that it is true for n=1).
    The induction part has the form of "If (equation involving n) then (equation involving n+1)". "If" is crucial for the induction step, and proving "(equation involving n)" is true with the base case is also crucial because "If false then true/false" is also true and we don't want that.
     

Share This Page