# Thread: Combinatorial Proofs

1. ## 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:

$
\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

2. 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:

$
\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.