### 23rd Putnam 1962

**Problem B1**

Define x^{(n)} = x(x - 1)(x - 2) ... (x - n + 1) and x^{(0)} = 1. Show that (x + y)^{(n)} = nC0 x^{(0)}y^{(n)} + nC1 x^{(1)}y^{(n-1)} + nC2 x^{(2)}y^{(n-2)} + ... + nCn x^{(n)}y^{(0)}.

**Solution**

Induction on n. It is obviously true for n = 1. Suppose it is true for n. We now multiply the rhs by (x + y - n). We now write:

nC0 x^{(0)}y^{(n)}(x + y - n) = (nC0 x^{(0)}y^{(n)} (y-n) ) + (nC0 x^{(0)}y^{(n)} x );
nC1 x^{(1)}y^{(n-1)} (x + y - n) = (nC1 x^{(1)}y^{(n-1)} (y-n+1) ) + (nC1 x^{(1)}y^{(n-1)} (x-1) );
nC2 x^{(2)}y^{(n-2)} (x + y - n) = (nC2 x^{(2)}y^{(n-2)} (y-n+2) ) + (nC2 x^{(2)}y^{(n-2)} (x-2) );
...
nCn x^{(n)}y^{(0)} (x + y - n) = (nCn x^{(n)}y^{(0)} y ) + (nCn x^{(n)}y^{(0)} (x-n) ).

Now the first term in the 1st equation gives (n+1)C0 x^{(0)}y^{(n+1)}. The second term in the 1st equation and the first term in the 2nd equation give (n+1)C1 x^{(1)}y^{(n)}. Then the second term in the 2nd equation and the first in the 3rd equation gives (n+1)C2 x^{(2)}y^{(n-1)} and so on. Finally the second term in the last equation gives (n+1)C(n+1) x^{(n+1)}y^{(0)}. So we have the result for n+1.

23rd Putnam 1962

© John Scholes

jscholes@kalva.demon.co.uk

5 Feb 2002