Results 1 to 3 of 3

Math Help - Induction

  1. #1
    Newbie
    Joined
    Feb 2011
    From
    Westwood, California
    Posts
    4

    Induction

    The question I have is....
    Using induction, verify the inequality

    (1+x)^n is greater than or equal to (1+nx)
    for x is greater than or equal to -1 and n is greater than or equal to 1

    The basis step was easy enough (as always)
    However, I became stuck at the induction part...
    Since the condition given is for BOTH x AND n, I tried doing induction for
    x+1 and n+1

    So I had the following...

    Assuming the above statement to be true, prove
    (2+x)^(n+1) is greater than or equal to 1+(n+1)(x+1)

    I tried a lot of different ways, but couldn't solve it...
    The closest thing I got to an answer was by doing the following...

    (2+x)^(n+1)=(2+x)(2+x)^n

    (2+x)(2+x)^n is greater than or equal to (1+x)^n+(n+x+1)

    Since, (2+x)^n is greater than or equal to (1+x)^n I assumed that part of the equation to be true... leaving me to prove
    (2+x) is greater than or equal to (n+x+1)/((1+x)^n)

    which is easy enough to prove.... Since (1+x)^n will ALWAYS be greater than 1 given the condition x is greater than or equal to -1 and n is greater than or equal to 1

    But I'm pretty sure this is NOT the right way to prove this (since this is supposed to be proven using induction... and I feel like I am taking way too many assumptions)

    Any hints/tips on how to solve an induction problem with two changing variables?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Siron's Avatar
    Joined
    Jul 2011
    From
    Norway
    Posts
    1,250
    Thanks
    20

    Re: Induction

    Using induction:
    First step
    n=1 then (1+x)\geq 1+x which is true.
    Second step
    Suppose the proposition is true for n=k and so:
    (1+x)^{k}\geq 1+kx
    We have to prove the proposition is true for n=k+1 and so for all n\geq 1 (by the given condition).
    Third step
    Proof for n=k+1 that means:
    (1+x)^{k+1}\geq 1+(k+1)x
    We now for sure that:
    (1+x)^{k}\cdot (1+x)\geq (1+kx)\cdot (1+x) (if (1+x)>0)
    (This is true by step 2)
    That means:
    (1+x)^{k}\cdot (1+x)\geq 1+kx+x+kx^2
    And because x^2>0: 1+kx+x+kx^2\geq 1+kx+x, therefore:
    (1+x)^{k}\cdot (1+x)\geq 1+kx+x+kx^2\geq 1+kx+x
    (1+x)^{k+1}\geq 1+kx+x
    (1+x)^{k+1}\geq 1+(k+1)x

    Which is true by step 2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1

    Re: Induction

    Quote Originally Posted by HyunGyum View Post
    The question I have is....
    Using induction, verify the inequality

    (1+x)^n is greater than or equal to (1+nx)
    for x is greater than or equal to -1 and n is greater than or equal to 1

    The basis step was easy enough (as always)
    However, I became stuck at the induction part...
    Since the condition given is for BOTH x AND n, I tried doing induction for
    x+1 and n+1

    So I had the following...

    Assuming the above statement to be true, prove
    (2+x)^(n+1) is greater than or equal to 1+(n+1)(x+1)

    I tried a lot of different ways, but couldn't solve it...

    Any hints/tips on how to solve an induction problem with two changing variables?
    x\ge\ -1

    so that

    1+x\ge\ 0\Rightarrow\ (1+x)^n\ge\ 0

    Hence we are dealing with non-negative values for that part.

    That is the significance of the constraint on x.

    To apply Proof By Induction, continue in the normal way using n=k and n=k+1.

    You want to prove that IF (1+x)^k\ge\ 1+kx

    THEN (1+x)^{k+1}\ge\ 1+(k+1)x

    Therefore

    (1+x)^{k+1}=(1+x)(1+x)^k

    So if (1+x)^k\ge\ 1+kx

    then (1+x)(1+x)^k\ge\ (1+x)(1+kx)

    Now you only need show that (1+x)(1+kx)\ge\ 1+(k+1)x

    when k is positive (since k is any value of n).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

/mathhelpforum @mathhelpforum