# 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.

• If you replace the RHS with $\binom{d+k}d$, then this is literally the Hockey Stick identity. – Mike Earnest Dec 13 '18 at 19:19

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.

$$\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}

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