Results 1 to 3 of 3

Thread: Induction

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

    Induction

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

    $\displaystyle (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 $\displaystyle (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
    Belgium
    Posts
    1,254
    Thanks
    24

    Re: Induction

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

    Re: Induction

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

    $\displaystyle (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?
    $\displaystyle x\ge\ -1$

    so that

    $\displaystyle 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 $\displaystyle (1+x)^k\ge\ 1+kx$

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

    Therefore

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

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

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

    Now you only need show that $\displaystyle (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: Apr 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Mar 19th 2008, 05:12 PM

/mathhelpforum @mathhelpforum