i have to proof the following equations but not with induction and I have absolutly no idea:
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 ways. So the number of ways of selecting k+1 numbers from n+1 is .
Originally Posted by hiddy
and more general:
This follows from the previous part of the question, which tells us that . Replace j by a+i in that sum to get . In a similar way, . Subtract the the second sum from the first to get the result.