Combinatorial Proofs

**hiddy** · March 15th 2010, 07:40 AM

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

**Opalg** · March 15th 2010, 10:05 AM

Originally Posted by hiddy

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,...,j–1 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}$ .

Originally Posted by hiddy

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.

Thread: Combinatorial Proofs

LinkBack

Thread Tools

Display

Combinatorial Proofs

Similar Math Help Forum Discussions

How to give combinatorial proofs

Can't do combinatorial proofs. Can someone help?

Probability - Combinatorial

combinatorial sum

Sequence Convergence Proofs vs. Continuity Function Proofs

Search Tags