4
$\begingroup$

For $k, l \in \mathbb N$ $$\sum_{i=0}^k\sum_{j=0}^l\binom{i+j}i=\binom{k+l+2}{k+1}-1$$ How can I prove this?

I thought some ideas with Pascal's triangle, counting paths on the grid and simple deformation of the formula.

It can be checked here (wolframalpha).

If the proof is difficult, please let me know the main idea.

Sorry for my poor English.

Thank you.

EDIT: I got the great and short proof using Hockey-stick identity by Anubhab Ghosal, but because of this form, I could also get the Robert Z's specialized answer. Then I don't think it is fully duplicate.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) $\endgroup$ – user10354138 Dec 12 '18 at 10:07
  • $\begingroup$ @user10354138 The double sum is related Hockey-Stick Identity but it is not a duplicate of the linked question. Moreover OP asks for a combinatorial proof (counting paths...) $\endgroup$ – Robert Z Dec 12 '18 at 11:30
  • $\begingroup$ @RobertZ The OP didn't ask for a combinatorial proof, only for a proof ("How can I prove this?" in the quote, not "How can I prove this combinatorially?"). It can be proved by applying the linked result twice, so it is a duplicate. $\endgroup$ – user10354138 Dec 12 '18 at 13:18
  • $\begingroup$ @user10354138 Fine. So we have a different opinion on this matter. Have a nice day. $\endgroup$ – Robert Z Dec 12 '18 at 15:48
3
$\begingroup$

Your idea about a combinatorial proof which is related to counting paths in a grid is a good one!

The binomial $\binom{i+j}i$ counts the paths on the grid from $(0,0)$ to $(i,j)$ moving only right or up. So the double sum $$\sum_{i=0}^k\sum_{j=0}^l\binom{i+j}i-1$$ counts the number of all such paths from $(0,0)$ to any vertex inside the rectangle $(0,k)\times (0,l)$ different from $(0,0)$.

Now consider the paths from $(0,0)$ to $(k+1,l+1)$ different from $$(0,0)\to (0,l+1)\to (k+1,l+1)\quad\text{and}\quad (0,0)\to (k+1,0)\to (k+1,l+1)$$ which are $$\binom{k+l+2}{k+1}-2.$$

Now any path of the first kind can be completed to a path of the second kind by changing direction, going to the boundary of the rectangle $(0,k+1)\times(0,l+1)$ and then moving to the corner $(k+1,l+1)$ along the side.

Is this a bijection between the first set of paths and the second one?

$\endgroup$
5
$\begingroup$

$$\displaystyle\sum_{i=0}^k\sum_{j=0}^l\binom{i+j}i=\sum_{i=0}^k\sum_{j=i}^{i+l}\binom{j}i=\sum_{i=0}^k\binom{i+l+1}{i+1} \ ^{[1]}$$

$$=\sum_{i=0}^k\binom{i+l+1}{l}=\sum_{i=l}^{k+l+1}\binom{i}{l}−1=\binom{k+l+2}{k+1}-1\ ^{[1]}$$

1. Hockey-Stick Identity

$\endgroup$
0
$\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}\sum_{j = 0}^{\ell} {i + j \choose i} = {k + \ell + 2 \choose k + 1} - 1:\ {\LARGE ?}.\qquad k, \ell \in \mathbb{N}}$.

\begin{align} &\bbox[10px,#ffd]{\sum_{i = 0}^{k}\sum_{j = 0}^{\ell} {i + j \choose i}} = \sum_{i = 0}^{k}\sum_{j = 0}^{\ell}{i + j \choose j} = \sum_{i = 0}^{k}\sum_{j = 0}^{\ell}{-i - 1 \choose j} \pars{-1}^{\,j} \\[5mm] = &\ \sum_{i = 0}^{k}\sum_{j = 0}^{\ell}\pars{-1}^{\,j} \bracks{z^{\, j}}\pars{1 + z}^{-i - 1} = \sum_{i = 0}^{k}\sum_{j = 0}^{\ell}\pars{-1}^{\,j} \bracks{z^{0}}{1 \over z^{\, j}}\,\pars{1 + z}^{-i - 1} \\[5mm] = &\ \bracks{z^{0}}\sum_{i = 0}^{k}\pars{1 \over 1 + z}^{i + 1} \sum_{j = 0}^{\ell}\pars{-\,{1 \over z}}^{\,j} \\[5mm] = &\ \bracks{z^{0}}\braces{{1 \over 1 + z}\, {\bracks{1/\pars{1 + z}}^{k + 1} - 1 \over 1/\pars{1 + z} - 1}} \braces{{\pars{-1/z}^{\ell + 1} - 1 \over -1/z - 1}} \\[5mm] = &\ \bracks{z^{0}}\braces{% {1 - \pars{1 + z}^{k + 1} \over -z} \,{1 \over \pars{1 + z}^{k + 1}}} \braces{{\pars{-1}^{\ell + 1} - z^{\ell + 1} \over -1 - z}\,{z \over z^{\ell + 1}}} \\[5mm] = &\ \bracks{z^{\ell + 1}}\braces{1 - {1 \over \pars{1 + z}^{k + 1}}} \braces{z^{\ell + 1} + \pars{-1}^{\ell} \over 1 + z} \\[5mm] = &\ \pars{-1}^{\ell}\bracks{z^{\ell + 1}} \bracks{\pars{1 + z}^{-1} - \pars{1 + z}^{-k - 2}} \\[5mm] = &\ \pars{-1}^{\ell}\bracks{\pars{-1}^{\ell + 1} - {-k - 2 \choose \ell + 1}} \\[5mm] = &\ -1 - \pars{-1}^{\ell}\,{-\bracks{-k - 2} + \bracks{\ell + 1} - 1 \choose \ell + 1}\pars{-1}^{\ell + 1} \\[5mm] = &\ -1 + { k + \ell + 2 \choose \ell + 1} = \bbx{{k + \ell + 2 \choose k + 1} - 1} \end{align}

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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