0
$\begingroup$

I am having trouble creating a proof for the below equation to show that they are in fact equal to one another. n and k are positive integers.

$$ \left(\!\!{n\choose k}\!\!\right) = \sum_{i=0}^{k}\ \left(\!\!{n-1\choose i}\!\!\right)$$

Any help would be greatly appreciated!

Overall I have tried multiple ways to relate it to something similar like the below to help get closer to something less complex, $$\sum_{i=0}^{k}\ \left(\!\!{n-1\choose i}\!\!\right) = {n+k -1\choose k}$$

however I can't seem to get anywhere that makes any sense in regards to proving the two first equations are equal to one another.

$\endgroup$
0
$\begingroup$

One approach is to argue combinatorially. Suppose that you want to choose a $k$-element multiset from the set $[n]=\{1,\ldots,n\}$. Let $\mathscr{M}$ be the family of all such multisets, and for $\ell=0,\ldots,k$ let $\mathscr{M}_\ell$ be the set of multisets in $\mathscr{M}$ that have $\ell$ copies of $n$. If $M\in\mathscr{M}_\ell$, then what remains of $M$ when you throw out the copies of $n$ is a multiset of cardinality $k-\ell$ chosen from the set $[n-1]$, so

$$|\mathscr{M}_\ell|=\left(\!\!\binom{n-1}{k-\ell}\!\!\right)\;,$$

and of course

$$|\mathscr{M}|=\left(\!\!\binom{n}k\!\!\right)\;.$$

Can you finish it from here?

Another possibility is to reduce it to binomial coefficients and try to show that

$$\binom{n+k-1}k=\sum_{i=0}^k\binom{n-2+i}i\;.$$

This can be rewritten as

$$\sum_{i=0}^k\binom{n-2+i}{n-2}=\binom{n-1+k}{n-1}\;,$$

which is sometimes known as the hockey stick identity and has several proofs here.

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