5
$\begingroup$

Question: Is there a closed form for the summation $$\sum_{k=0}^p \binom{k+m-1}{m-1}?$$

By writing out the summation, we have $$\binom{m-1}{m-1} + \binom{m}{m-1} + \binom{m+1}{m-1}+...+\binom{p+m-2}{m-1}+\binom{p+m-1}{m-1}$$ $$ = 1 + m + \frac{m(m+1)}{2} + \frac{m(m+1)(m+2)}{3!}+...+\frac{m(m+1)...(m+(k-1))}{k!}+...+\frac{m(m+1)...(m+(p-1))}{p!}.$$ However, I do not see a closed form for it.

$\endgroup$
  • 3
    $\begingroup$ $\dbinom{p+m}{m}$. See the hockey-stick identity. $\endgroup$ – darij grinberg Feb 15 '18 at 2:25
  • 2
    $\begingroup$ Compare with Pascal's triangle to see hockey stick identity showing up. :-) $\endgroup$ – Rohan Shinde Feb 15 '18 at 3:13
6
$\begingroup$

In the summation $$\sum_{k=0}^p \binom{k+m-1}{m-1},$$ make a change of variable by letting $i = k + m - 1$. When $k = 0$, $i = m-1$; when $k = p$, $i = p+m-1$. The required summation becomes $$\sum_{i=m-1}^{p+m-1} \binom{i}{m-1}.$$ Apply the Hockey-stick identity $${\sum _{i=r}^{n}{i \choose r}={n+1 \choose r+1}}$$ with $n = p+m-1$ and $r = m - 1$, so that $$\sum_{k=0}^p \binom{k+m-1}{m-1} = \sum_{i=m-1}^{p+m-1} \binom{i}{m-1} = {p+m \choose m}.$$

| cite | improve this answer | |
$\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.