Proving Combination identity by reasoning [duplicate]

By suitably interpreting each side show that $${k\choose k}+{{k+1}\choose k}+{{k+2}\choose k}+...+{{n-1}\choose k}+{n\choose k}={{n+1}\choose{k+1}}$$

This is easily shown by induction, but I think the questin is asking (and regardless I would like to know) what is the 'reason' for this, i.e. can we justify this result by considering subsets the way we can for results like ${n\choose r}+{n\choose{r+1}}={{n+1}\choose{r+1}}?$

I was surprised that I was unable to find this results on the internet although I'm almost certain it's out there so apologies if this need not be posted here.

Thank you.

marked as duplicate by naslundx, Henrik, Namaste, user223391, Community♦Aug 28 '16 at 14:33

• – grand_chat Aug 27 '16 at 21:30
• Oh yeah, apologies – Aka_aka_aka_ak Aug 28 '16 at 14:33

How many ways are there to choose $k+1$ out of $n+1$ ?

For the sake of simplicity, let us choose $k+1$ numbers out of $[1,n+1]$

First case : $1$ is chosen. We must choose another $k$ numbers out of $n$, so we have $\binom{n}{k}$ possibilities.

Second case : $1$ is not chosen, but $2$ : We now have $\binom{n-1}{k}$ possibilities. You can continue until the case that $n-k+1$ is the smallest chosen number.

Hint: Say there are $n+1$ numbers, $1,2,\dots,n+1$. You want to choose $k+1$ of them. Suppose you choose $i$ as the rightmost number. This means you must choose $k$ out of the remaining $i-1$ numbers to the left of $i$. Can you derive the equality from here?

Consider the set $S_n=\{1,\dots,n+1\}$. Then ${n \choose k}$ is the number of subsets of $S_n$ containing $k+1$ elements, one of which is the element $n+1$. In this way we have counted all possible subsets of $S_n$ containing $k+1$ elements, except for the subsets that do not contain $n+1$.

To proceed, ${n-1 \choose k}$ is the number of subsets of $S_n$ containing $k+1$ elements, one of which is the element $n$, and not containing $n+1$.

At this point we have counted all subsets of $S_n$ except for those that do not contain $n+1$ nor $n$.

Proceed in this way to get to the statement.

• Are you accidentally writing ${{k}\choose{n}}$ instead of ${{n}\choose{k}}$? – Tom Aug 27 '16 at 21:19
• @Tom I was indeed, thanks. – user2520938 Aug 27 '16 at 21:20