Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
    
I understand the technical process but why is it summed up to the same number of possibilities? –  AnnieOK Mar 16 at 9: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 at 9:13
    
Got it. Thanks! –  AnnieOK Mar 16 at 9:18
1  
this is called hockey stick identity: artofproblemsolving.com/Wiki/index.php/… –  Alex Mar 16 at 9:28

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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