Give the combinatorial proof of the identity $\sum\limits_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$ Given the identity
$$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$
Need to give a combinatorial proof 
a) in terms of subsets
b) by interpreting the parts in terms of compositions of integers
I should not use induction or any other ways...
Please help.
 A: HINTS:


*

*Consider a $k$-element subset of $[n+k]=\{1,\dots,n+k\}$; it has a maximum element, which can be anything from $k$ through $n+k$. How many such subsets are there with maximum element $k+i$ for $i=0,\dots,n$?

*There are $\binom{k-1+i}{k-1}$ compositions of $k+i$ with $k$ terms. There are $\binom{n+k}k$ compositions of $n+k+1$ with $k+1$ terms.
A: Use $\binom{k}{r} = \binom{k-1}{r} + \binom {k-1}{r-1}$ repeatedly on the expansion of sum.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Leftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\color{#f00}{\sum_{j = 0}^{n}{k - 1 + j \choose k - 1}} & =
\sum_{j = 0}^{n}{k - 1 + j \choose j} =
\sum_{j = 0}^{n}{-k + 1 - j + j - 1 \choose j}\pars{-1}^{j} =
\sum_{j = 0}^{n}{-k \choose j}\pars{-1}^{j}
\\[3mm] & =
\sum_{j = -\infty}^{n}{-k \choose j}\pars{-1}^{j} =
\sum_{j = -n}^{\infty}{-k \choose -j}\pars{-1}^{-j} =
\sum_{j = 0}^{\infty}{-k \choose n - j}\pars{-1}^{j + n} =
\\[3mm] & =
\pars{-1}^{n}\sum_{j = 0}^{\infty}\pars{-1}^{j}\oint_{\verts{z} = 1^{-}}
{\pars{1 + z}^{-k} \over z^{n - j + 1}}\,{\dd z \over 2\pi\ic}
\\[3mm] & =
\pars{-1}^{n}\oint_{\verts{z} = 1^{-}}
{\pars{1 + z}^{-k} \over z^{n + 1}}\sum_{j = 0}^{\infty}\pars{-z}^{j}
\,{\dd z \over 2\pi\ic} =
\pars{-1}^{n}\oint_{\verts{z} = 1^{-}}
{\pars{1 + z}^{-k - 1} \over z^{n + 1}}\,{\dd z \over 2\pi\ic}
\\[3mm] & =
\pars{-1}^{n}{-k - 1 \choose n} =
\pars{-1}^{n}{k + 1 + n - 1 \choose n}\pars{-1}^{n} =
{n + k \choose n} = \color{#f00}{n + k \choose k}
\end{align}
A: Alternatively, both the LHS and RHS count the number of non-negative integer solutions to the inequality $\displaystyle \sum_{r=0}^{k}x_{r} \leq n$ which can be readily seen via the double counting below:
1) From the LHS, this inequality can be written as $n+1$ equalities of the form $\displaystyle \sum_{r=0}^{k}x_{r} = i$ where $i=0,1, \ldots n$, each of which have $\displaystyle \binom{k+i-1}{k-1}$ solutions in the non-negative integers and hence the total number of solutions is $\displaystyle \sum_{i=0}^{n}\binom{k+i-1}{k-1}$.
2) From the RHS viewpoint, we can convert this inequality into an equality by adding a slack variable $x_{k+1}$ on the LHS to obtain $\displaystyle \sum_{r=0}^{k+1}x_{r} = n$ which of course has $\displaystyle \binom{n+k}{k}$ solutions in the non-negative integers.
