USA 1975 Problem 3

If P(x) denotes a polynomial of degree n such that

P(k) = \frac{k}{k + 1}

for k = 0, 1, 2, ... n,  determine P(n + 1).

Solution

Every polynomial can be written in Newton's form

P(x) = a_{0} + a_{1}x + a_{2}x(x-1) + a_{3}x(x-1)(x-2) + ...

The coefficients a_{0}, a_{1}, ... are the so called Newton's divided differences that have a well developed theory and find numerous application in both theory and practice of interpolation. However, for this particular problem, the theory is not needed as the values of the coefficients are easily guessed following a few examples. The formula shows that

P_{n}(x) = P_{n-1}(x) + a_{n}x(x-1)(x-2) \ldots (x-(n-1)),

for some coefficient a_{n}, Obviously, P_{0}(x)\equiv{0} . Further, P_{1}(x) = \frac{x}{2}.

To find P_{2}(x) = \frac{x}{2} + a_{2}x(x-1) we only need to determine the coefficient b. We know that P_{2}(2) = \frac{2}{3} which gives

\frac{2}{3} = \frac{2}{2} + {a_{2}}{2}(2-1)

which gives a_{2} = -\frac{1}{6}.

Since P_{3}(x) = P_{2}{x} + a_{3}x(x-1)(x-2), we again need only to find one coefficient, a_{3}. This is found from P_{3}(3) = \frac{3}{4}:

\frac{3}{4} = \frac{3}{2} - \frac{3(3-1)}{6} + a_{3}3(3-1)(3-2),

which gives a_{3} = \frac{1}{24} = \frac{1}{4!}. We may now guess that the generic coefficient a_{n} = \frac{(-1)^{n+1}}{(n+1)!} so that

P_{n}(x) = P_{n-1}(x) + a_{n}x(x-1)\ldots(x-(n-1)).

The convenience of Newton's formula is apparent from the following property: For all k \lt n, P_{n}(k) = P_{n-1}(k).

More explicitly these polynomials are written as

P_{n}(x) = \frac{x}{2!} -\frac{x(x-1)}{3!} + \ldots + (-1)^{n+1}\frac{{x(x-1)}\ldots(x-(n-1))}{(n+1)!}.

Next we verify that P_{n}(n) = \frac{n}{n+1}. Multiplying and dividing by n+1 does a magic

P_{n}(n) = \frac{1}{n+1} ({{n+1}\choose{2}} - {{n+1}\choose{3}} + \ldots + (-1)^{n+1}{{n+1}\choose{n+1}}).

If we recollect the binomial formula and the fact that (1-1)^{n+1} = 0 , we obtain

P_{n}(n) = \frac{1}{n+1}(-1 + (n+1)) = \frac{n}{n+1}

Just as stipulated in the problem. On the other hand, multiplying and dividing by n+2,

P_{n}(n+1) = \frac{1}{n+2} ({{n+2}\choose{2}} - {{n+2}\choose{3}} + \ldots + (-1)^{n+1}{{n+2}\choose{n+1}}).

So that

P_{n}(n+1) = \frac{1}{n+2} (-1 + (n+2) + (-1)^{n}) = \frac{1}{n+2}(n+1 + (-1)^{n}).