# Problem Of The Week #396 Dec 9th, 2019

Status
Not open for further replies.

#### anemone

##### MHB POTW Director
Staff member
Here is this week's POTW:

-----

A polynomial $P(x)$ of the $n$-th degree satisfies $P(k)=2^k$ for $k=0,\,1,\,2,\,\cdots,\,n$. Find the value of $P(n+1)$.

-----

#### anemone

##### MHB POTW Director
Staff member
Congratulations to the following members for their correct solution!

1. Opalg
If $P(x)$ has degree $n$ then the difference polynomial $P(x) - P(x-1)$ has degree $n-1$, because the coefficients of $x^n$ cancel.The second difference $(P(x) - P(x-1)) - (P(x-1) - P(x-2)) = P(x) - 2P(x-1) + P(x-2)$ has degree $n-2$, and so on.
More precisely, define a sequence of polynomials $P_k(x)$ inductively by $P_0(x) = P(x)$ and $P_{k+1}(x) = P_k(x) - P_k(x-1)$ for $k\geqslant0$. Then $P_k(x)$ is a polynomial of degree $n-k$. A proof by induction, using the fact that ${k+1\choose j} = {k\choose j} + {k\choose j-1}$, shows that $$\displaystyle P_k(x) = \sum_{j=0}^k (-1)^j{k\choose j}P(x-j)$$.
When $k=n$, $P_n(x)$ will be a polynomial of degree $0$, a constant. And when $k=n+1$, $P_{n+1}(x) = P_n(x) - P_n(x-1)$ will be identically zero. In particular, $P_{n+1}(n+1) = 0$. But $$P_{n+1}(n+1) = \sum_{j=0}^{n+1} (-1)^j{n+1\choose j}P(n+1-j) = P(n+1) + \sum_{j=1}^{n+1} (-1)^j{n+1\choose j}2^{n+1-j}.$$ Therefore $$P(n+1) + \sum_{j=1}^{n+1} (-1)^j{n+1\choose j}2^{n+1-j} = 0.\qquad(*)$$ On the other hand, the binomial expansion of $(x-1)^{n+1}$, with $x=2$, shows that $$2^{n+1} + \sum_{j=1}^{n+1} (-1)^j{n+1\choose j}2^{n+1-j} = (2-1)^{n+1} = 1.$$ Compare that last equation with $(*)$ to see that $P(n+1) = 2^{n+1} - 1.$