0
$\begingroup$

$ \textbf{Question}: $ Let $ n $ and $ k $ be nonnegative integers such that $ n \ge 1, $ then $$ \displaystyle \binom{n - 1}{0} + \binom{n}{1} + \binom{n + 1}{2} + \dots + \binom{n + k - 1}{k} = \binom{n + k}{k} \; \; \; \; \; \; \; (\ast) $$

I ran into this problem while trying to prove the formula involving counting multisets. In general, the number of ways to form $ k $-elements multisets from an $ n $-elements set, denoted by $ M(n, k) $ where $ n \ge 1, $ is $ \displaystyle \binom{n + k - 1}{k}. $ I am attempting to prove this fact using proof by strong induction on $ n, $ which eventually leads to proving that $ (\ast) $ is true, but I currently stuck on proving $ (\ast). $ Can someone provide me some hints to tackle $ (\ast)? $

Also, $ (\ast) $ implies that $ \displaystyle M(n + 1, k) = \sum_{i = 0}^{k} \; M(n, i). $

$\endgroup$
  • 1
    $\begingroup$ This is the hockey stick identity. $\endgroup$ – Lee David Chung Lin Sep 9 '16 at 3:35
  • $\begingroup$ @LeeDavidChungLin How so? I found the identity you mention here (artofproblemsolving.com/wiki/index.php/Combinatorial_identity) but it doesn't seem to match the formula in $ (\ast) $ $\endgroup$ – user298251 Sep 9 '16 at 5:37
  • 1
    $\begingroup$ $\text{Your expression} = {n-1 \choose n-1} + {n \choose n-1} + {n+1 \choose n-1} + \ldots + {n+k-1 \choose n-1}$ so your $n-1$ is that page's $r$ and their $n$ is your $n+k-1$. $\endgroup$ – Lee David Chung Lin Sep 9 '16 at 5:51
  • $\begingroup$ Oh yes thank you for pointing that out! I actually used that identity you mentioned earlier in my induction proof to arrive at $ (\ast), $ but this time I didn't recognize that identity. $\endgroup$ – user298251 Sep 9 '16 at 6:09
  • $\begingroup$ yeah, you had your last line of the post right there since the beginning, which of course is another equivalent form. $\endgroup$ – Lee David Chung Lin Sep 9 '16 at 6:39
0
$\begingroup$

So $$\binom{n+k}{k}=\binom{n+(k+1)-1}{(k+1)-1}$$ which is the number of ways to create $n$ with $k+1$ summands(allowing $0$ as a summand).

So, lets denote $A_{n,k+1}$ the sets of those tuples(each elements in the tuple is like a summand).

So, you have to prove that $A_{n,k+1}=\phi(\bigcup _{i=0}^k A_{n-1,i+1})$ where $\phi$ is defined as $\phi ((x_1,x_2,\ldots ,x_r))=(x_1,x_2,\ldots ,x_r+1,\underbrace {0,\ldots ,0}_{\text{$k+1-r$ times}})$. By adding principle, you will get your resut.

$\endgroup$
0
$\begingroup$

The left hand side is the coefficient of $x^k$ in \begin{align*} x^k(1+x)^{n-1}+x^{k-1}(1+x)^n &+ \cdots + (1+x)^{n+k-1} = x^k(1+x)^{n-1}\frac{\left(1-\left(\frac{1+x}{x}\right)^{k+1}\right)}{1-\frac{1+x}{x}}\\ &=x^k(1+x)^{n-1}\frac{(1+x)^{k+1}-x^{k+1}}{x^{k}}\\ &= (1+x)^{n+k} - x^{k+1}(1+x)^{n-1} \end{align*} and hence equals $\binom{n+k}{k}$.

$\endgroup$
0
$\begingroup$

HINT: $\binom{n-1+i}i=\binom{n-1+i}{n-1}$ is the number of $n$-element subsets of $\{1,2,\ldots,n+k\}$ whose largest element is $n+i$. What is $\binom{n+k}n$?

$\endgroup$

Your Answer

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