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.
 A: 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.  
A: 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*}
