How do you find a quadratic approximation to the Fibonacci sequence?

Question

I found this question in a website somewhere, tried solving it, failed. So I'm asking here: How do you find a quadratic approximation to the Fibonacci sequence? By approximation I mean a quadratic $ax^2 + bx + c$ such that for all integer values of $x < n$, $ax^2 + bx + c = f(x)$, where $n$ is maximized, and $f(n)$ is the $n$th Fibonacci number.

Answer 1

Nothing quite like that, however $$ x^2 + xy - y^2 = \pm 1 $$ where $x<y$ are consecutive Fibonacci numbers. $$3^2 + 3 \cdot 5 - 5^2 = -1,$$ $$5^2 + 5 \cdot 8 - 8^2 = 1. $$

Answer 2

To explain "governed by the largest root of an auxiliary polynomial" ... (should be largest in absolute value)

Suppose $u_{n+1}=(\alpha+\beta)u_n-\alpha\beta u_{n-1}$

(and for higher degree recurrences we take corresponding numbers of roots and the relevant symmetric polynomials - for the Fibonacci numbers $\alpha+\beta=1, \alpha\beta=-1$)

Then it is easy to check that $u_n=A\alpha^n +B\beta^n$ is a solution and if $u_0=V, u_1=W$ we have $$V=A+B, W=A\alpha +B\beta$$ So that $W-\beta V=A(\alpha-\beta)$ and $W-\alpha V=B(\beta-\alpha)$ give $A$ and $B$. If we have $|\alpha|\gt |\beta|, A \neq 0$ (so roots are not equal, the coefficient of the largest root is non-zero) then the asymptotic behaviour follows $A\alpha^n$.

Now I expressed the recurrence in terms of $\alpha$ and $\beta$ but generally it will be $u_{n+1}=Pu_n-Q u_{n-1}$ and we recover $\alpha$ and $\beta$ as roots of the auxiliary quadratic $x^2-Px+Q=0$.

Answer 3

For short, there isn't any non-zero polynomial such that $p(x+2)=p(x+1)+p(x)$.
If we assume that the leading coefficient of the LHS is $L\neq 0$, the leading coefficient of the RHS is $2L\neq L$, hence polynomial approximations of the whole Fibonacci sequence are out of question. But clearly one may use Lagrange interpolation to get just a few terms, and $$ F_n \approx \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n $$ is well-known and easy to prove.