Find $f(2015)$ given the values it attains at $k=0,1,2,\cdots,1007$ 
Let $f$ be a polynomial of degree $1007$ such that $f(k)=2^k$ for $k=0,1,2,\cdots, 1007$. Determine $f(2015)$.

Taking $f(x)=\sum_{n=0}^{1007} a_n x^n $, (whence $a_0=1$), I tried to combine $$a_1=1-\sum_{n=2}^{1007} a_n$$ and the easily derivable $$ a_n = \frac{2^n-1}{n^n} - \sum_{k=1}^{n-1} a_k n^{k-n} - \sum_{k=n+1}^{1007} a_k n^{k-n},$$ hoping to find several null coefficients, but that didn't work. I looked for the solution on Yahoo Answers, and I came to know it's about binomial coefficients, Tartaglia in particular; however the explanation is confusing to me, I'd like a better one, or even a different approach.

You are basically supposed to guess that since $f(x) \approx 2^x = (1 + 1)^k = \sum_{k=0}^{x} {x \choose k} 1^k 1^{x - k}$, that perhaps you can crop the series at $1008$ terms to get $f(x) = \sum_{k = 0}^{1007} {x \choose k}$.
Then use the fact that ${x \choose k} = {x \choose x - k}$ to get $$\sum_{k = 0}^{1007} {x \choose k} = \frac 12 \sum_{k = 0}^{2015} {x \choose k}$$
and apply the binomial sum again with 
$$\sum_{k = 0}^{2015} {x \choose k} = \sum_{k = 0}^{2015} {x \choose k} 1^k 1^{2015 - k} = (1 +1)^{2015}$$
