3
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.