1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It follows from Pascals equality $\endgroup$ – Jakobian Jun 21 '18 at 22:33
  • $\begingroup$ @Adam From Wikipedia, I got $\binom{N+1}{7} = \binom{N}{6} + \binom{N}{7}$. This is not exactly what the equation says:< $\endgroup$ – James Wang Jun 21 '18 at 22:40
  • $\begingroup$ If you use it repeatedly then you get your equation $\endgroup$ – Jakobian Jun 21 '18 at 22:43
  • $\begingroup$ @Adam Got it! Thanks! $\endgroup$ – James Wang Jun 21 '18 at 22:45
1
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.