1

Consider:

$$\sum\limits_{t = 0}^k {\left( {\begin{array}{*{20}{c}} {n + t} \\ n \\ \end{array}} \right)} = \left( {\begin{array}{*{20}{c}} {n + k + 1} \\ {n + 1} \\ \end{array}} \right)$$

First, I'm not supposed to solve it algebraically. Instead, I need to use combinatorics rationalization.

The right-hand side can be described as the number of possibilities to choose a $n+k+1$ long binary word containing $n+1$ $1$'s.

Now, If we showed the left-hand side can also describe this, then we would solve the problem.

I understood the left-hand side can be described as follows:

First, place $1$ at one of the cells between $n$ and $n+k+1$.
Every cell right to it would contain $0$.
Now choose $n$ other cells to be $1$.

I don't understand it completely why is it the same as the right-hand side.
Be glad for clarifications.

Thanks.

AnnieOK
  • 2,920
  • See http://math.stackexchange.com/questions/704710/how-to-prove-sum-k-0m-binomnkn-binomnm1n1-without-induction/704715#704715 – r9m Mar 16 '14 at 08:58
  • I understand the technical process but why is it summed up to the same number of possibilities? – AnnieOK Mar 16 '14 at 09:05
  • 1
    when you pick up a sample of size $n+1$ from $S$ it always has a largest number. The idea is to partition the $\binom{n+m+1}{n+1}$ ways of choosing according to the largest number that is chosen. (If the largest number of two collection samples is different it means the collections are different .. so the expression in LHS is a partition of $\binom{n+m+1}{n+1}$) – r9m Mar 16 '14 at 09:13
  • Got it. Thanks! – AnnieOK Mar 16 '14 at 09:18
  • 1
    this is called hockey stick identity: http://www.artofproblemsolving.com/Wiki/index.php/Combinatorial_identity#Hockey-Stick_Identity – Alex Mar 16 '14 at 09:28

1 Answers1

1

Let $A_0$ be the set of words that have length $n+k+1$ and $n+1$ ones. There are two kinds of elements in $A_0$: the words that end with $1$ and the words that don't.

Let $B_0$ be the set of the words that end with $1$. There are $\binom{n+k}n$ elements in $B_0$, that is the last term of the sum at the left part of the identity. The complement $A_1=A_0-B_0$ contains $\binom{n+k}{n+1}$ elements: we have decreased the upper term of the binomial coefficient. Now use induction.

ajotatxe
  • 65,084