# Finding a close formula for $\sum_{r=0}^k {k \choose r}{k \choose r-1}$

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!

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

• +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 – Marc van Leeuwen Apr 13 '13 at 7:40

$\newcommand{\angles}{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}{\,{\rm Li}_{#1}} \newcommand{\pars}{\left(\, #1 \,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}} \newcommand{\verts}{\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}

• You really like that formula that uses the contour integral, don't you? ;) (You use it a lot...) – apnorton Dec 2 '14 at 16:53
• @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. – Felix Marin Dec 2 '14 at 18:35