# binomial sum binomial (a + k , a)

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.

• This is certainly a duplicate you might look in the website before posting such questions – Elaqqad Apr 26 '15 at 16:50
• @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...) – Chappers Apr 26 '15 at 16:52
• 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. – Lucian Apr 26 '15 at 17:34

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