Results 1 to 3 of 3

Math Help - induction question

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    55

    induction question

    For each m >=1, prove that

    <br />
\displaystyle\sum_{k = 0}^{m} k .  \dbinom{m}{k} = m \cdot 2 ^{m-1}

    No idea what to do
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by smplease View Post
    For each m >=1, prove that

    <br />
\displaystyle\sum_{k = 0}^{m} k .  \dbinom{m}{k} = m \cdot 2 ^{m-1}

    No idea what to do
    \displaystyle \sum_{k=0}^{m} k\cdot \dbinom{m}{k} = m \cdot 2 ^{m-1}

    proof:-
    \displaystyle \sum_{k=0}^{m} k\cdot \dbinom{m}{k} = 0 + \dbinom{m}{1} + 2 \dbinom{m}{2} + 3\dbinom {m}{3} + ... + m \dbinom{m}{m}

    \displaystyle \sum_{k=0}^{m} k\cdot \dbinom{m}{k} = \frac{m!}{(m-1)!1!}+ \frac{2m!}{(m-2)!2!} + \frac{3m!}{(m-3)!3!} + ... + \frac{m!}{m!0!}

    \displaystyle \sum_{k=0}^{m} k\cdot \dbinom{m}{k} = m \left( \frac{(m-1)!}{(m-1)!} + \frac{(m-1)!}{(m-2)!} + \frac{(m-1)!}{(m-3)!2!}+ ... +\frac{(m-1)!}{(m-1)!}\right) = m \cdot 2^{m-1}

    since
    \displaystyle 2^{m-1} = \sum_{k=0}^{m-1} \dbinom{m-1}{k}

    check here

    ohh sorry by induction

    let P(m) : \sum_{k=0}^{m} k \dbinom{m}{k} = m2^{m-1}

    check for P(1)

     \sum_{k=0}^{1} k \dbinom{1}{k} = 0 + 1 \dbinom{1}{1} and this = 1 \cdot 2^{0}
    P(m) is true for 1

    suppose P(m) is true want P(m+1) true
    want \displaystyle \sum_{k=0}^{m+1} k \dbinom{m+1}{k} = (m+1)2^{m}

    \displaystyle \sum_{k=0}^{m+1} k\cdot \dbinom{m+1}{k} = \frac{(m+1)!}{(m+1-1)!1!} +2 \frac{(m+1)!}{(m+1-2)!2!} +3 \frac{(m+1)!}{(m-2)!3!}+...+ \frac{(m+1)!}{(m+1)!}

    \displaystyle \sum_{k=0}^{m+1} k\cdot \dbinom{m+1}{k} = (m+1)\left( \frac{(m)!}{(m+1-1)!1!} +2 \frac{m!}{(m+1-2)!2!} +3 \frac{(m)!}{(m-2)!3!}+...+ \frac{(m)!}{(m)!}\right)

    and \displaystyle \frac{(m)!}{(m+1-1)!1!} +2 \frac{m!}{(m+1-2)!2!} +3 \frac{(m)!}{(m-2)!3!}+...+ \frac{(m)!}{(m)!} = \sum_{k=0}^{m} \dbinom{m}{k}

    \displaystyle \sum_{k=0}^{m+1} k\cdot \dbinom{m+1}{k} = (m+1)\left(\sum_{k=0}^{m} \dbinom{m}{k}\right)= (m+1)2^m

    since \displaystyle 2^m = \sum_{k=0}^{m} \dbinom{m}{k}
    so P(m) is true the proof ends
    Last edited by Amer; October 8th 2010 at 10:19 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2008
    Posts
    55
    you are a GOD!
    thanks so much Amer
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 7th 2009, 01:44 PM
  2. question about induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 19th 2009, 03:32 PM
  3. induction question..
    Posted in the Calculus Forum
    Replies: 5
    Last Post: January 6th 2009, 07:23 AM
  4. Induction question..
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 12th 2007, 09:13 PM
  5. induction question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 16th 2007, 09:14 AM

Search Tags


/mathhelpforum @mathhelpforum