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?

  • 1
    $\begingroup$ You can use the result of the user drhab below and proof e.g. by induction. $\endgroup$
    – user90369
    Mar 28, 2019 at 16:53

2 Answers 2


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*}


  • 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .