<s>[INST] Trouble Understanding Proof of Lagrange's Identity Using Binomial Formula I've been reading a book on elementary mathematics and am having trouble understanding a proof that they give for Lagrange's identity using the binomial formula.
Lagrange's identity is stated as :
\begin{equation}
\sum_{j=0}^{n} \binom{n}{j}^{2} = \binom{2n}{n}
\end{equation}
In the proof they say :
"Writing $(1+x)^{2n} = (1+x)^{n}(1+x)^{n}$ and applying Newton's binomial formula to both sides we get :
\begin{equation}
\binom{2n}{n} = \sum_{i+j=n} \binom{n}{i} \binom{n}{j} = \sum_{i=0}^{n} \binom{n}{i}\binom{n}{n-i} = \sum_{i=0}^{n} \binom{n}{i}^{2} 
\end{equation}
$\square$."
A lot of detail seems to be missing here. Could someone provide the missing details here ? I cannot understand the proof due to the elision of details.
 [/INST] The binomial coefficient $\binom{2n}{n}$ is the coefficient of $x^n$ in the left-hand side.
In the right hand side you get $x^n$ from terms $x^i$ and $x^j$ where $i+j=n$. The term $x^i$ has coefficient $\binom{n}{i}$ and similarly for $x^j$, so you have
$$
\binom{2n}{n}=\sum_{i+j=n}\binom{n}{i}\binom{n}{j}
$$
Now observe that if $i+j=n$, then $j=n-i$ and that
$$
\binom{n}{n-i}=\binom{n}{i}
$$
and that $i$ can run from $0$ to $n$, so we finally get
$$
\binom{2n}{n}=\sum_{i=0}^n\binom{n}{i}^{\!2}
$$
As an example with $n=3$: in the right hand side we have
$$
\binom{3}{0}+\binom{3}{1}x+\binom{3}{2}x^2+\binom{3}{3}x^3
$$
multiplied by itself, but we just need to consider the terms with $x^3$, so
$$
\binom{3}{0}\cdot\binom{3}{3}x^3+\binom{3}{1}x\cdot\binom{3}{2}x^2
+\binom{3}{2}x^2\cdot\binom{3}{1}x+\binom{3}{3}x^3\cdot\binom{3}{0}
$$
</s>