A STEP question (1999 STEP II, Q4) asks:

By considering the expansions in powers of $x$ of both sides of the identity $(1+x)^n (1+x)^n \equiv (1+x)^{2n}$

show that: $\sum_{s=0}^{n} \left( \nCr{n}{s} \right)^2 = \left( \nCr{2n}{n} \right)$,

where $\nCr{n}{s} = \frac{n!}{s!(n-s)!}$.

By considering similar identities, or otherwise, show also that:

(i) If $n$ is an even integer, then $\sum_{s=0}^{n} (-1)^s \left( \nCr{n}{s} \right)^2 = (-1)^{\frac {n}{2}} \left( \nCr {n}{\frac{n}{2}}\right)$;

(ii) $\sum_{t=1}^{n} 2t \left( \nCr {n}{t} \right)^2 = n \left( \nCr {2n}{n} \right)$.

This is quite a typical STEP question: it gives you a starter, to let you see if you have a way into the question, then a couple of variations that need a bit of creativity to weasel out.

In this case, the starter needs a little bit of an insight: if you look at the right hand side, you might wonder where you’d get a $\left( \nCr {2n}{n} \right)$ from in the expansion of $(1+x)^{2n}$ and it hits you: that’s the coefficient of the $x^n$ term. So, what’s the coefficient of $x^n$ in the expansion of $(1+x)^n (1+x)^n$?

Let’s multiply it out:

|  $\nCr {n}{0} x^{0}$ | $\nCr {n}{1} x^{1}$ | $\nCr {n}{2} x^{2}$ | …  | $\nCr {n}{k} x^{k}$ |  …  | $\nCr {n}{n-2} x^{n-2}$ | $\nCr {n}{n-1} x^{n-1}$ | $\nCr {n}{n} x^{n}$ | | $\nCr {n}{0} x^{0}$ | $\pnCr{n}{0}^2 x^{0}$ | $\pnCr{n}{0} \pnCr{n}{1} x^{1}$ | $\pnCr{n}{0} \pnCr{n}{2} x^{2}$ |  … | $\pnCr{n}{0} \pnCr{n}{k} x^{k}$ | …  | $\pnCr{n}{0} \pnCr{n}{n-2} x^{n-2}$ |$\pnCr{n}{0} \pnCr{n}{n-1} x^{n-1}$ | $\pnCr{n}{0} \pnCr{n}{n} x^{n}$ | | $\nCr {n}{1} x^{1}$ | $\pnCr{n}{1} \pnCr{n}{0} x^{1}$ | $\pnCr{n}{1}^2 x^{2}$ | $\pnCr{n}{1} \pnCr{n}{2} x^{3}$ |  …  | $\pnCr{n}{1} \pnCr{n}{k} x^{k+1}$ |  …  | $\pnCr{n}{1} \pnCr{n}{n-2} x^{n-1}$ | $\pnCr{n}{1} \pnCr{n}{n-1} x^{n}$ | $\pnCr{n}{1} \pnCr{n}{n} x^{n+1}$ | | $ \nCr {n}{2} x^{2}$ | $\pnCr{n}{2} \pnCr{n}{0} x^{2}$ | $\pnCr{n}{2} \pnCr{n}{1} x^{3}$ | $\pnCr{n}{2}^2 x^{4}$ |  …  | $\pnCr{n}{2} \pnCr{n}{k} x^{k+2}$ |  …  | $\pnCr{n}{2} \pnCr{n}{n-2} x^{n}$ | $\pnCr{n}{2} \pnCr{n}{n-1} x^{n+1}$ | $\pnCr{n}{2} \pnCr{n}{n} x^{n+2}$ | | …  |  …  |  …  |  …  |  …  |  …  |  …  |  …  |  …  |  …  | | $ \nCr {n}{k} x^{k}$ | $\pnCr{n}{k} \pnCr{n}{0} x^{k}$ | $\pnCr{n}{k} \pnCr{n}{1} x^{k+1}$ | $\pnCr{n}{k} \pnCr{n}{2} x^{k+2}$ |  …  | $\pnCr{n}{k}^2 x^{2k}$ |  …  | $\pnCr{n}{k} \pnCr{n}{n-2} x^{k+n-2}$ | $\pnCr{n}{k} \pnCr{n}{n-1} x^{k+n-1}$ | $\pnCr{n}{k} \pnCr{n}{n} x^{k+n}$ | |  …  |  …  |  …  |  …  |  …  |  …  |  …  |  …  |  …  |  …  | | $ \nCr {n}{n-2} x^{n-2}$ | $\pnCr{n}{n-2} \pnCr{n}{0} x^{n-2}$ | $\pnCr{n}{n-2} \pnCr{n}{1} x^{n-1}$ | $\pnCr{n}{n-2} \pnCr{n}{2} x^{n}$ |  …  | $\pnCr{n}{n-2} \pnCr{n}{k} x^{k+n-2}$ |  …  | $\pnCr{n}{n-2}^2 x^{2n-4}$ | $\pnCr{n}{n-2} \pnCr{n}{n-1} x^{2n-3}$ | $\pnCr{n}{n-2} \pnCr{n}{n} x^{2n-2}$ | | $ \nCr {n}{n-1} x^{n-1}$ | $\pnCr{n}{n-1} \pnCr{n}{0} x^{n-1}$ | $\pnCr{n}{n-1} \pnCr{n}{1} x^{n}$ | $\pnCr{n}{n-1} \pnCr{n}{2} x^{n+1}$ |  …  | $\pnCr{n}{n-1} \pnCr{n}{k} x^{k+n-1}$ |  …  | $\pnCr{n}{n-1} \pnCr{n}{n-2} x^{2n-3}$ | $\pnCr{n}{n-1}^2 x^{2n-2}$ | $\pnCr{n}{n-1} \pnCr{n}{n} x^{2n-1}$ | | $ \nCr {n}{n} x^{n}$ | $\pnCr{n}{n} \pnCr{n}{0} x^{n}$ | $\pnCr{n}{n} \pnCr{n}{1} x^{n+1}$ | $\pnCr{n}{n} \pnCr{n}{2} x^{n+2}$ |  …  | $\pnCr{n}{n} \pnCr{n}{k} x^{k+n}$ |  …  | $\pnCr{n}{n} \pnCr{n}{n-2} x^{2n-2}$ | $\pnCr{n}{n} \pnCr{n}{n-1} x^{2n-1}$ | $\pnCr{n}{n}^2 x^{2n}$ | (Have you any idea how long it took me to get that formatted? 90 minutes of coding, that’s how long.)

