Degree $2015$ polynomial value at $2016$

Question

I was doing this question from an RMO Practice Paper, and I have been unable to solve it.

Let $P(x)$ be a polynomial of degree $2015$. $P(k)=2^k$ for $k=0,1,2,\dots,2015$. Find $P(2016)$

My attempt:

Let $Q(x)=P(x)-2^x$.

Then its zeroes are $0,1,2,\dots,2015$. Thus $Q(x)$ is a polynomial of degree $2015$ with $2016$ zeroes. Therefore it is always $0$, thus giving $P(x)=2^x$, so $P(2016)=2^{2016}$, but the answer is given as $2^{2016}-1$.

Where did I go wrong and how do I get the correct answer?

Please help.

Answer 1

Using repeated differences, we get that the first value in every row is $1$: $$ \begin{array}{llll} 1 & 2 & 4 & 8 & \cdots \\ 1 & 2 & 4 & \cdots \\ 1 & 2 & \cdots \\ 1 & \cdots \\ \cdots \\ 1 & \\ \end{array} $$ Newton's interpolation formula then gives $$ P(n)= 1 \binom{n}{0} + 1 \binom{n}{1} + 1 \binom{n}{2} + \cdots = \sum_{k=0}^{2015} \binom{n}{k} $$ Therefore, $$ P(2016) = \sum_{k=0}^{2015} \binom{2016}{k} = \sum_{k=0}^{2016} \binom{2016}{k} - \binom{2016}{2016} = 2^{2016}-1 $$

Answer 2

Your answer is wrong because $Q(x)$ is not a polynomial due to the presence of $2$ to the power $x$.

Answer 3

From the calculus of finite differences, the leading coefficient of $P(x)$ is $$a=\frac1{2015!}\sum_{j=0}^{2015}(-1)^j\binom{2015}jf(2015-j) =\frac1{2015!}\sum_{j=0}^{2015}(-1)^j\binom{2015}j2^{2015-j} =\frac{(2-1)^{2015}}{2015!}$$ etc.

Consider now $Q(x)=P(x+1)-2P(x)$. This also has degree $2015$, leading coefficient $-a$. and $P(0)=P(1)=\cdots=P(2014)=0$. Therefore $Q(x)=-ax(x-1)(x-2)\cdots(x-2014)$ and then $Q(2015)=P(2016)-2^{2016}=-2015!a$ etc.