Results 1 to 8 of 8
Like Tree5Thanks
  • 1 Post By emakarov
  • 3 Post By Soroban
  • 1 Post By emakarov

Math Help - Proving an inequality without induction

  1. #1
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Proving an inequality without induction

    Hello, I have proved this statement using induction, but I am just wondering if you can do it without induction:

    \sum_{k=1}^n\frac{k}{2^k}<2

    for all n\geq 1.

    I'm wondering if there is another way since I heard that induction is "not elegant".

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Proving an inequality without induction

    Induction in general is very elegant. In this case, obviously, it requires strengthening the induction statement from \sum_{k=1}^n\frac{k}{2^k}<2 to \sum_{k=1}^n\frac{k}{2^k}<2-E(n) for some positive expression E(n). This method illustrates the reason for the inequality and shows how close the sum gets to 2. I would say this is very illuminating way of proving the inequality. Which E(n) did you use?

    Another way is a standard trick from generating functions. Let f(x)=\sum_{k=0}^\infty\frac{x^k}{2^k} =\frac{2}{2-x}. Then f'(x)=\sum_{k=1}^\infty\frac{kx^{k-1}}{2^k} for x<2 (see Wikipedia), so f'(1)=\sum_{k=1}^\infty\frac{k}{2^k}.
    Thanks from Ragnarok
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,719
    Thanks
    634

    Re: Proving an inequality without induction

    Hello, Ragnarok!

    Hello, I have proved this statement using induction,
    but I am just wondering if you can do it without induction:

    . . . \displaystyle\sum_{k=1}^n\frac{k}{2^k}<2

    We have: . . . . . S \;=\;\frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + \frac{4}{2^4} + \hdots + \frac{n}{2^n}

    Multiply by \tfrac{1}{2}:\;\frac{1}{2}S \;=\;\qquad \frac{1}{2^2} + \frac{2}{2^3} + \frac{3}{2^4} + \hdots + \frac{n-1}{2^n} + \frac{n}{2^{n+1}}

    Subtract: . . . . \frac{1}{2}S \;=\;\underbrace{\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \hdots + \frac{1}{2^n}}_{\text{geometric series}} - \frac{n}{2^{n+1}}

    . . The geometric series has a sum of: 1 - \tfrac{1}{2^n}


    We have: . \frac{1}{2}S \;=\;\left(1 - \frac{1}{2^n}\right) - \frac{n}{2^{n+1}}

    . . . . . . . . \frac{1}{2}S \;=\;\frac{2^{n+1} - 2 - n}{2^{n+1}}

    Multiply by 2: . S \;=\;\frac{2^{n+1} - 2 - n}{2^n}

    . . . . . . . . . . . S \;=\;\frac{2^{n+1}}{2^n} - \frac{2+n}{2^n}

    . . . . . . . . . . . S \;=\;2 - \frac{n+2}{2^n}


    Since the fraction is positive, S \:<\:2.
    Thanks from johng, emakarov and Ragnarok
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Proving an inequality without induction

    Thank you both so much! I'm sorry I didn't get back to you sooner. emakarov, I tried to put my proof in the form you described and I couldn't - in fact, I couldn't even reproduce the proof. So maybe I got something wrong. I'm going to try again. Soroban, I love your answer, thank you so much.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Proving an inequality without induction

    I am not sure my method, which is supposed to work by proving \sum_{k=1}^n k/2^k<2-E(n) for some E(n), is feasible. However, Soroban's final equality can be proved by induction.
    Thanks from Ragnarok
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Proving an inequality without induction

    Okay, I think I got it. Here's what I did for the inductive step:

    \sum_{k=1}^n\frac{k}{2^k}<2

    \Longleftrightarrow\frac{1}{2^n}\sum_{k=1}^n2^{n-k}k<2

    \Longleftrightarrow\sum_{k=1}^n2^{n-k}k<2^{n+1}

    \Longleftrightarrow \left(\sum_{k=1}^n2^{n-k}k\right)+(n+1)<2^{n+1}+(n+1)

    Since n+1<2^{n+1} (can be shown separately), we have 2^{n+1}+(n+1)<2\cdot 2^{n+1}=2^{n+2} and so

    \Longleftrightarrow\sum_{k=1}^{n+1}2^{n-k}k<2^{n+2}

    as required.

    So what would be the E(n) in this argument?
    Last edited by Ragnarok; June 30th 2013 at 02:27 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Proving an inequality without induction

    Oh, sorry, I forgot to put it back in the right form:

    \sum_{k=1}^{n+1}2^{n-k}k<2^{n+2}

    \Longleftrightarrow \frac{1}{2^{n+1}}\sum_{k=1}^{n+1}2^{n-k}k<2

    \Longleftrightarrow \sum_{k=1}^{n+1}\frac{k}{2^k}<2

    I hope that's right...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Proving an inequality without induction

    Mistake in that last bit...should be an n+1 in parts of it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving inequality through induction
    Posted in the Advanced Math Topics Forum
    Replies: 18
    Last Post: May 22nd 2012, 09:13 AM
  2. Replies: 3
    Last Post: December 12th 2010, 01:16 PM
  3. Induction for an inequality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 5th 2010, 10:51 PM
  4. induction inequality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2010, 04:09 AM
  5. Induction Inequality
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 10th 2008, 08:21 PM

Search Tags


/mathhelpforum @mathhelpforum