# Degree $2015$ polynomial value at $2016$

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.

## 3 Answers

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

• What do you mean by repeated differences? – MalayTheDynamo Jul 5 '18 at 16:38
• @MalayTheDynamo, see my edited answer – lhf Jul 5 '18 at 16:41

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.

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

• I don't think it's fair to downvote this. OP originally just asked "Where did I go wrong?", and this post answers that original question completely. OP later added "and how do I get the correct answer?" – PersonX Jul 5 '18 at 16:43
• @PersonX I agree. The reason given is exactly why the answer is wrong, and you're right the OP later added "and how do I get the correct answer?" after Dr. N.Padmanabhan's answer. I reformatted the answer Dr. N.Padmanabhan, hope this is ok. – Daniel Buck Jul 5 '18 at 17:08