How to determine the value of $\sum_{k = 0}^{r} \binom{n + k - 1}{k}$?

Question

How to determine the value of $\displaystyle \sum_{k=0}^{r} \binom{n+k-1}{k}$?

By what rule/principle of summation you use to solve the problem given above? I have modified some theorems to use, but gives no result at last. There must be some ways I don't find it yet, which in reality may glance it. Could you help me?

Answer 1

Note that

$$\binom{n+k-1}{k}=\binom{n+k-1}{n-1}$$

then

$$\sum_{k=0}^{r} \binom{n+k-1}{k}=\sum_{k=0}^{r} \binom{n+k-1}{n-1}$$

then use Hockey-stick identity that is

$$\sum_{k=0}^{r} \binom{n+k-1}{n-1}=\sum_{k=n-1}^{n+r-1} \binom{k}{n-1}={{n+r}\choose{n}} $$

Answer 2

By the Binomial Theorem for a negative exponent, $$(1-x)^{-n}=\sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k$$ so $$ (1-x)^{-n-1} = (1-x)^{-1} \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k $$ Applying the Binomial Theorem again (twice), $$\sum_{k=0}^{\infty} \binom{n+k}{k} x^k =\sum_{j=0}^{\infty}x^j \cdot \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k$$ The coefficient of $x^r$ on the left-hand side of the equation above is $$\binom{n+r}{r}$$ while the coefficient on the right-hand side is $$\sum_{k=0}^r \binom{n+k-1}{k}$$ so we must have $$\binom{n+r}{r}=\sum_{k=0}^r \binom{n+k-1}{k}$$

Answer 3

We claim that $$ \sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1}\tag{1}. $$ Indeed the RHS counts the number of $k+1$ element subsets of $\{0,1\dotsc,n\}$. The LHS counts the same thing by classifying the subsets based on their maximum element. For $0\leq i\leq n$, there are $\binom{i}{k}$ subsets of $\{0,1\dotsc,n\}$ whose maximum element is $i$.

Now note that $$ \sum_{k=0}^{r} \binom{n+k-1}{k}=\sum_{k=0}^{r} \binom{n+k-1}{n-1}=\sum_{u=n-1}^{n+r-1}\binom{u}{n-1}=\binom{n+r}{n} $$ by (1).

Answer 4

First, lets prove $ \sum_{i=0}^{n} \binom{i}{k} = \binom{n+1}{k+1}$

I intend to provide an algebraic proof based on simple generating functions such as the geometric series, here you go :

Note that $[x^k]f(x)$ denotes the coefficient of $x^k$ in $f(x)$. Now, we need :

$([x^k](1+x)^0)+([x^k](1+x)^1)+...+([x^k](1+x)^n)$ , as coefficient of $x^k$ in $(1+x)^i$ is $\binom{i}{k}$ .

$ = [x^k] \sum_{i=0}^{n}(1+x)^i $ .

Now, we can see $ \sum_{i=0}^{n}(1+x)^i$ is a geometric series. So,

$= [x^k] \frac{1-(1+x)^{n+1}}{(1-(1+x))} $

$ = [x^k] \frac{(1+x)^{n+1}-1}{x}$

$ = [x^k] (x^{-1}(1+x)^{n+1})+[x^k]x^{-1}$

$ = [x^k]x^{-1}(1+x)^{n+1}$

$ = \binom{n+1}{k+1}$, by binomial theorem.

Now, to prove for $ \sum_{k=0}^{r} \binom{n+k-1}{k}$, note that we just need to push the geometric series accordingly, like :

$ \sum_{i=n-1}^{n+r-1} (1+x)^i$, and then follow the same procedure.