Results 1 to 3 of 3

Thread: Sums of Binomial Coefficients - proof by induction

  1. January 22nd 2010, 05:06 AM #1
    shmounal
    shmounal is offline
    Junior Member
    Joined
    Jan 2010
    Posts
    28

    Sums of Binomial Coefficients - proof by induction

    Hi,

    Was wondering if anyone could help with this question i've been struggling with. Im sure I'm just missing something simple but can't work it out. I need to prove by induction that the sum from j=o to n of j Choose k is equal to n+1 Choose k+1. Think I need to use the identity n Choose k+1 is equal to (n-1 Choose k) plus (n-1 choose k+1). Any help very appreciated!!

    \binom{n+1}{k+1} = \sum_{j=0}^{n}\binom{j}{k}
    Follow Math Help Forum on Facebook and Google+
  2. January 22nd 2010, 06:27 AM #2
    Grandad
    Grandad is offline
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello shmounal

    Welcome to Math Help Forum!
    Quote Originally Posted by shmounal View Post
    Hi,

    Was wondering if anyone could help with this question i've been struggling with. Im sure I'm just missing something simple but can't work it out. I need to prove by induction that the sum from j=o to n of j Choose k is equal to n+1 Choose k+1. Think I need to use the identity n Choose k+1 is equal to (n-1 Choose k) plus (n-1 choose k+1). Any help very appreciated!!

    \binom{n+1}{k+1} = \sum_{j=0}^{n}\binom{j}{k}
    You're right! The result you quote is:
    \binom{n-1}{k}+\binom{n-1}{k+1}= \binom{n}{k+1}
    and if, in this result, we replace n by (n+2) we get:
    \binom{n+1}{k}+\binom{n+1}{k+1}= \binom{n+2}{k+1} ...(1)
    Now suppose that P(n) is the propositional function
    \sum_{j=0}^{n}\binom{j}{k}= \binom{n+1}{k+1}
    Then:
    P(n) \Rightarrow
    \sum_{j=0}^{n+1}\binom{j}{k}= \sum_{j=0}^{n}\binom{j}{k}+\binom{n+1}{k}
    =\binom{n+1}{k+1}+ \binom{n+1}{k}

    =\binom{n+2}{k+1} using     (1)
    Therefore:
    P(n) \Rightarrow P(n+1)
    I'll leave you to verify that P(1) is true, and that by Induction the result follows.

    Grandad
    Follow Math Help Forum on Facebook and Google+
  3. January 22nd 2010, 07:44 AM #3
    shmounal
    shmounal is offline
    Junior Member
    Joined
    Jan 2010
    Posts
    28
    Thankyou so much for your help - LEGEND
    Last edited by shmounal; January 23rd 2010 at 04:03 AM.
    Follow Math Help Forum on Facebook and Google+
« Circular Permutations of a Multiset | congruency questions »

Similar Math Help Forum Discussions

  1. Proof of binomial sums
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 8th 2011, 07:01 AM
  2. Parity proof with binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2011, 12:57 PM
  3. Proof of a series with binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 25th 2010, 08:08 PM
  4. Induction proof involving sums of consecutive powers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2009, 06:01 AM
  5. Binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 5th 2008, 11:21 AM

Search Tags


/mathhelpforum @mathhelpforum