I am trying to work through a few problem-solving practice questions, and this one is giving me a lot of trouble:
Given integers $r,n$ such that $0\leq r\leq n$ , use a counting argument to prove the following equalities:
1)
$\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}+...+\binom{n}{r}=\binom{n+1}{r+1}$
2)
$\sum_{k=r}^{n}\binom{n}{k}\binom{k}{r}=2^{n-r}\binom{n}{r}$
I have mostly been trying to figure out some real world scenario that models the first inequality, although I have spent a bit of time with the second inequality as well. I have been unsuccessful in trying to figure out why these equalities are true.
For the first one, I have mostly considered situations involving drawing $r$ balls from each of $n-r+1$ bags, where one bag has $r$ balls, then another has $r+1$ balls and so on up to $n$ balls. I am not really getting anywhere so if anyone has a better approach, that is much appreciated.
For 1), separate the possible selections of $r{+}1$ elements from $n{+}1$ by the index of the first selected element. Then when the first element is chosen, there are $\binom nr$ ways to choose the remaining elements; when the second element is the lowest index chosen, there are $\binom {n-1}r$ ways to choose the remaining elements, and so on until when the lowest indexed element is as high as possible there is only $\binom rr =1$ way to choose the final elements.
For 2), we are counting all ways of having an intermediate selection of $k$ elements before making the final choice of $r$ elements, summing across the possible sizes of such intermediate selections. Considering any one final choice, the possible intermediate selections can either have or not have any of the other elements that do not make the final choice, tracking the powerset of non-chosen elements. Thus there are $2^{n-r}$ possible intermediate selection sets for each final choice.