Anyhow, you’ll notice I’ve shaded the $x^n$ terms, which are the ones we’re looking for. The coefficient of $x^n$ is $\pnCr{n}{0} \pnCr{n}{n} + \pnCr{n}{1} \pnCr{n}{n-1} + \pnCr{n}{2} \pnCr{n}{n-2} + … + \pnCr{n}{n} \pnCr{n}{0}$. However, the definition of $\nCr{}{}$ is such that $\nCr{n}{a} = \nCr{n}{n-a}$, so this whole line can be written as $\pnCr{n}{0}^2 + \pnCr{n}{1}^2 + \pnCr{n}{2}^2 + … + \pnCr{n}{n}^2$, or even more succinctly, $\sum_{r=0}^{n} \pnCr{n}{r}^2$, as required. So that’s a good start.

Looking at part (i), my first thought was to try $(1-x)^n (1-x)^n$, but that doesn’t work – the $x^n$ terms don’t alternate signs as we need them to. Instead, what about $(1-x)^n (1+x)^n$? This is the same thing as $(1-x^2)^n$, using the difference of two squares. The expansion of that is $\nCr{n}{0} - \nCr{n}{1} x^2 + \nCr{n}{2} x^4 - … + (-1)^k \nCr{n}{k} x^{2k} + … + \nCr{n}{n} x^{2n}$, given that $n$ is even. The $x^n$ term is when $k = \frac{n}{2}$, so its coefficient is $(-1)^{\frac{n}{2}} \nCr{n}{\frac{n}{2}}$. That matches the right-hand side, which is good.

On the left-hand-side, the coefficients are the same as in the starter part, except with alternating signs – the $(-1)^s$ that comes up in the thing we’re trying to prove. That’s reassuring!

Part (ii) is less ‘obvious’, though. It’s one of those that, if I showed it to the average student, they would say “I’d never have thought of that!” That’s because they hadn’t gone through enough STEP questions writing down the tricks that worked for them.

The way to get it is by differentiating the starter and considering the coefficient of the $x^{n-1}$ term.

On the right-hand side, differentiating clearly gives you $n \nCr {2n}{n}$ as the coefficient. The left-hand side is trickier.

Differentiating the product gives $2(1+x)^n \diff{}{t} (1+x)^n$. Obviously, you could differentiate that second factor as it stands, but I’m going to do it term by term instead: if $(1+x)^n = 1 + \nCr{n}{1} x + … + \nCr {n}{t} x^t + … x^n$, then its derivative is $\nCr {n}{1} + 2 \nCr {n}{2} x + … + t \nCr {n}{t} x^{t-1} + … + n x^{n-1}$.

Multiplying out (and ignoring the 2 for now):

 

$\nCr {n}{0} x^{0}$

$\nCr {n}{1} x^{1}$

$\nCr {n}{2} x^{2}$

 … 

$\nCr {n}{t} x^{t}$

 … 

$\nCr {n}{n-2} x^{n-2}$

$\nCr {n}{n-1} x^{n-1}$

$\nCr {n}{n} x^{n}$

$ \left(1\right) \nCr {n}{1} x^{0}$

$\left(1\right) \pnCr{n}{1} \pnCr{n}{0} x^{0}$

$\left(1\right) \pnCr{n}{1}^2 x^{1}$

$\left(1\right) \pnCr{n}{1} \pnCr{n}{2} x^{2}$

 … 

$\left(1\right) \pnCr{n}{1} \pnCr{n}{t} x^{t}$

 … 

$\left(1\right) \pnCr{n}{1} \pnCr{n}{n-2} x^{n-2}$

