37th Putnam 1976 Problem B5 Find ∑ 0 n (-1) i nCi ( x - i ) n , where nCi is the binomial coefficient. Solution
: n! Given a polynomial p(x), define Δp(x) = p(x) - p(x-1). If p(x) is of order n with leading coefficient a x n , then Δp(x) is of order n-1 with leading coefficient a n x n-1 . [Proof: let p(x) = a x n + b x n-1 + terms in x n-2 and below. Then Δp(x) = a(x n - (x-1) n ) + b(x n-1 - (x-1) n-1 ) + terms in x n-2 and below = a(x n - x n + n x n-1 ) + b(x n-1 - x n-1 ) + terms in x n-2 and below = a n x n-1 + lower terms.] Hence Δ n p(x) = a n! But the expression given is simply Δ n p(x) with p(x) = x n , so it evaluates to n! That is the slick solution. The more plodding solution is to observe that the coefficient of x n-m is (-1) m nCm ( - nC1 1 m + nC2 2 m - nC3 3 m + ... ). But the expression in parentheses is just the value at x = 1 of (x d/dx) m (1 - x) n (*). For m < n, all terms in (*) will have a non-zero power of (1 - x) and hence will evaluate to zero. For m = n, the only term not evaluating to zero will be x n n! (-1) n which gives n! (-1) n . Hence the expression in the question has the coefficient of x r zero, except for the constant term, which is (-1) n nCn n! (-1) n = n! . 37th Putnam 1976 © John Scholes jscholes@kalva.demon.co.uk 23 Jan 2001