Results 1 to 7 of 7

Math Help - Mathematical Induction with an inequality

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    15

    Mathematical Induction with an inequality

    Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove


    <br />
\frac{1}{n!} \leq \frac{1}{2^{n-1}}<br />

    for all positive integers i.e n=0,1,2,3..

    anyone mind throwing some hints?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    This holds iff n!\ge 2^{n-1}. To prove this by induction, note that when going from n to n+1, the left-hand side is multiplied by n+1, while the right-hand side is multiplied by 2.

    In fact, it is not necessary to take reciprocals. The LHS is divided by n+1, and the RHS is divided by 2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Dave2718 View Post
    Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove


    <br />
\frac{1}{n!} \leq \frac{1}{2^{n-1}}<br />

    for all positive integers i.e n=0,1,2,3..

    anyone mind throwing some hints?
    0! is defined as 1

    \frac{1}{1}<\frac{1}{2^{-1}} as \frac{1}{2^{-1}}=2

    \frac{1}{1!}=\frac{1}{2^0}

    \frac{1}{2(1)}=\frac{1}{2^1}

    \frac{1}{3(2)}<\frac{1}{2(2)}

    \frac{1}{4(3)2}<\frac{1}{2(2)2}

    By inspection, the factorial is always increasing more since we are multiplying by values more and more greater than 2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Dave2718 View Post
    Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove


    <br />
\frac{1}{n!} \leq \frac{1}{2^{n-1}}<br />

    for all positive integers i.e n=0,1,2,3.. Zero is not a positive integer.

    anyone mind throwing some hints?
    It's straight forward.

    I will show you the inductive step.

    Proof:

    We assume \frac{1}{n!} \leq \frac{1}{2^n-1}, and wish to prove \frac{1}{(n+1)!} \leq \frac{1}{2^{n+1}-1}.

    By implication it is expressed as

     <br />
\frac{1}{n!} \leq \frac{1}{2^n-1} \Rightarrow \frac{1}{(n+1)!} \leq \frac{1}{2^{n+1}-1}<br />

    So if we can start from \frac{1}{n!} \leq \frac{1}{2^n-1} and end our proof with \frac{1}{(n+1)!} \leq \frac{1}{2^{n+1}-1}, we are home free.

    Let's begin with \frac{1}{n!} \leq \frac{1}{2^n-1}. Multiplying through with \frac{1}{n+1}, we obtain

    \frac{1}{(n+1)n!} \leq \frac{1}{(2^n-1)(n+1)}. Observe

    \frac{1}{(n+1)!} \leq \frac{1}{n2^n+2^n-n-1}
    \frac{1}{(n+1)!} \leq \frac{1}{2^n(n+1)-n-1}= \frac{1}{2\cdot 2^n-n-1}\leq \frac{1}{2^{n+1}-2}< \frac{1}{2^{n+1}-1}

    So we succeeded.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Dave2718 View Post
    Hello, I had this on my exam today, I was positive that I'd be able to deal with inequalities but for some reason this one threw me off. I had to prove


    <br />
\frac{1}{n!} \leq \frac{1}{2^{n-1}}<br />

    for all positive integers i.e n=0,1,2,3..

    anyone mind throwing some hints?
    via induction..

    \frac{1}{n!}\le \frac{1}{2^{n-1}} ?

    Does the above cause \frac{1}{(n+1)!}\le \frac{1}{2^n} ?

    Proof

    \frac{1}{(n+1)!}\le \frac{1}{2^n}\ \Rightarrow\ \left(\frac{1}{n+1}\right)\frac{1}{n!}\le \left(\frac{1}{2}\right)\frac{1}{2^{n-1}}

    When n\ge\ 2,\ n+1\ge\ 2

    Hence the inequality is true as \left(\frac{1}{n+1}\right)\frac{1}{n!}\le\ \left(\frac{1}{2}\right)\frac{1}{2^{n-1}} if \frac{1}{n!}\le\ \frac{1}{2^{n-1}}

    and proof of the truth of the inequality is verified for the first n.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Archie Meade View Post
    via induction..

    \frac{1}{n!}\le \frac{1}{2^{n-1}} ?

    Does the above cause \frac{1}{(n+1)!}\le \frac{1}{2^n} ?

    Proof

    \frac{1}{(n+1)!}\le \frac{1}{2^n}\ \Rightarrow\ \left(\frac{1}{n+1}\right)\frac{1}{n!}\le \left(\frac{1}{2}\right)\frac{1}{2^{n-1}}

    When n\ge\ 2,\ n+1\ge\ 2

    Hence the inequality is true as \left(\frac{1}{n+1}\right)\frac{1}{n!}\le\ \left(\frac{1}{2}\right)\frac{1}{2^{n-1}} if \frac{1}{n!}\le\ \frac{1}{2^{n-1}}

    and proof of the truth of the inequality is verified for the first n.
    Sorry, I wasn't paying attention. Since it's \frac{1}{2^{n-1}} , it should be easier.

    Let's see:

    <br />
\begin{aligned}<br />
\frac{1}{(n+1)!}&=\frac{1}{2^{n-1}}\cdot \frac{1}{(n+1)}\\<br />
&\leq \frac{1}{2^{n-1}}\cdot \frac{1}{(2)}\\<br />
&\leq \frac{1}{2^n}<br />
\end{aligned}<br />

    Yep!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    15
    thanks guys, I actually tried the problem after the test before anyone was able to help me out and actually got it pretty much just as all of you did, don't you hate it when that happens?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical induction
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: August 26th 2011, 05:28 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Proof of mathematical induction inequality
    Posted in the Algebra Forum
    Replies: 5
    Last Post: March 15th 2010, 03:34 PM
  4. mathematical induction for an inequality
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 4th 2010, 02:28 PM
  5. mathematical induction...!!!!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 12th 2009, 04:37 AM

Search Tags


/mathhelpforum @mathhelpforum