3
$\begingroup$

I'm looking to find a closed formula for: $\sum_{r=0}^k {k \choose r}{k \choose (r-1)}$. My conjecture is that it is equal to ${2k \choose k-1}$ but I could not prove it. I'm interested in knowing if there's a way to prove this identity (preferably a combinatorical one), but really any would do. my preference is due to the fact that it helps understanding the intuition behind the proof. Thanks a million!

$\endgroup$
4
$\begingroup$

Your conjecture is correct (though the sum probably needs to start with $r=1$).

You can rewrite as

$$\sum_{r=1}^{k} \binom{k}{k-r} \binom{k}{r-1}$$

which has a combinatorial interpretation.

Picking $k-1$ things from $k+k$ things (choose $r-1$ from first $k$, remaining from the second), which is $$\binom{2k}{k-1}$$

$\endgroup$
  • $\begingroup$ +1 Actually there is no harm in allowing $r=0$, as there is none in allowing $r=k+1$, or even in summing over all $r\in\mathbf Z$ to make clear that the range of summation is not producing a "cut-off" effect that would spoil using the Vandermonde convolution $\endgroup$ – Marc van Leeuwen Apr 13 '13 at 7:40
1
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align}&\color{#66f}{\sum_{r\ =\ 0}^{k}{k \choose r}{k \choose r - 1}} =\sum_{r\ =\ 0}^{k}{k \choose r} \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{k} \over z^{r}}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1}\pars{1 + z}^{k} \sum_{r\ =\ 0}^{k}{k \choose r}\pars{1 \over z}^{r}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}\pars{1 + z}^{k}\pars{1 + {1 \over z}}^{k} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2k} \over z^{k}} \,{\dd z \over 2\pi\ic}=\color{#66f}{\large{2k \choose k - 1}} \end{align}

$\endgroup$
  • $\begingroup$ You really like that formula that uses the contour integral, don't you? ;) (You use it a lot...) $\endgroup$ – apnorton Dec 2 '14 at 16:53
  • $\begingroup$ @anorton Yes. I really like it because it leads to straightforward calculations. However, it doesn't give any insight toward the 'counting or/and combinatoric' procedure. Thanks. $\endgroup$ – Felix Marin Dec 2 '14 at 18:35

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.