Fibonacci closed form via vector space of infinite sequences of real numbers and geometric sequences

Question

This question is from Linear Algebra with Applications (5th edition) by Otto Bretscher. It is in section 4.1 (Introduction to vector spaces), question 60. Below is the question:

Consider the sequence $(f_0,f_1,f_2,...)$ recursively defined by $f_0=0,f_1=1$, and $f_n=f_{n-2}+f_{n-1}$ for all $n=2,3,4,...$. This is known as the Fibonacci sequence. In this exercise you are invited to derive a closed formula for $f_n$, expressing $f_n$ in terms of $n$, rather than recursively in terms of $f_{n-1}$ and $f_{n-2}$.

1. Find the terms $f_0,f_1,...,f_9,f_{10}$ of the Fibonacci sequence.
2. In the space $V$ of all infinite sequences of real numbers, consider the subset $W$ of all sequences $(x_0,x_1,x_2,...)$ that satisfy the recursive equation $x_n=x_{n-2}+x_{n-1}$ for all $n=2,3,4,...$. Note that the Fibonacci sequence belongs to $W$. Show that $W$ is a subspace of $V$, and find a basis of $W$. Determine the dimension of $W$.
3. Find all geometric sequences of the form $(1,r,r^2,...)$ in $W$. Can you form a basis of $W$ consisting of such sequences?
4. Write the Fibonacci sequences as a linear combination of geometric sequences. Use your answer to find a closed formula for $f_n$ (Binet's formula).
5. Explain why $f_n$ is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right)^n$, for all $n=0,1,2,...$ Use technology to find $f_{50}$.
6. Find $\lim_{n \xrightarrow{} \infty} \frac{f_{n+1}}{f_n}$

For part 2. I found that the first terms of the sequence are $$(x_0,x_1,x_0+x_1,x_0+2x_1,2x_0+3x_1,3x_0+5x_1,5x_0+8x_1,8x_0+13x_1,...)$$ i.e. $$(1x_0,0,1x_0,1x_0,2x_0,3x_0,5x_0,8x_0,...)+(0,1x_1,1x_1,2x_1,3x_1,5x_1,8x_1,13x_1,...)$$ which led me to construct a basis $$\mathfrak{B}=\{(1,0,1,1,2,3,5,8,...), (0,1,1,2,3,5,8,13,...)\}=\{b_1,b_2\}$$ for $W$. So $W$ has dimension 2.

My first question: I am confused why the basis I found seems different from the basis found here: Finding a Basis for the Vector space of sequences of the form $u_{n+1} = u _{n-1} + u_n$? which is $\mathfrak{C}=\{(1,0,1,0,1,0,...),(0,1,1,2,3,5,8,...)\}$. How could one get the first 4 terms, $(x_0,x_1,x_0+x_1,x_0+2x_1,...)$ with a linear combination of $\mathfrak{C}$?

For part 3., I noticed that the first 2 terms of such a geometric sequence will be $(1,r,...)$, which forces us to use weights 1 and r on $\mathfrak{B}$, yielding sequences of the form \begin{aligned} 1b_1+rb_2 &= 1(1,0,1,1,2,3,5,8,...)+r(0,1,1,2,3,5,8,13,...) \\ &= (1,r,1+r,1+2r,2+3r,3+5r,5+8r,8+13r,...) \end{aligned}

So $r^2=1+r$, which has solutions $\phi_+=\frac{1+\sqrt{5}}{2}$ and $\phi_-=\frac{1-\sqrt{5}}{2}$. So all such geometric sequences in $W$ are of the form $$(1,\phi_+,\phi_+^2, \phi_+^3, \phi_+^4 ...)$$ or $$(1,\phi_-, \phi_-^2,\phi_-^3, \phi_-^4...)$$

They are 2 linearly independent vectors in $W$ (since neither is a linear combination of the other), and dim$W=2$, so they must span $W$, so together these form another basis for $W$.

For part 4., using the basis of geometric sequences we have $$\alpha_1(1,\phi_+,...)+\alpha_2(1,\phi_-, ...)=(0,1,...)$$ so $\alpha_2=-\alpha_1$ and $\frac{\alpha_1+\alpha_1\sqrt{5}}{2}-\frac{\alpha_1-\alpha_1\sqrt{5}}{2}=1$, so the weights are $\alpha_1=\frac{1}{\sqrt{5}}$ and $\alpha_2=-\frac{1}{\sqrt{5}}$.

So $$f_n = \frac{1}{\sqrt{5}}\phi_+^n - \frac{1}{\sqrt{5}}\phi_-^n = \frac{1}{\sqrt{5}}(\phi_+^n-\phi_-^n)$$

My second question: for part 5., how do we show $f_n$ is the integer closest to $\frac{1}{\sqrt{5}}\phi_+^n$? Is it because $\phi_-^n$ approaches 0 as $n \xrightarrow{} \infty$?

Also, what is the relationship between this method of finding the closed form of a recurrence and using characteristic polynomials?

Answer 1

For your first question, I wouldn't put too much stock into the linked question, as $(1, 0, 1, 0, 1, 0, \ldots)$ does not satisfy the recurrence relation (note: the 4th term is not the sum of the 2nd and 3rd). Your basis is correct.

For your second question, it is to do with $\phi_{-}^n \to 0$ as $n \to \infty$, but it's more about how quickly it descends to $0$. All you really need is $$\left|\frac{1}{\sqrt{5}}\phi^n_{-}\right| < \frac{1}{2},$$ for $n \ge 0$, so that $\frac{1}{\sqrt{5}}\phi^n_{+}$ is never more than $\frac{1}{2}$ away from the $n$th Fibonacci number. Since $|\phi_-| < 1$, the sequence $\left|\frac{1}{\sqrt{5}}\phi^n_{-}\right|$ is decreasing, so it suffices to check the $n = 0$ case. When $n = 0$, this simplifies to the clearly true inequality $$\frac{1}{\sqrt{5}} < \frac{1}{2},$$ so the desired inequality holds for all $n$.