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


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


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.