Putnam 1962/B1 solution

23rd Putnam 1962

Problem B1

Define x⁽ⁿ⁾ = x(x - 1)(x - 2) ... (x - n + 1) and x⁽⁰⁾ = 1. Show that (x + y)⁽ⁿ⁾ = nC0 x⁽⁰⁾y⁽ⁿ⁾ + nC1 x⁽¹⁾y^(n-1) + nC2 x⁽²⁾y^(n-2) + ... + nCn x⁽ⁿ⁾y⁽⁰⁾.

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⁽⁰⁾y⁽ⁿ⁾(x + y - n) = (nC0 x⁽⁰⁾y⁽ⁿ⁾ (y-n) )  + (nC0 x⁽⁰⁾y⁽ⁿ⁾ x );

nC1 x⁽¹⁾y^(n-1) (x + y - n)  = (nC1 x⁽¹⁾y^(n-1) (y-n+1) ) + (nC1 x⁽¹⁾y^(n-1) (x-1) );

nC2 x⁽²⁾y^(n-2) (x + y - n) = (nC2 x⁽²⁾y^(n-2) (y-n+2) ) + (nC2 x⁽²⁾y^(n-2) (x-2) ); 

...

nCn x⁽ⁿ⁾y⁽⁰⁾ (x + y - n) = (nCn x⁽ⁿ⁾y⁽⁰⁾ y ) + (nCn x⁽ⁿ⁾y⁽⁰⁾ (x-n) ).

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

23rd Putnam 1962