Results 1 to 2 of 2

Math Help - Combinatorial Proofs

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    15

    Combinatorial Proofs

    Hey

    i have to proof the following equations but not with induction and I have absolutly no idea:

    \sum_{j=k}^{n} {j \choose k} = {n+1 \choose k+1}

    and more general:

    <br />
\sum_{j=m}^{n} {a+i \choose k} = {a+n+1 \choose k+1}-{a+m \choose  k+1}\quad    \forall n \in \mathbb N \quad \forall a \in  \mathbb R


    Hope anyone can help me
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by hiddy View Post
    i have to proof the following equations but not with induction and I have absolutly no idea:

    \sum_{j=k}^{n} {j \choose k} = {n+1 \choose k+1}
    Combinatorial proof: Suppose you want to choose k+1 of the n+1 numbers 0,1,2,...,n. Let j be the largest of these k+1 numbers. Then j must be one of the numbers k, k+1, ... , n. The remaining k numbers can be chosen from the j numbers 0,1,2,...,j1 in \textstyle{j\choose k} ways. So the number of ways of selecting k+1 numbers from n+1 is \sum_{j=k}^n{j\choose k}.

    Quote Originally Posted by hiddy View Post
    and more general:

    <br />
\sum_{j=m}^{n} {a+i \choose k} = {a+n+1 \choose k+1}-{a+m \choose  k+1}\quad    \forall n \in \mathbb N \quad \forall a \in  \mathbb R
    This follows from the previous part of the question, which tells us that {a+n+1\choose k+1} = \sum_{j=k}^{a+n}{j\choose k}. Replace j by a+i in that sum to get {a+n+1\choose k+1} = \sum_{i=k-a}^{n}{a+i\choose k}. In a similar way, {a+m\choose k+1} = \sum_{i=k-a}^{m-a-1}{a+i\choose k}. Subtract the the second sum from the first to get the result.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to give combinatorial proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 21st 2010, 12:06 AM
  2. Can't do combinatorial proofs. Can someone help?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 20th 2009, 10:39 AM
  3. Probability - Combinatorial
    Posted in the Statistics Forum
    Replies: 5
    Last Post: August 15th 2009, 08:26 AM
  4. combinatorial sum
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2009, 11:46 AM
  5. Replies: 3
    Last Post: October 6th 2007, 03:01 PM

Search Tags


/mathhelpforum @mathhelpforum