Find the value of the polynomial at a given point

Question

f is a polynomial of degree $1007$ ,if $f(k) = 2^k$ for $0\le k \le 1007$ find the value of $f(2015)$

The solution should be $f(2015) = 2^{2014}$ and the polynomial $p(x) = \sum_{k=0}^{1007}{x \choose k}$ but i don't get how we can arrive to that.

Answer 1

The idea is to use the identity $$ {{n}\choose{0}}+ {n \choose 1} + \cdots + {n \choose n} = 2^n $$ to create a polynomial of degree 1007 that has the desired properties. We can see that this is true by the binomial theorem. Observe that $$ (x+y)^n = \sum_{k=0}^{n}{n \choose k} x^{n-k} y^{k}, $$ so letting $x = y =1$ we obtain the desired result.

With this result in mind, we can show the polynomial $$ p(x) = \sum_{k=0}^{1007} {x \choose k} $$ satisfies the desired properties. Furthermore, since we are specifying 1008 points that a 1007 degree polynomial maps to, this must be the unique polynomial of this degree that does this. Finally, calculating $p(2015)$ requires a one last binomial coefficient identity. For any $n$ and $k$, $$ {n \choose k} = {n \choose n-k}. $$ Using this and the previous identity, we see that for any Odd $n = 2n' + 1$, \begin{align*} 2^n &= \sum_{k=0}^{n} {n \choose k} \\ & = \sum_{k=0}^{n'} {n \choose k} + \sum_{k=n'+1}^{n} {n \choose k} \\ & = \sum_{k=0}^{n'} {n \choose k} + \sum_{k=n'+1}^{n} {n \choose n - k}. \end{align*} The latter sum is equal to ${n \choose n'} + {n \choose n' -1 }+ ... + {n \choose 0} $, while the former is equal to ${n \choose 0} + ... + {n \choose n'}$. Therefore, they are equal, so \begin{align*} 2^n &= 2 \sum_{k=0}^{n'} {n \choose k} \\ & \text{and} \\ 2^{n-1} &=\sum_{k=0}^{n'} {n \choose k}. \end{align*} This identity allows us to calculate $p(2015)$. Observe that $2015 = 2 \times 1007 +1$. Then by the above identity,

\begin{align*} p(2015) & = \sum_{k=0}^{1007} {2015 \choose k} \\ & = 2^{2015-1} \\ &= 2^{2014}, \end{align*} as desired.

Answer 2

Hint $\ $ Write $\,f(x) = c_0 + c_1 x + c_2 x(x-1) + c_3 x(x-1)(x-2) + \cdots$ then successively evaluate at $\,x=0,1,2\ldots$ to deduce $\,c_n = 1/n!\,\ $ (this is essentially Newton interpolation).