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.

Similar problem: https://math.stackexchange.com/questions/1177129/find-the-value-of-the-polynomial-at-a-given-point — Arnaldo, Jul 05 '18 at 16:24
If you think that $Q(x)$ is a polynomial: what is its degree? What is the degree of $x^{2015}-2^x$? of $x^2-2015^x$? of $x^x$? — Greg Martin, Jul 05 '18 at 16:28
Possible duplicate of Find the value of the polynomial at a given point — Arnaldo, Jul 05 '18 at 16:56

lhf · Accepted Answer · 2018-07-05T16:51:29.913

5

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

edited Jul 05 '18 at 16:51

answered Jul 05 '18 at 16:37

lhf

216,483

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

score 2 · Answer 2 · edited Jul 05 '18 at 17:00

2

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

edited Jul 05 '18 at 17:00

Daniel Buck

3,564

answered Jul 05 '18 at 16:20

Dr. N.Padmanabhan

91

1

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 05 '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 05 '18 at 17:08

score 2 · Answer 3 · answered Jul 05 '18 at 16:37

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.

Degree $2015$ polynomial value at $2016$

3 Answers3