How can i prove the identity $\sum_{k=0}^{n} \binom{x+k}{k}=\binom{x+n+1}{n}$ I'm having a difficult time understanding how to give a combinatorics proof of the identity $$\sum_{k=0}^{n} \binom{x+k}{k}=\binom{x+n+1}{n}$$
 A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \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{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#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}$
$\ds{\bbox[5px,#ffd]{\sum_{k = 0}^{n}{x + k \choose k} =
{x + n + 1 \choose n}}:\ {\Large ?}}$.

\begin{align}
\bbox[5px,#ffd]{\sum_{k = 0}^{n}{x + k \choose k}} & =
\sum_{k = 0}^{n}\bracks{z^{k}}\pars{1 + z}^{x + k} =
\bracks{z^{0}}\pars{1 + z}^{x}\sum_{k = 0}^{n}\pars{1 + z \over z}^{k}
\\[5mm] & =
\bracks{z^{0}}\pars{1 + z}^{x}\,
{\pars{1 + z}^{n + 1}/z^{n + 1} - 1 \over \pars{1 + z}/z - 1}
\\[5mm] = &\
\bracks{z^{0}}\pars{1 + z}^{x}\,{1 \over z^{n}}
\bracks{\pars{1 + z}^{n + 1} - z^{n + 1}}
\\[5mm] = &\
\bracks{z^{n}}\pars{1 + z}^{x + n + 1} =
\bbx{\large{x + n + 1 \choose n}} \\ &
\end{align}
A: This can be proved by noting that the sum counts the number of subsets  of $\{1,2,\cdots,x+n\}$ of size $x$, together with an integer $k\in \{0,1,2,\cdots n\}$ such that $x+k$ is at least the largest element of the subset.  Seperating into the two cases where $k$ equals the largest element, and where it is strictly greater than the largest element, we get:
\begin{eqnarray*}\sum_{k=0}^{n} \binom{x+k}{k}&=&\sum_{k=0}^{n} \binom{x+k}{x}\\ &=&\binom{x+n}{x}+\binom{x+n}{x+1}\\&=&\binom{x+n+1}{x+1}\\&=&\binom{x+n+1}{n}.\end{eqnarray*}
