Anyone know a way to compute such a sum : $$S = \sum_{k=0}^{n}\binom{a+k}{a} $$ I encountered this sum in a problem in which $a=7, n=7$. In this case the sum can be computed by hand, but I was interested in fiding a general formula.For anyone who might be interested, I was computing the number of increasing sequences of length 8 with terms between 1 and 10.

  • 1
    $\begingroup$ This is certainly a duplicate you might look in the website before posting such questions $\endgroup$ – Elaqqad Apr 26 '15 at 16:50
  • $\begingroup$ @Elaqqad This duplicate is becoming ridiculously common... I think this is something like the sixth instance I've seen in the last month. If only we had sticky questions... (Or maybe the matching algorithm for duplicates is bad at finding these...) $\endgroup$ – Chappers Apr 26 '15 at 16:52
  • $\begingroup$ As an aside, $~\displaystyle\sum_{k=0}^\infty\binom{a+k}{a}x^k ~=~ \sum_{k=0}^\infty\binom{a+k}{k}x^k ~=~ \dfrac1{(1-x)^{a+1}}~.~$ See binomial series. $\endgroup$ – Lucian Apr 26 '15 at 17:34

I just finish the work started by @Chappers

$$\begin{align}\sum_{k=0}^n\binom{a+k}{a}&=\sum_{k=0}^n\binom{a+k+1}{a+1}-\sum_{k=0}^n\binom{a+k}{a+1}\\ &=\sum_{k=1}^{n+1}\binom{a+k}{a+1}-\sum_{k=0}^n\binom{a+k}{a+1}\\ &=\binom{a+n+1}{a+1}-\binom{a+1}{a+1}\\ &=\binom{a+n+1}{n}-1 \end{align}$$


Note the identity, derived from Pascal's identity, $$ \binom{a+k+1}{a+1}-\binom{a+k}{a+1} = \binom{a+k}{a}, $$ and then make the sum telescope.


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.