4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $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. $\endgroup$ – Muralidharan Dec 7 '18 at 1:17
  • $\begingroup$ so fix $x_n=i$ and solve $x_1+x_2+\cdots+x_{n-1} = k-i$. Nice @Muralidharan :) $\endgroup$ – rsadhvika Dec 7 '18 at 1:21
  • $\begingroup$ @Muralidharan This is exactly what I know, but how can I reduce this argument into a direct algebraic proof of the identity? $\endgroup$ – AlexanderJ93 Dec 7 '18 at 1:26
  • $\begingroup$ @AlexanderJ93 I think you may simply use the identity $$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$$ $\endgroup$ – rsadhvika Dec 7 '18 at 1:35
  • $\begingroup$ $$\binom{n+k-1}{k} = \binom{n+(k-1)-1}{k} + \binom{n+(k-1)-1}{k-1} = \cdots $$ $\endgroup$ – rsadhvika Dec 7 '18 at 1:37
3
$\begingroup$

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

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

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

$\endgroup$

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.