Combinatorial identity: summation of stars and bars I noticed that the following identity for a summation of stars and bars held for specific $k$ but I was wondering if someone could provide a general proof via combinatorics or algebraic manipulation. I wouldn't be surprised if this is a known result; it looks very similar to the Hockey Stick identity.
$$\sum_{i=0}^k {d+i-1 \choose d-1} = {d+k \choose k}$$
The left can be immediately rewritten as $\sum_{i=0}^k {d+i-1 \choose i}$ if it helps inspire intuition.
 A: Consider the set $S=\{1,2,\ldots,d,d+1,\ldots,d+k\}$. The right hand side gives us the number of ways selecting a subset of $S$ of $d$ elements.
If we choose such a subset $X$ of $S$ of $d$ elements, the highest element of $X$ can be $d,d+1,\ldots,d+k$. If the highest element of $X$ is $d+i$ then we can find $d-1$ more elements of $X$ from $\{1,2,\ldots,d+i-1\}$. The number of ways that we can do that is ${d+i-1\choose d-1}$. By running $i$ from $0$ to $k$ we have the left hand side of the identity.
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{\sum_{i = 0}^{k}{d + i - 1 \choose d - 1} =
{d + k \choose k}:\ {\LARGE ?}}$.

\begin{align}
&\bbox[10px,#ffd]{\sum_{i = 0}^{k}{d + i - 1 \choose d - 1}} =
\sum_{i = 0}^{k}{d + i - 1 \choose i}
\\[5mm] = &\
\sum_{i = 0}^{k}{-\bracks{d + i - 1} + i - 1 \choose i}
\pars{-1}^{i} =
\sum_{i = 0}^{k}\pars{-1}^{i}{-d \choose i}
\\[5mm] = &\
\sum_{i = 0}^{k}\pars{-1}^{i}\bracks{z^{i}}\pars{1 + z}^{-d} =
\bracks{z^{0}}\pars{1 + z}^{-d}
\sum_{i = 0}^{k}\pars{-\,{1 \over z}}^{i}
\\[5mm] = &\
\bracks{z^{0}}\pars{1 + z}^{-d}\,
{\pars{-1/z}^{k + 1} - 1 \over \pars{-1/z} - 1}
\\[5mm] = &\
\bracks{z^{0}}\pars{1 + z}^{-d}\,
{z \over z^{k + 1}}\,{\pars{-1}^{k + 1} - z^{k + 1} \over -1 - z}
\\[5mm] = &\
\bracks{z^{k}}\pars{1 + z}^{-d - 1}\,
\bracks{z^{k + 1} - \pars{-1}^{k + 1}} =
\pars{-1}^{k}\bracks{z^{k}}\pars{1 + z}^{-d - 1}
\\[5mm] = &\
\pars{-1}^{k}{-d - 1 \choose k} =
\pars{-1}^{k}\braces{%
{-\bracks{-d - 1} + k - 1 \choose k}\pars{-1}^{k}}
\\[5mm] = &\ \bbx{d + k \choose k} \\ &
\end{align}
A: Starting from
$$\sum_{q=0}^k {d+q-1\choose d-1}$$
we get
$$\sum_{q\ge 0} {d+q-1\choose d-1} [[0\le q\le k]]
= \sum_{q\ge 0} {d+q-1\choose d-1} [z^k] \frac{z^q}{1-z}
\\ = [z^k] \frac{1}{1-z} \sum_{q\ge 0} {d+q-1\choose d-1} z^q
= [z^k] \frac{1}{1-z} \frac{1}{(1-z)^d}
\\ = [z^k] \frac{1}{(1-z)^{d+1}}
= {d+k\choose k}.$$
