Let \(S\) be the vector space of complex sequences and define the left-shift operator \[ T(a_1,a_2,a_3,\ldots)=(a_2,a_3,a_4,\ldots). \]
Describe the eigenvectors of \(T\).
Consider the recurrence \[ x_{n+2}=x_{n+1}+x_n. \] Show that its solutions form a two-dimensional subspace \(E\subset S\) with \(T(E)\subset E\), and find an explicit basis for \(E\).
The Fibonacci numbers satisfy \(f_1=f_2=1\) and \(f_{n+2}=f_{n+1}+f_n\). Find an explicit formula for \(f_n\).
Solution
1. A nonzero sequence\[ a=(a_1,a_2,\ldots) \]is an eigenvector of \(T\) with eigenvalue \(\lambda\) if and only if\[ a_{n+1}=\lambda a_n \]for every \(n\geq1\).
The equation \[ T(a)=\lambda a \] means \[ (a_2,a_3,\ldots) = (\lambda a_1,\lambda a_2,\ldots), \] which is exactly the displayed coordinate relation.
2. For every \(\lambda\in\CC\), the \(\lambda\)-eigenspace of \(T\) is\[ \operatorname{span}_{\CC} \left\{ (1,\lambda,\lambda^2,\ldots) \right\}. \]
By step 1, \[ a_n=a_1\lambda^{n-1} \] for every \(n\). If \(a_1=0\), the whole sequence is zero. Thus every nonzero eigenvector is a nonzero scalar multiple of \[ (1,\lambda,\lambda^2,\ldots). \] Conversely, this geometric sequence satisfies \(a_{n+1}=\lambda a_n\), so \[ T(a)=\lambda a. \]
3. Let \(E\) be the set of sequences satisfying\[ x_{n+2}=x_{n+1}+x_n. \]Then \(E\) is a vector subspace of \(S\).
The recurrence is homogeneous and linear. If \(x,y\in E\) and \(a,b\in\CC\), then \[ \begin{aligned} (ax+by)_{n+2} &= a x_{n+2}+b y_{n+2}\\ &= a(x_{n+1}+x_n) + b(y_{n+1}+y_n)\\ &= (ax+by)_{n+1}+(ax+by)_n. \end{aligned} \] Thus \(ax+by\in E\).
4. Every pair\[ (c,d)\in\CC^2 \]occurs as the first two entries of a unique sequence in \(E\).
Starting from \[ x_1=c, \qquad x_2=d, \] the recurrence determines \[ x_3=x_2+x_1, \] then \(x_4=x_3+x_2\), and inductively every later term. Hence existence and uniqueness follow recursively.
5. The map\[ \Phi:E\longrightarrow\CC^2, \qquad \Phi(x)=(x_1,x_2), \]is a linear isomorphism. Consequently,\[ \boxed{ \dim_{\CC}E=2. } \]
Linearity is immediate. Step 4 says precisely that \(\Phi\) is bijective. Therefore \(E\cong\CC^2\).
6. The subspace \(E\) is invariant under \(T\):\[ \boxed{ T(E)\subseteq E. } \]
Let \(x\in E\) and set \[ y=T(x), \qquad y_n=x_{n+1}. \] Then \[ \begin{aligned} y_{n+2} &= x_{n+3}\\ &= x_{n+2}+x_{n+1}\\ &= y_{n+1}+y_n. \end{aligned} \] Thus \(y\in E\).
7. Let\[ \alpha=\frac{1+\sqrt5}{2}, \qquad \beta=\frac{1-\sqrt5}{2}. \]Then\[ \alpha^2=\alpha+1, \qquad \beta^2=\beta+1. \]
The numbers \(\alpha,\beta\) are the two roots of \[ r^2-r-1=0. \]
8. The two sequences\[ u=(1,\alpha,\alpha^2,\ldots) \]and\[ v=(1,\beta,\beta^2,\ldots) \]belong to \(E\).
7. The proof for \(v\) is identical.
9. The sequences \(u\) and \(v\) are linearly independent.
By step 2, \(u\) and \(v\) are eigenvectors of \(T\) with distinct eigenvalues \[ \alpha\neq\beta. \] Eigenvectors belonging to distinct eigenvalues are linearly independent.
10. An explicit basis of \(E\) is\[ \boxed{ \left\{ (1,\alpha,\alpha^2,\ldots), (1,\beta,\beta^2,\ldots) \right\}. } \]
5. Hence they form a basis.
11. Define\[ F_n = \frac{\alpha^n-\beta^n}{\sqrt5}. \]Then\[ F_1=F_2=1. \]
Since \[ \alpha-\beta=\sqrt5, \] one has \[ F_1=1. \] Also \[ \alpha+\beta=1, \] so \[ \begin{aligned} F_2 &= \frac{\alpha^2-\beta^2}{\sqrt5}\\ &= \frac{(\alpha-\beta)(\alpha+\beta)}{\sqrt5}\\ &= 1. \end{aligned} \]
12. The sequence \((F_n)\) satisfies\[ F_{n+2}=F_{n+1}+F_n. \]
By step 7, \[ \alpha^{n+2} = \alpha^{n+1}+\alpha^n \] and \[ \beta^{n+2} = \beta^{n+1}+\beta^n. \] Subtract the two identities and divide by \(\sqrt5\).
13. The Fibonacci numbers are\[ \boxed{ f_n = \frac1{\sqrt5} \left[ \left( \frac{1+\sqrt5}{2} \right)^n - \left( \frac{1-\sqrt5}{2} \right)^n \right]. } \]
Steps <1>11–<1>12 show that \((F_n)\) satisfies the Fibonacci recurrence and the initial conditions \[ F_1=F_2=1. \] By uniqueness of a sequence determined by a second-order recurrence and its first two terms, \[ f_n=F_n \] for every \(n\).
14. Q.E.D.
Step 2 answers part (1), steps <1>5–<1>10 prove part (2), and step 13 answers part (3).