37th Putnam 1976

Problem B5

Find ∑0n (-1)i nCi ( x - i )n, where nCi is the binomial coefficient.



Answer: 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 xn, then Δp(x) is of order n-1 with leading coefficient a n xn-1. [Proof: let p(x) = a xn + b xn-1 + terms in xn-2 and below. Then Δp(x) = a(xn - (x-1)n) + b(xn-1 - (x-1)n-1) + terms in xn-2 and below = a(xn - xn + n xn-1) + b(xn-1 - xn-1) + terms in xn-2 and below = a n xn-1 + lower terms.]

Hence Δn p(x) = a n! But the expression given is simply Δnp(x) with p(x) = xn, so it evaluates to n!

That is the slick solution. The more plodding solution is to observe that the coefficient of xn-m is (-1)m nCm ( - nC1 1m + nC2 2m - nC3 3m + ... ). 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 xn n! (-1)n which gives n! (-1)n. Hence the expression in the question has the coefficient of xr zero, except for the constant term, which is (-1)n nCn n! (-1)n = n! .



37th Putnam 1976

© John Scholes
23 Jan 2001