2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?" $\endgroup$ – PersonX Jul 5 '18 at 16:43
  • $\begingroup$ @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. $\endgroup$ – Daniel Buck Jul 5 '18 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.