Mathematical induction

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

  1. dark_angel
    OP

    dark_angel Advanced Member

    Newcomer
    67
    1
    Jul 14, 2006
    Queensland
    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

    The Teej Also known as The Tjalian

    Former Staff
    4,210
    6
    Jun 27, 2004
    England
    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

    elenar GBAtemp Regular

    Member
    106
    3
    Aug 10, 2007
    United States
    (2^n)^(1/n)
     
  4. dark_angel
    OP

    dark_angel Advanced Member

    Newcomer
    67
    1
    Jul 14, 2006
    Queensland
    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

    BigX GBAtemp Regular

    Member
    292
    0
    Aug 29, 2007
    Canada
    over there
    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

    dark_angel Advanced Member

    Newcomer
    67
    1
    Jul 14, 2006
    Queensland
    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

    Joey90 Not around any more

    Member
    703
    0
    Apr 21, 2007
    UK
    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

    kazumi213 GBAtemp Regular

    Member
    293
    0
    Oct 16, 2006
    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

    PizzaPasta Son of p1ngpong

    Member
    530
    1
    Jan 2, 2008
    United States
    Akron, Ohio
    This thread = YUCK!

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

    Elfish GBAtemp Fan

    Member
    447
    3
    Sep 20, 2004
    Gambia, The
    pwned ^^
     
  11. CockroachMan

    CockroachMan Scribbling around GBATemp's kitchen.

    Member
    3,889
    5
    Jan 14, 2006
    Brazil
    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

    deathfisaro Narcistic Deathfisaro Fan

    Member
    2,053
    0
    Mar 16, 2007
    Canada
    Vancouver, BC
    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.