### 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.

© John Scholes
jscholes@kalva.demon.co.uk
5 Feb 2002