# Algebraic proof that $\binom{n+k-1}{k} = \sum\limits_{i=0}^k \binom{(n-1)+(k-i)-1}{k-i}$

Prove (algebraically) that $$f_k(n) = \binom{n+k-1}{k} = \sum\limits_{i=0}^k \binom{(n-1)+(k-i)-1}{k-i} = \sum\limits_{i=0}^k f_{k-i}(n-1)$$ for $$n \geq 2$$ and that $$f_k(1) = 1$$ for all $$k$$.

Then, show that if $$f_k(n) = \sum\limits_{i=0}^k f_{k-i}(n-1)$$ for $$n\geq 2$$ and $$f_k(1) = 1$$ for all $$k$$, then $$f_k(n) = \binom{n+k-1}{k}$$.

Attempting the first one: it's easy to see that $$f_k(1) = 1$$ for all $$k$$ by substitution. I'm not so sure about what to so with the summation of binomial coefficients. I'm sure there's a way to use $$\sum\limits_{i=0}^k \binom{k}{i}x^i = (x+1)^k$$, either directly or in a double-sum, but I'm not sure how to manipulate the summand into such a form.

For the second one: after the first one is solved, it's trivial, since they agree for $$n=1$$ and if they agree for $$n = N-1$$, they must agree for $$n=N$$ by the first identity. So the main difficulty in this problem is coming from the first part.

Edit: I should also note that I can understand this identity by relating $$f_k(n)$$ with the number of ways to choose an ordered $$n$$-tuple of numbers adding to $$k$$, or equivalently the number of $$k$$-degree terms in an $$n$$-dimensional polynomial. However, my attempts converting that intuition into an algebraic proof haven't gone anywhere.

• $f_k(n)$ is the number of non negative integer solutions to $x_1+x_2+\cdots +x_n = k$. Now $f_{k-i}(n-1)$ counts the number of those solutions in which $x_n = i$. The identity follows. – Muralidharan Dec 7 '18 at 1:17
• so fix $x_n=i$ and solve $x_1+x_2+\cdots+x_{n-1} = k-i$. Nice @Muralidharan :) – rsadhvika Dec 7 '18 at 1:21
• @Muralidharan This is exactly what I know, but how can I reduce this argument into a direct algebraic proof of the identity? – AlexanderJ93 Dec 7 '18 at 1:26
• @AlexanderJ93 I think you may simply use the identity $$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$$ – rsadhvika Dec 7 '18 at 1:35
• $$\binom{n+k-1}{k} = \binom{n+(k-1)-1}{k} + \binom{n+(k-1)-1}{k-1} = \cdots$$ – rsadhvika Dec 7 '18 at 1:37

We have \eqalign{ & \sum\limits_{0\, \le \,i\, \le \,k} {\left( \matrix{ n - 2 + k - i \cr k - i \cr} \right)} = \cr & = \sum\limits_{0\, \le \,j\, \le \,k} {\left( \matrix{ n - 2 + j \cr j \cr} \right)} = \quad \quad (1) \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( \matrix{ k - j \cr k - j \cr} \right)\left( \matrix{ n - 2 + j \cr j \cr} \right)} = \quad \quad (2) \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( { - 1} \right)^{\,k - j} \left( \matrix{ - 1 \cr k - j \cr} \right)\left( { - 1} \right)^{\,j} \left( \matrix{ - n + 1 \cr j \cr} \right)} = \quad \quad (3)\cr & = \left( { - 1} \right)^{\,k} \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\left( \matrix{ - 1 \cr k - j \cr} \right)\left( \matrix{ - n + 1 \cr j \cr} \right)} = \quad \quad (4) \cr & = \left( { - 1} \right)^{\,k} \left( \matrix{ - n \cr k \cr} \right) = \quad \quad (5) \cr & = \left( \matrix{ n + k - 1 \cr k \cr} \right) \quad \quad (6) \cr} where:
(1) change of index
(2) replacing sum bounds with binomial
(3) upper negation
(5) convolution (6) upper negation

Note to (2):

The binomial $$\binom{k-j}{k-j}$$ equals $$1$$ for $$j \le k$$ and is null for $$k.
Therefore we can use it to replace the upper bound for $$j$$ in the sum.
On the other side, the second binomial intrinsically ensures for the lower bound $$0 \le j$$.
Therefore we can leave the index free to take all values: that's why I indicated the bound in brackets.
That's a "trick" many time useful in manipulating binomial sums, and I am in debt to the renowned "Concrete Mathematics" for teaching that.

• This is great, I'm just not understanding what's actually happening in (2). – AlexanderJ93 Dec 7 '18 at 1:48
• @AlexanderJ93: you are not probably alone in that, so I included a note to explain such a useful "trick" – G Cab Dec 7 '18 at 2:01
• Not quite. The binomial $\dbinom{k-j}{k-j}$ is not $0$ when $j <0$; you need the other binomial for that. – darij grinberg Dec 7 '18 at 2:09
• @darijgrinberg: oh yes, you are fully right : I shall amend the description. Thanks for signalling such a mistake. – G Cab Dec 7 '18 at 2:29

Let $$[x^j]:f(x)$$ denote the coefficient of $$x^j$$ of the function $$f(x)$$. We have $$\begin{eqnarray*} \sum_{i=0}^{k} \binom{n+k-i-2}{k-i} &=& \sum_{i=0}^{k} [x^{k-i}]: (1+x)^{n+k-i-2} \\ &=& [x^k]: \sum_{i=0}^{k} (1+x)^{n+k-2} \left(\frac{x}{x+1} \right)^i \\ &=& [x^k]: (1+x)^{n+k-2} \sum_{i=0}^{\infty} \left(\frac{x}{x+1} \right)^i \\ &=& [x^k]: (1+x)^{n+k-1} = \binom{n+k-1}{k}. \end{eqnarray*}$$