Proving binomial coefficients identity: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$

Question

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that:

$$\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}.$$

Tried proving it by induction but got stuck. Any help with proving it by induction or any other proof technique is appreciated.

Answer 1

Assign numbers $1,2,3,\ldots,n,n+1$ to $n+1$ objects. The number of ways to choose $r+1$ of them is $\dbinom{n+1}{r+1}$.

Either you choose the very last one and $r$ others bearing lower numbers (the number of ways to do that is $\dbinom n r$),

or you choose the one just before the last one and $r$ others bearing lower numbers (the number of ways to do that is $\dbinom{n-1}r$),

or you choose the one just before that one and $r$ others bearing lower numbers (the number of ways to do that is $\dbinom{n-2}r$),

or $\ldots\ldots$

Answer 2

Let $E = \{1,2, \dots , n+1\}$. The number $\binom{n+1}{r+1}$ is the number of subsets $A$ of $E$ with $r + 1$ elements.

Classify these subsets $A$ according to their largest element $b$, which can be any number among $r + 1$, $r + 2$, ..., $n + 1$. The number of $(r+1)$-element subsets of $E$ with largest element $b$ is the same as the number of $r$-element subsets of $\{1, 2, \dots, b-1\}$, which is $\binom{b-1}{r}$.

Now $b$ can be any number $r + 1, r + 2, \ldots, n + 1$, and there are $\binom{r}{r}$, $\binom{r + 1}{r}, \ldots, \binom{n}{r}$ possible subsets $A$ in each case. This proves the desired equality.

Answer 3

As mentioned above, this has been answered before (actually very recently). But for something different, here is a pictorial proof. $$\def\r{\color{red}{\bullet}}\def\b{\color{blue}{\bullet}}\def\u{\circ}\def\w{\bullet}\def\s{\ \ \ \ } \eqalignno{ \matrix{\w\cr \w\s\w\cr \w\s\w\s\w\cr \w\s\w\s\w\s\w\cr \w\s\w\s\w\s\w\s\w\cr \w\s\w\s\b\s\w\s\w\s\w\cr}\cr =\matrix{\w\cr \w\s\w\cr \w\s\w\s\w\cr \w\s\w\s\w\s\w\cr \w\s\r\s\b\s\w\s\w\cr \w\s\w\s\u\s\w\s\w\s\w\cr}\cr =\matrix{\w\cr \w\s\w\cr \w\s\w\s\w\cr \w\s\r\s\b\s\w\cr \w\s\r\s\w\s\w\s\w\cr \w\s\w\s\u\s\w\s\w\s\w\cr}\cr =\matrix{\w\cr \w\s\w\cr \w\s\r\s\b\cr \w\s\r\s\w\s\w\cr \w\s\r\s\w\s\w\s\w\cr \w\s\w\s\u\s\w\s\w\s\w\cr}\cr =\matrix{\w\cr \w\s\r\cr \w\s\r\s\w\cr \w\s\r\s\w\s\w\cr \w\s\r\s\w\s\w\s\w\cr \w\s\w\s\u\s\w\s\w\s\w\cr}\cr}$$

Answer 4

Proving by induction

inductive step

$$\begin{pmatrix}r\\r\end{pmatrix} + \begin{pmatrix}r+1\\r\end{pmatrix} + \dots + \begin{pmatrix}n\\r\end{pmatrix} =\begin{pmatrix}n\\r+1\end{pmatrix} + \begin{pmatrix}n\\r\end{pmatrix}$$ [as the identity holds for natural numbers less than n.]

We Know that, $$\begin{pmatrix}n\\r+1\end{pmatrix}+ \begin{pmatrix}n\\r\end{pmatrix} = \begin{pmatrix}n+1\\r+1\end{pmatrix}$$ see here

Hence proved.