1
$\begingroup$

I have an identity $$\sum_{k=0}^{n}\frac{n-k}{k+1}\binom{n}{k}^2 = \binom{2n}{n-1}$$ for which I'm looking for a combinatorial proof. Any ideas?

I was thinking about separating $2n$ on boys and girls, but the fraction that appears on the LHS seems problematic. Dividing by $k+1$ suggests some element being chosen on $k+1$ ways, but I don't see what could be a possible story to that.

$\endgroup$
6
$\begingroup$

One way to deal with the left-hand side is to notice that $$ \frac{n-k}{k+1} {n \choose k} = {n \choose k+1} = {n \choose n-1-k}. $$ Therefore the left-hand side is $$ \sum_{k=0}^{n-1} {n \choose k}{n \choose n-1-k}. $$ One way to look at this sum is that it counts the number of ways to select a group of size $n-1$ from a population of $n$ girls and $n$ boys. Why? Suppose that we want to count the ways to do this task with the added condition that we choose $k$ girls. So there are ${ n\choose k}$ ways to pick the $k$ (out of $n$) girls and ${n \choose n-1-k}$ ways to pick the remaining $n-1-k$ (out of $n$) boys for the group. Summing over all possible $k$ completes this task.

Now clearly, the number of ways to select a group of size $n-1$ from a population of $2n$ people is ${2n \choose n-1}$.

$\endgroup$
  • $\begingroup$ Very nice, that first equation is a key here. Thanks. $\endgroup$ – Jules Jun 20 '16 at 19:05
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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#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}$ \begin{align} \color{#f00}{\sum_{k = 0}^{n}{n - k \over k + 1}{n \choose k}^{2}} & = \sum_{k = 0}^{n}{n \choose k}{\color{#f00}{n} \choose \color{#f00}{n - k - 1}} = \sum_{k = 0}^{n}{n \choose k} \oint_{\verts{z} = 1}{\pars{1 + z}^{\color{#f00}{n}} \over z^{\color{#f00}{n - k -1} + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n}} \sum_{k = 0}^{n}{n \choose k}z^{k}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n}} \pars{1 + z}^{n}\,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1}{\pars{1 + z}^{\color{#f00}{2n}} \over z^{\color{#f00}{n - 1} + 1}}\,{\dd z \over 2\pi\ic} = \color{#f00}{2n \choose n - 1} \end{align}

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