prove simple binomial sum, combinatorics I want to prove that:
$$\large\sum_{i = 1}^{n} \binom{n}{i}\binom{n}{i-1} = \binom{2n}{n-1}$$
On the right hand side we simply have the coefficient of $x^{n-1}$ of the term $(1+x)^{2n}$
But on the other hand,
$$(1+x)^{2n} = (1+x)^{n}(1+x)^{n} = \large\sum_{i = 0}^{n}\binom{n}{i}x^i\sum_{j = 0}^{n}\binom{n}{j}x^j$$
and the coefficient here of $x^{n-1}$ is when $j = n-1-i$ and obviously $i$ cant be higher than $n-1$ so overall:
$$\large\sum_{i=0}^{n-1}\dbinom{n}{i}\dbinom{n}{n-i-1}$$
How do we continue from here?

Here is a similar technique using the coefficient of operator $[x^n$] to denote the coefficient of $x^n$ in a series. This way we can write    e.g.
\begin{align*}
[x^i](1+x)^n=\binom{n}{i}
\end{align*}
We also adopt the convention that binomial coefficients $\binom{n}{k}=0$ if $k>n$ or $k<0$.

We obtain
  \begin{align*}
\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}&=\sum_{i=0}^\infty[x^i](1+x)^n[y^{i-1}](1+y)^n\tag{1}\\
&=[y^{-1}](1+y)^n\sum_{i=0}^\infty y^{-i}[x^i](1+x)^n\tag{2}\\
&=[y^{-1}](1+y)^n\left(1+\frac{1}{y}\right)^n\tag{3}\\
&=[y^{n-1}](1+y)^{2n}\tag{4}\\
&=\binom{2n}{n-1}
\end{align*}

Comment:


*

*In (1) we apply the coefficient of operator twice and extend the lower and upper limit of the sum without changing anything, since we add only zeros.

*In (2) we use the linearity of the coefficient of operator and apply the rule
\begin{align*}
[y^{p+q}]A(y)=[y^{p}]y^{-q}A(y)
\end{align*}

*In (3) we use the substitution rule of the coefficient of operator
\begin{align*}
A(y)=\sum_{i=0}^{\infty}a_iy^i=\sum_{i=0}^\infty y^i [x^i]A(x)
\end{align*}

*In (4) we factor out $\frac{1}{y^n}$ and use again the rule from (2) to obtain $[y^{-1}]y^{-n}=[y^{n-1}]$
