Counting functions and subsets

Question

I'm having troubles understanding how to tackle this problem about coefficients. By equating the coefficients of $x^n$ in $(1+x)^{2n} = (1+x)^n(1+x)^n$ prove that $$\binom{2n}{n} = \sum^n_{i=0}\binom{n}{i}^2$$I started by doing an induction on n by stating my base case to be n =0 which is true. Now I have as my I.H. to be let n = k and assume is true so now I'm trying to prove it for n = k+1. My problem is trying to correlate the information given with the problem to begin solving the problem. A starting point or a hint will be appreciated.

Answer 1

There is no need to use induction. We can show it straightforward. In order to do so, it's convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^n=[x^k]\sum_{i=0}^n\binom{n}{i}x^i=\binom{n}{k} \end{align*}

We obtain

\begin{align*} [x^n](1+x)^{2n}=[x^n]\sum_{i=0}^{2n}\binom{2n}{i}x^i=\binom{2n}{n}\tag{1} \end{align*} and \begin{align*} [x^n](1+x)^{2n}&=[x^n](1+x)^n(1+x)^n\\ &=[x^n]\sum_{i=0}^n\binom{n}{i}x^i\sum_{j=0}^n\binom{n}{j}x^j\tag{2}\\ &=\sum_{i=0}^n\binom{n}{i}[x^{n-i}]\sum_{j=0}^n\binom{n}{j}x^j\tag{3}\\ &=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}\tag{4}\\ &=\sum_{i=0}^n\binom{n}{i}^2\tag{5} \end{align*}

Since we have selected in (1) and (5) the same coefficient $[x^n]$ the validity of the binomial identity \begin{align*} \binom{2n}{n}=\sum_{i=0}^n\binom{n}{i}^2 \end{align*} follows.

Comment:

• In (1) we expand $(1+x)^{2n}$ according to the binomial formula and select the coefficient of $x^{2n}$.

• In (2) we expand each factor $(1+x)^n$

• In (3) we use the linearity of the coefficient of operator and use the rule $$[x^k]x^jA(x)=[x^{k-j}]A(x)$$

• In (4) we select the coefficient of $x^{n-i}$ from the righthand sum

• In (5) we use the symmetry $\binom{n}{i}=\binom{n}{n-i}$