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?
On
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$.
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}$$