Hint on how to prove the identity $\sum_{0 \leq k \leq n } \binom{k}{m} = \binom{n + 1}{m + 1}$

Question

Let $N$ be a positive integer. Then, we have

$\sum\limits_{j=1}^{N} \binom{j}{6} = \binom{N+1}{7}$.

Could anyone explain this equation a little bit? I wrote out the left hand side as $\binom{1}{6} + \dots + \binom{N}{6}$, but it did not help at much.

UPDATE

From lecture notes, I found a proposition says:

$\sum\limits_{0\leq k\leq n} \binom{k}{m} = \binom{n+1}{m+1}$.

Could anyone give a hint on how to prove it?

Answer 1

We can also prove the Hockey-stick identity with a bit of algebra. It is convenient to use the coefficient of operator $[x^m]$ to denote the coefficient of $x^m$ in a series. This way we can write for instance \begin{align*} [x^m](1+x)^n=\binom{n}{m} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n\binom{k}{m}}&=\sum_{k=0}^n[x^m](1+x)^k\tag{1}\\ &=[x^m]\sum_{k=0}^n(1+x)^k\tag{2}\\ &=[x^m]\frac{(1+x)^{n+1}-1}{(1+x)-1}\tag{3}\\ &=[x^{m+1}](1+x)^{n+1}\tag{4}\\ &\,\,\color{blue}{=\binom{n+1}{m+1}}\tag{5} \end{align*}

Comment:

• In (1) we apply the coefficient of operator.

• In (2) we use the linearity of the coefficient of operator.

• In (3) we use the finite geometric series formula.

• In (4) we apply the rule $[x^{m+1}]A(x)=[x^m]x^{-1}A(x)$. We also skip the term $-1$ on the right hand side, since this constant value does not contribute to $[x^{m+1}]$.

• In (5) we select the coefficient of $x^{m+1}$.

Answer 2

This is often called the hockey stick identity, because of what it looks like in Pascal's triangle. You can prove from summing $$ \binom{n}{k} = \binom{n+1}{k+1}-\binom{n}{k+1} $$ from $n=1$ to $N$ and noting most of the terms on the right-hand side cancel.

Answer 3

We wish to prove that $$\sum_{0 \leq k \leq n} \binom{k}{m} = \binom{n + 1}{m + 1}$$

The expression $\binom{n + 1}{m + 1}$ is the number of ways of selecting a subset of $m + 1$ elements from the set $S = \{0, 1, 2, \ldots, n\}$.

The expression $\binom{k}{m}$ is the number of subsets of $S$ with $m + 1$ elements with largest element $k$ since there are $k$ elements of $S$ less than $k$ from which the remaining $m$ elements of the subset must be selected. Summing over all possible values of $k$ yields the identity.