Counting functions and subsets 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. 
 A: 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}$
