# 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