How to prove this statement: $\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

Still a beginner here. Need to learn formatting.

I am guessing by induction? Not sure what or how to go forward with this.

Need help with the proof.

Answer 1

Those binomial coefficients can be visualized in Pascal's triangle as something that looks like a hockey stick, where everything along the shaft representing the left side of your equation, and the blade representing the right side term.

A fundamental property of Pascal's triangle is that the sum of any two numbers in the same row, next to each other, is equal to the number in the row below them, in between them. This is called Pascal's rule.

If you use Pascal's rule $n-r+1$ times, you get the hockey stick identity.

Answer 2

Yes. It can be proved by induction.

In the process of proof, you should know the following equality:

$C_n^r+C_n^{r+1}=C_{n+1}^{r+1}$

Added:

When $n=r$, it holds. Suppose that $n=k$, it also holds. Now let $n=k+1$,

$$C_r^r + C_{r+1}^r + \cdots + C_{k+1}^r+ C_{k+2}^r=C_{k+1}^{r+1}+C_{k+2}^{r}=C_{k+2}^{r+1}$$

Answer 3

What is the number on the left counting?

The number of subsets of size $r$ of $\{1,2,3\dots r\}$ plus the number of subsets of size $r$ of $\{1,2,3\dots r+1\}$ plus the number of subsets of size $r$ of $\{1,2,3\dots r+1,r+2\}$ and so on up until the number of subsets of size $r$ of the set $\{1,2,3\dots n\}$

What is the element in the right counting? Th number of sunsets of size $r+1$ of the set $\{1,2,3\dots n+1\}$

Lets give a bijection between the elements in the right and those in the left.

How? suppose you have a subset $S$ of size $r+1$ of $\{1,2,3\dots n+1\}$ Let $k$ be it's greatest element, we associate to this subset a subset of size $r$ of the set $\{1,2,3\dots k-1\}$ which one?

$S-k$ Clearly this is a function from the obects counted on the right to those counted on the left. It is injective since different subsets go to different sets, and it is surjective since the subset $R$ of size $r$ of $\{1,2,3\dots m\}$ comes precisely from the set $R\cup \{m+1\}$.