# Binomial coefficients sum

Let $$n \geq 1$$ and $$N \geq 1$$ be integers. I am interested in the sum $$\sum_{k=0}^{N} \binom{k + n-1}{n - 1}$$ I don't know how to tackle this. I've tried using the definition of $$\binom{n}{k}$$ but did not get anywhere.

Could anyone suggest a method of attack for evaluating this sum?

• You can use the result of the user drhab below and proof e.g. by induction. – user90369 Mar 28 '19 at 16:53

In general we have:$$\sum_{i+j=k}\binom{i}{r}\binom{j}{s}=\binom{k+1}{r+s+1}$$

For a proof of that see here.

Setting $$s=0$$ we get:$$\sum_{i=r}^k\binom{i}{r}=\binom{k+1}{r+1}$$ which get the looks of the summation in your question.

Based on this we find:$$\sum_{k=0}^{N}\binom{k+n-1}{n-1}=\sum_{k=n-1}^{N+n-1}\binom{k}{n-1}=\binom{N+n}{n}$$

We use the coefficient of operator $$[z^k]$$ to denote the coefficient of $$z^k$$ in a series. This way we can write for instance \begin{align*} \binom{n}{k}=[z^k](1+z)^n\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^N\binom{k+n-1}{n-1}}&=\sum_{k=0}^N[z^{n-1}](1+z)^{k+n-1}\tag{2}\\ &=[z^{n-1}](1+z)^{n-1}\sum_{k=0}^N(1+z)^{k}\tag{3}\\ &=[z^{n-1}](1+z)^{n-1}\frac{(1+z)^{N+1}-1}{(1+z)-1}\tag{4}\\ &=[z^n]\left((1+z)^{N+n}-(1+z)^{n-1}\right)\tag{5}\\ &\,\,\color{blue}{=\binom{N+n}{n}}\tag{6} \end{align*}

Comment:

• In (2) we apply the coefficient of operator according to (1).

• In (3) we factor out terms which do not depend on $$k$$.

• In (4) we use the finite geometric series formula.

• In (5) we collect terms and apply the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$.

• In (6) we select the coefficient of $$z^n$$.