Expect Fibonacci

We will use n=10 as an example, and it is easy to see that this method generalizes to all other n. We can use a difference table to find the polynomial that passes through the first nine points (i.e. $f_{10} (x)$ ). $\begin{array}{c}\\ 1&0&1&-1&2&-3&5&-8&13 \\ 1&1&0&1&-1&2&-3&5 \\ 2&1&1&0&1&-1&2 \\ 3&2&1&1&0&1 \\ 5&3&2&1&1 \\ 8&5&3&2 \\ 13&8&5 \\ 21&13 \\ 34 \end{array}$ Because this is a degree 8 polynomial, the 8th column (after the initial column) will be constant, so we can put another 13 below the last 13 in the table and work backwards to find $f_{10} (10)$ . $\begin{array}{c}\\ 1&0&1&-1&2&-3&5&-8&13 \\ 1&1&0&1&-1&2&-3&5&13 \\ 2&1&1&0&1&-1&2&18 \\ 3&2&1&1&0&1&20 \\ 5&3&2&1&1&21 \\ 8&5&3&2&22 \\ 13&8&5&24 \\ 21&13&29 \\ 34&42 \\ 76 \end{array}$ Notice that $f_{10} (10)$ was just the number that we placed under the final 13 (which in this case happened to also be a 13) plus the entire diagonal. In other words if we changed the number we placed below the final 13 by a certain amount, it would change $f_{10} (10)$ by the same amount. Now we just need to think about what number we would have placed in that spot if we wanted the actual Fibonacci sequence, not the expected Fibonacci sequence. It is easy to see that because we are taking the forward difference to obtain the next column in the difference table, each column is the Fibonacci sequence shifted down. This means that the rows are the Fibbonacci sequence extended in the negative direction (also the Fibonacci sequence with alternating signs). Thus we can see that we would have placed a -8, not a 13 in the final spot, giving the difference between expected and actual Fibonacci of 8+13=21 (this generalizes for all n, the only difference being sign changes, but the absolute value function takes care of that). This is the definition for the next Fibbonaci number (after 8 and 13), so $\big|^e F_n - F_n \big|=F_{n-2}$ The ratio between large Fibonacci numbers approaches $\phi=\frac{1+\sqrt5}2$ , so our answer is $\frac{1}{\phi^2} \approx 0.381966$

Let $G_n(X)$ be the polynomial of degree $n-1$ such that $G_n(j) = F_j$ for $1 \le j \le n$ . Lagrangian interpolation gives us that $\begin{aligned} G_n(X) & = \; \sum_{u=1}^n F_u \prod_{{1 \le v \le n} \atop {v \neq u}} \frac{X-v}{u-v} \; = \; \sum_{u=1}^n \frac{F_u}{(-1)^{n-u}(u-1)!(n-u)!}\prod_{{1 \le v \le n} \atop {v \neq u}} (X-v) \\ & = \; \frac{1}{(n-1)!} \sum_{u=1}^n (-1)^{n-u}\binom{n-1}{u-1}F_u \prod_{{1 \le v \le n} \atop {v \neq u}}(X-v) \end{aligned}$ and so the leading coefficient of $G_n(X)$ is $\alpha_n \; = \; \frac{1}{(n-1)!}\sum_{u=1}^n (-1)^{n-u}\binom{n-1}{u-1}F_u$ Using Binet's Formula for the Fibonacci numbers, and writing $\phi = \tfrac12(1 + \sqrt{5})$ and $\psi = \tfrac12(1 - \sqrt{5})$ , we see that $\begin{aligned} \alpha_n & = \; \frac{1}{\sqrt{5}(n-1)!}\sum_{u=1}^n (-1)^{n-u}\binom{n-1}{u-1} \big[\phi^u - \psi^u\big] \; = \; \frac{1}{\sqrt{5}(n-1)!}\sum_{u=0}^{n-1} (-1)^{n-1-u}\binom{n-1}{u} \big[\phi^{u+1} - \psi^{u+1}\big] \\ &= \; \frac{1}{\sqrt{5}(n-1)!}\big[ \phi(\phi-1)^{n-1} - \psi(\psi-1)^{n-2}\big] \; = \; \frac{1}{\sqrt{5}(n-1)!}\big[\phi(-\psi)^{n-1} - \psi(-\phi)^{n-1}\big] \\ & = \; \frac{1}{\sqrt{5}(n-1)!}\big[(-\psi)^{n-2} - (-\phi)^{n-2}\big] \; = \; \frac{(-1)^{n-1}}{\sqrt{5}(n-1)!}\big[\phi^{n-2} - \psi^{n-2}\big] \; = \; \frac{(-1)^{n-1}}{(n-1)!}F_{n-2} \end{aligned}$ On the other hand we know that $G_{n+1}(X) - G_n(X)$ is a degree $n$ polynomial that vanishes at $1,2,...,n$ , and so there is a constant $\beta$ such that $G_{n+1}(X) - G_n(X) \; = \; \beta(X-1)(X-2)\cdots (X-n)$ From this it is clear that $\beta = \alpha_{n+1}$ is the leading coefficient of $G_{n+1}(X)$ . Putting $X = n+1$ we see that $\begin{aligned} G_{n+1}(n+1) - G_n(n+1) & = \; \alpha_{n+1} n! \\ F_{n+1} - {}^eF_{n+1} & = \; (-1)^n F_{n-1} \end{aligned}$ so that $\lim_{n \to \infty} \frac{|F_n - {}^eF_n|}{F_n} \; = \; \lim_{n \to \infty}\frac{F_{n-1}}{F_{n+1}} \; = \; \phi^{-2} \; = \; \boxed{\tfrac12(3 - \sqrt{5})}$ using Binet's Formula again to evaluate this limit.