Proving $\sum\limits_{k=1}^n \binom{n}{k}\binom{n}{k-1} = \binom{2n}{n+1}$

Question

I'm thinking about using a group of $2n$ balls and pick $n+1$ of them for the right hand side.

However, I have no idea how to do the left hand side. Or do I need to use induction?

Answer 1

$$\sum\limits_{k=1}^n \binom{n}{k}\binom{n}{k-1}=\sum\limits_{k=1}^n \binom{n}{k}\binom{n}{n+1-k}=\binom{n+n}{k+(n+1-k)}=\binom{2n}{n+1}$$

Answer 2

In how many ways can we choose $n+1$ people from $n$ men and $n$ women? The RHS is obviously right, or we could pick which $k$ men qualify and which $k-1$ don't, giving the desired LHS.

Answer 3

Imagine there are $2n$ students in a class with $n$ boys and $n$ girls. You need to choose $n+1$ students from them for your school trip.

Think the above process in two different ways

1. Select $k$ boys who would go for the trip and select $k-1$ girls who would not go to the trip. So finally you would have $k$ boys and $n+1-k$ girls for the trip, totalling to $n+1$ students for the trip. Vary the value of $k$ from $0$ to $n$ and you have the total number of ways of taking those students to the trip.
2. Otherwise, you may select any $n+1$ students out of $2n$ students and take them to the trip.

The number of ways of selection of students according to first method corresponds to LHS of your equation. The second method forms the RHS of the equation. No matter how you choose the students, the total number of ways should be same.

That's an intuitive answer for you :)

Answer 4

$\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{\bbox[5px,#ffd]{\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1} = {2n \choose n + 1}}:\ {\Large ?}}$

---

\begin{align} &\bbox[5px,#ffd]{\sum_{k = 1}^{n}{n \choose k}{n \choose k - 1}} = \sum_{k = 1}^{n}{n \choose k}{n \choose n - k + 1} = \sum_{k = 1}^{n}{n \choose k}\bracks{z^{n - k + 1}}\pars{1 + z}^{n} \\[5mm] = &\ \bracks{z^{n + 1}}\pars{1 + z}^{n}\sum_{k = 1}^{n}{n \choose k}z^{k} = \bracks{z^{n + 1}}\pars{1 + z}^{2n} = \bbx{2n \choose n + 1} \\ & \end{align}