I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got.
Let $p(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+a_0$ . Construct the polynomials $p_1(x)=a_n(x-1)^n+a_{n-1}(x-1)^{n-1}+\dots +a_1(x-1)+a_0$ and $p_2(x)=a_n(x-2)^n+a_{n-1}(x-2)^{n-1}+\dots +a_1(x-2)+a_0$.
Then the polynomial $p-(p_1+p_2)$ has infinitely many roots since $p(i)=p_1(i)+p_2(i)$ for $i$ an integer $\ge 1$ because of the Fibonacci recurrence. Hence we have $p_1+p_2=p$ since a non-zero polynomial of degree $n$ can have at most $n$ zeros.
However $p_1+p_2$ has leading coefficient $2a_n$. So they cannot be equal.
What do you think of my proof. Can you find other proofs? Simpler proofs? harder proofs? The less standard the better. I appreciate proofs which might look excessive in the amount of theory they use, although only if they finish quickly.
Thank you very much.
Regards
Best Answer
Taking successive differences of a nonzero polynomial should result in a polynomial of the next smallest degree. That is, if $p$ is degree $n$, then $p(x)-p(x-1)$ should be of degree $n-1$.
But if $p(i)$ gives Fibonacci numbers, then $p(i)-p(i-1)=p(i-2)$. So $\deg p=\deg(p)-1$, a contradiction. (This is a different take on your argument (which is great) since you asked about alternatives.)