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?
 A: Let $k=i+1$. Then, $i=k-1$, and  
$$
\sum_{i=0}^{n-1}\binom{n}{i}\binom{n}{n-i-1}=\sum_{k=1}^{n}\binom{n}{k-1}\binom{n}{n-k}=\sum_{k=1}^{n}\binom{n}{k-1}\binom{n}{k},
$$
where the last equality follows since $\binom{n}{n-k}=\frac{n!}{k!(n-k)!}=\binom{n}{k}$.
A: 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}]$
A: $\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}{\Leftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\ol}[1]{\overline{#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}$
\begin{align}
\color{#f00}{\sum_{j = 1}^{n}{n \choose j}{n \choose j - 1}} & =
\sum_{j = 1}^{n}{n \choose j}{n \choose n - j + 1} =
\sum_{j = 1}^{n}{n \choose j}\ \overbrace{\oint_{\verts{z} = 1}
{\pars{1 + z}^{n} \over z^{n - j + 2}}\,{\dd z \over 2\pi\ic}}
^{\ds{{n \choose n - j + 1}}}
\\[3mm] & =
\oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 2}}\
\overbrace{\sum_{j = 1}^{n}{n \choose j}z^{j}}^{\ds{\pars{1 + z}^{n} - 1}}\
\,{\dd z \over 2\pi\ic}
\\[3mm] & =
\overbrace{%
\oint_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}}
^{\ds{{2n \choose n + 1}}}\ -\
\overbrace{%
\oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}}
^{\ds{{n \choose n + 1} = 0}} =
{2n \choose n + 1} = \color{#f00}{{2n \choose n - 1}}
\end{align}
