Trouble Understanding Proof of Lagrange's Identity Using Binomial Formula

Question

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.

Answer 1

They forgot to say they compute the coefficient of $x^n$ in the product and they apply the general formula for the product of two polynomials: $$\sum_{i=0}^n a_ix^i\cdot \sum_{j=0}^p b_jx^j=\sum_{k=1}^{n+p}\Bigl(\sum_{i+j=k}a_ib_j \Bigr)x^k ?$$

Answer 2

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} $$