<s>[INST] Prove by induction: $C(2n, 2) = 2C(n, 2) + n^2$ 
Show that if $n$ is a positive integer, then $C(2n, 2) = 2C(n, 2) + n^2$. Here, $C(a, b)$ means the binomial coefficient $\dbinom{a}{b}$.
Prove this by induction.

Here is my calculation:
$n$ cannot be $1$ because $n$ should be equal or larger than $2$ for $C(n, 2)$.
If $n=2$: $C(4, 2) = 2C(2, 2) + 2^2 = 6$
If $n=m$: $C(2m, 2) = 2C(m, 2) + m^2 = 2m^2 - m$
If $n=m+1$: $C(2m+2, 2) = 2C(m+1, 2) + (m+1)^2 = 2m^2 + 3m + 1$
And I think I have to prove that:
\begin{align*}
C(2m+2, 2) & = [\dots]\\
           & = [2C(m, 2) + m^2] + [2C(m, 1) + (2m + 1)]\\
           & = 2C(m+1, 2) + (m+1)^2 && \text{(by Pascal's Identity).}
\end{align*}
But I have no idea what to do on $[\dots]$ part.
Thanks.
 [/INST] We assume for our inductive hypothesis that $\binom{2n}{2}=2\binom{n}{2}+n^2$ is true for all positive integers $n$ which are less than or equal to some $k$.  We then try to prove that this will further imply it is true for $k+1$ as well.
$$\begin{array}{rl}\binom{2(k+1)}{2}&=\binom{2k+2}{2}=\binom{2k+1}{1}+\binom{2k+1}{2}\\
&=\binom{2k+1}{1}+\binom{2k}{1}+\binom{2k}{2}\\
&=2k+1+2k+\binom{2k}{2}\\
~^{\text{I.H.}}&=2k+1+2k+2\binom{k}{2}+k^2\\
&=k+\binom{k}{2}+k+\binom{k}{2}+k^2+2k+1\\
&=\binom{k}{1}+\binom{k}{2}+\binom{k}{1}+\binom{k}{2}+k^2+2k+1\\
&=\binom{k+1}{2}+\binom{k+1}{2}+(k+1)^2\\
&=2\binom{k+1}{2}+(k+1)^2\end{array}$$
which is exactly what we hoped to show.  Note how we used (and pointed out our use of) the induction hypothesis going from the third to the fourth line.
The big trick here was to recognize that $n = \binom{n}{1}$ and to recognize that $\binom{n}{r-1}+\binom{n}{r}=\binom{n+1}{r}$ (in particular when $r=2$)

Reiterating what was said in comments above, some times it is preferable to use a combinatorial proof rather than an inductive proof.  The combinatorial proof for this situation is relatively straightforward once you know how to spot it.
Suppose we have $2n$ balls, $n$ of which are red, and the other $n$ of which are black, and these balls are all numbered.  We count how many ways there are to select two balls from these and do so in two different ways.
The first method, we just count directly.  There are $2n$ balls total, and to choose two of them this can be done in $\binom{2n}{2}$ ways.
The second method, we break into cases based on the colors chosen.  If both balls chosen were red, there are $\binom{n}{2}$ ways to do this.  Similarly there are $\binom{n}{2}$ ways to do so if they are both black.  If they are one of each color there are $n^2$ ways to do this, for a total of $2\binom{n}{2}+n^2$ ways to choose two balls.
By the nature of the fact that these expressions both correctly answer the same counting question, despite appearing in different forms they must be equal.  Therefore $\binom{2n}{2}=2\binom{n}{2}+n^2$.
</s>