Polynomial $P(x)$ Satisfying $P(k)=2^k$: POTW #396 Dec 9th, 2019

[anemone]

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)$.

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to the following members for their correct solution!(Cool)

1. Opalg
2. kaliprasad

Solution from Opalg:

Spoiler

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 $$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.$