- #1

- 42

- 2

## Homework Statement

Give combinatorial proofs of the identities below. Use the following structure for each proof. First, define an appropriate set S. Next, show that the left side of the equation counts the number of elements in S. Then show that, from another perspective, the right side of the equation also counts the number of elements in set S. Conclude that the left side must be equal to the right, since both are equal to |S|.

a)

##\binom{2n}{n} \sum_{k=0}^n \binom{n}{k} * \binom{n}{n-k}##

b)

##\sum_{i=0}^r \binom{n+i}{i} = \binom{n+r+1}{r}##

Hint: consider a set of binary strings that could be counted using the right side of the equation, then try partitioning them into subsets countable by the elements of the sum on the left.

## Homework Equations

## The Attempt at a Solution

a)The left hand side is just choosing n out of 2n.

The right hand side is choosing a total of n out of 2n as well, but with the constraint that some k must be from one half, some n-k must be from the other. Thus you would need to sum across all of k up to n in order to all possible selections.

b) I'm having trouble understanding their hint. I've never seen counting attempted on a set of binary strings before, only on a singular binary string. I don't know what to do with the right hand side.

The left hand side I think I understand a little more: Each individual term ##\binom{n+i}{i}## is the way I've seen used to express the number of possibilities if you have an n+i binary string, choosing i of the bits to be 1's. If there's a summation from i=0 to r, then it seems to me that might be a set of binary strings from length n to n+r, and the number of possible combinations for each string is added up. However, I don't see how the right hand side relates to this. Am I on the right track?