$\left(1\right) \pnCr{n}{1} \pnCr{n}{n-1} x^{n-1}$

$\left(1\right) \pnCr{n}{1} \pnCr{n}{n} x^{n}$

$ \left(2\right) \nCr {n}{2} x^{1}$

$\left(2\right) \pnCr{n}{2} \pnCr{n}{0} x^{1}$

$\left(2\right) \pnCr{n}{2} \pnCr{n}{1} x^{2}$

$\left(2\right) \pnCr{n}{2}^2 x^{3}$

 … 

$\left(2\right) \pnCr{n}{2} \pnCr{n}{t} x^{t+1}$

 … 

$\left(2\right) \pnCr{n}{2} \pnCr{n}{n-2} x^{n-1}$

$\left(2\right) \pnCr{n}{2} \pnCr{n}{n-1} x^{n}$

$\left(2\right) \pnCr{n}{2} \pnCr{n}{n} x^{n+1}$

 … 

 … 

 … 

 … 

 … 

 … 

 … 

 … 

 … 

 … 

$ \left(t\right) \nCr {n}{t} x^{t-1}$

$\left(t\right) \pnCr{n}{t} \pnCr{n}{0} x^{t-1}$

$\left(t\right) \pnCr{n}{t} \pnCr{n}{1} x^{t}$

$\left(t\right) \pnCr{n}{t} \pnCr{n}{2} x^{t+1}$

 … 

$\left(t\right) \pnCr{n}{t}^2 x^{2k-1}$

 … 

$\left(t\right) \pnCr{n}{t} \pnCr{n}{n-2} x^{n+t-3}$

$\left(t\right) \pnCr{n}{t} \pnCr{n}{n-1} x^{n+t-2}$

$\left(t\right) \pnCr{n}{t} \pnCr{n}{n} x^{n+t-1}$

 … 

 … 

 … 

 … 

 … 

 … 

 … 

 … 

 … 

 … 

$ \left(n-2\right) \nCr {n}{n-2} x^{n-3}$

$\left(n-2\right) \pnCr{n}{n-2} \pnCr{n}{0} x^{n-3}$

$\left(n-2\right) \pnCr{n}{n-2} \pnCr{n}{1} x^{n-2}$

$\left(n-2\right) \pnCr{n}{n-2} \pnCr{n}{2} x^{n-1}$

 … 

$\left(n-2\right) \pnCr{n}{n-2} \pnCr{n}{t} x^{n+t-3}$

 … 

$\left(n-2\right) \pnCr{n}{n-2}^2 x^{2n-5}$

$\left(n-2\right) \pnCr{n}{n-2} \pnCr{n}{n-1} x^{2n-4}$

$\left(n-2\right) \pnCr{n}{n-2} \pnCr{n}{n} x^{2n-3}$

$ \left(n-1\right) \nCr {n}{n-1} x^{n-2}$

$\left(n-1\right) \pnCr{n}{n-1} \pnCr{n}{0} x^{n-2}$

$\left(n-1\right) \pnCr{n}{n-1} \pnCr{n}{1} x^{n-1}$

$\left(n-1\right) \pnCr{n}{n-1} \pnCr{n}{2} x^{n}$

 … 

$\left(n-1\right) \pnCr{n}{n-1} \pnCr{n}{t} x^{n+t-2}$

 … 

$\left(n-1\right) \pnCr{n}{n-1} \pnCr{n}{n-2} x^{2n-4}$

$\left(n-1\right) \pnCr{n}{n-1}^2 x^{2n-3}$

$\left(n-1\right) \pnCr{n}{n-1} \pnCr{n}{n} x^{2n-2}$

$ \left(n\right) \nCr {n}{n} x^{n-1}$

$\left(n\right) \pnCr{n}{n} \pnCr{n}{0} x^{n-1}$

$\left(n\right) \pnCr{n}{n} \pnCr{n}{1} x^{n}$

$\left(n\right) \pnCr{n}{n} \pnCr{n}{2} x^{n+1}$

 … 

$\left(n\right) \pnCr{n}{n} \pnCr{n}{t} x^{n+t-1}$

 … 

$\left(n\right) \pnCr{n}{n} \pnCr{n}{n-2} x^{2n-3}$

$\left(n\right) \pnCr{n}{n} \pnCr{n}{n-1} x^{2n-2}$

$\left(n\right) \pnCr{n}{n}^2 x^{2n-1}$

Looking at the shaded terms, you get a coefficient of: $(1)\pnCr{n}{1}\pnCr{n-1}{n} + (2) \pnCr{n}{2}\pnCr{n}{n-2} + … + (t) \pnCr{n}{t} \pnCr{n}{n-t} + … + (n) \pnCr{n}{n} \pnCr{n}{0}$

Using the symmetry trick like before (and doubling to take account of the 2 I sneakily set aside earlier), that works out to $\sum_{t=1}^{n} 2t \left(t \nCr{n}{t} \right)^2$, as required.

I’m not going to claim that thinking this way is easy or obvious – but you will need to master it if you want to do well in STEP II.

* Edited 2016-04-25 to fix LaTeX errors. Thanks, @christianp!