combinatorics - Find a simple formula for $binom{n}{0}binom{n}{1}+binom{n}{1}binom{n}{2}+...+binom{n}{n-1}binom{n}{n}$

$$\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+...+\binom{n}{n-1}\binom{n}{n}$$

All I could think of so far is to turn this expression into a sum. But that does not necessarily simplify the expression. Please, I need your help.

Answer

First note that $\dbinom{n}k = \dbinom{n}{n-k}$. Hence, your sum can be written as
$$\sum_{k=0}^{n-1} \dbinom{n}k \dbinom{n}{k+1} = \sum_{k=0}^{n-1} \dbinom{n}k \dbinom{n}{n-k-1}$$
Now consider a bag with $n$ red balls and $n$ blue balls. We want to choose a total of $n-1$ bals. The total number of ways of doing this is given by $$\dbinom{2n}{n-1} \tag{$\star$}$$
However, we can also count this differently. Any choice of $n-1$ balls will involve choosing $k$ blue balls and $n-k-1$ red balls. Hence, the number of ways of choose $n-1$ balls with $k$ blue balls is $$\color{blue}{\dbinom{n}k} \color{red}{\dbinom{n}{n-1-k}}$$ Now to count all possible ways of choosing $n-1$ balls, we need to let our $k$ run from $0$ to $n-1$. Hence, the total number of ways is
$$\sum_{k=0}^{n-1} \color{blue}{\dbinom{n}k} \color{red}{\dbinom{n}{n-k-1}} \tag{$\dagger$}$$
Now since $(\star)$ and $(\dagger)$ count the same thing, they must be equal and hence, we get that
$$\sum_{k=0}^{n-1} \color{blue}{\dbinom{n}k} \color{red}{\dbinom{n}{n-k-1}} = \dbinom{2n}{n-1}$$

---

EDIT As Brian points out in the comments, the above is a special case of the more general Vandermonde's identity.
$$\sum_{k=0}^r \dbinom{m}k \dbinom{n}{r-k} = \dbinom{m+n}r$$ The proof for this is essentially the same as above. Consider a bag with $m$ blue balls and $n$ red balls and count the number of ways of choosing $r$ balls from these $m+n$ balls in two different ways as discussed above.