1

$$\left( \left( 1/2\,{\frac {-\beta+ \sqrt{{\beta}^{2}-4\,\delta\, \alpha}}{\alpha}} \right) ^{i}- \left( -1/2\,{\frac {\beta+ \sqrt{{ \beta}^{2}-4\,\delta\,\alpha}}{\alpha}} \right) ^{i} \right) \left( \sqrt{{\beta}^{2}-4\,\delta\,\alpha} \right) ^{-1}$$

What exactly is the connection between the above formula and $$x^2-x-c$$ c being a constant. I know about linear recursion, but I don't understand why the Fibonacci Numbers are associated with $$x^2-x-1$$ I know about $${\frac {\sqrt {5}+1}{{2}}}$$

But I don't see the connection. If I were to represent these terms algebraically it seems I would do something like this:

$${\alpha}^{-1}$$ $$-{\frac {\beta}{{\alpha}^{2}}}$$ $$-{\frac {-{\beta}^{2}+\delta\,\alpha}{{\alpha}^{3}}}$$ $${\frac {\beta\, \left( -{\beta}^{2}+2\,\delta\,\alpha \right) }{{ \alpha}^{4}}}$$ $${\frac {{\beta}^{4}-3\,{\beta}^{2}\delta\,\alpha+{\delta}^{2}{\alpha}^ {2}}{{\alpha}^{5}}}$$ $$-{\frac {\beta\, \left( {\beta}^{4}-4\,{\beta}^{2}\delta\,\alpha+3\,{ \delta}^{2}{\alpha}^{2} \right) }{{\alpha}^{6}}} $$

There also seems to be a relationship with factorials when they are used as arrays in matrices.

Joe
  • 4,757
  • 5
  • 35
  • 55
Thomas Olson
  • 63
  • 6
  • Letting $\varphi$ and $\psi$ (respectively) be the positive and negative roots of $x^2-x-1$, the Fibonacci sequence has closed form $$F_i=\left(\varphi^i-\psi^i\right)(\sqrt{5})^{-1},$$ which is of the form you gave, with $\alpha=1,\beta=\delta=-1$. – Cameron Buie Mar 26 '13 at 21:07

3 Answers3

4

Let $F_0=0$, $F_1=1$, $\forall n \in \Bbb N, F_{n+2}=F_{n+1}+F_n$

It's the Fibonacci sequence.

Now let $\forall n \in \Bbb N,V_n=\begin{pmatrix} F_n\\F_{n+1}\end{pmatrix}$

Let $M=\begin{pmatrix}0 & 1\\ 1 & 1\end{pmatrix}$

Then $MV_n=\begin{pmatrix}0 & 1\\ 1 & 1\end{pmatrix}\begin{pmatrix} F_n\\F_{n+1}\end{pmatrix}=\begin{pmatrix} F_{n+1}\\F_n+F_{n+1}\end{pmatrix}$

By induction, $\forall n \in \Bbb N, V_n=M^nV_0$

So the only thing we really need to compute is $M^n$. In order to do this, we try do diagonalize it.

Its characteristic polynomial is $\chi_M(\lambda)=\det(M-\lambda I_2)=\det \begin{pmatrix}-\lambda & 1\\ 1 & 1-\lambda\end{pmatrix}=(-\lambda)(1-\lambda)-(1)(1)=\lambda^2-\lambda-1$

Let $\varphi=\cfrac{1+\sqrt{5}}{2}$ and $\psi=\cfrac{1-\sqrt{5}}{2}$ be the two roots of that polynomial.

Since $M\in M_2(\Bbb R)$, we can find $P\in GL_2(\Bbb R)$ so that $M=PDP^{-1}$ where $D=\begin{pmatrix}\varphi & 0\\ 0 & \psi\end{pmatrix}$

$D$ is the matrix of the canonical endomophism associated to $M$ in a basis $e=(e_1,e_2)$ where $Me_1=\varphi e_1$ and $Me_2=\psi e_2$

We know that $e_1\in Ker(M-\varphi I_2) = Ker\left(\begin{pmatrix}-\varphi & 1\\ 1 & 1-\varphi\end{pmatrix}\right)=Vect\left(\begin{pmatrix}\cfrac{1}{\varphi}\\1\end{pmatrix}\right)$ because $\cfrac{1}{\varphi}\begin{pmatrix}-\varphi\\ 1 &\end{pmatrix}+1\begin{pmatrix} 1\\ 1-\varphi\end{pmatrix}=\begin{pmatrix} 0\\0\end{pmatrix}$ so we can take $e_1=\varphi\begin{pmatrix}\cfrac{1}{\varphi}\\ 1\end{pmatrix}=\begin{pmatrix}1\\ \varphi\end{pmatrix}$

Similarly, $e_2\in Ker(M-\psi I_2) = Ker\left(\begin{pmatrix}-\psi & 1\\ 1 & 1-\psi\end{pmatrix}\right)=Vect\left(\begin{pmatrix}\cfrac{1}{\psi}\\1\end{pmatrix}\right)$ because $\cfrac{1}{\psi}\begin{pmatrix}-\psi\\ 1 &\end{pmatrix}+1\begin{pmatrix} 1\\ 1-\psi\end{pmatrix}=\begin{pmatrix} 0\\0\end{pmatrix}$ so we can take $e_2=\psi\begin{pmatrix}\cfrac{1}{\psi}\\ 1\end{pmatrix}=\begin{pmatrix}1\\ \psi\end{pmatrix}$

And we get $P=\begin{pmatrix}1 & 1\\ \varphi & \psi\end{pmatrix}$

Then we need $P^{-1}=\cfrac{\begin{pmatrix}\psi & -1\\ -\varphi & 1\end{pmatrix}}{\psi-\varphi}$

Then $M^n=(PDP^{-1})^n=PD^nP^{-1}$ and $D^n=\begin{pmatrix}\varphi & 0\\ 0 & \psi\end{pmatrix}^n=\begin{pmatrix}\varphi^n & 0\\ 0 & \psi^n\end{pmatrix}$

So $\begin{pmatrix} F_n\\F_{n+1}\end{pmatrix}=V_n=PD^nP^{-1}V_0=\cfrac{1}{\psi-\varphi}\begin{pmatrix}1 & 1\\ \varphi & \psi\end{pmatrix}\begin{pmatrix}\varphi^n & 0\\ 0 & \psi^n\end{pmatrix}\begin{pmatrix}\psi & -1\\ -\varphi & 1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\cfrac{1}{\psi-\varphi}\begin{pmatrix}1 & 1\\ \varphi & \psi\end{pmatrix}\begin{pmatrix}\varphi^n & 0\\ 0 & \psi^n\end{pmatrix}\begin{pmatrix}-1\\1\end{pmatrix}=\cfrac{1}{\psi-\varphi}\begin{pmatrix}1 & 1\\ \varphi & \psi\end{pmatrix}\begin{pmatrix}-\varphi^n\\\psi^n\end{pmatrix}=\cfrac{1}{\psi-\varphi}\begin{pmatrix}1 & 1\\ \varphi & \psi\end{pmatrix}\begin{pmatrix}-\varphi^n\\\psi^n\end{pmatrix}=\cfrac{1}{\psi-\varphi}\begin{pmatrix}-\varphi^n+\psi^n\\-\varphi^{n+1}+\psi^{n+1}\end{pmatrix}=\begin{pmatrix}\cfrac{\psi^n-\varphi^n}{\psi-\varphi}\\ \cfrac{\psi^{n+1}-\varphi^{n+1}}{\psi-\varphi}\end{pmatrix}$

From which we can deduce $F_n = \cfrac{\psi^n-\varphi^n}{\psi-\varphi}$

It's more often written as $\cfrac{\varphi^n-\psi^n}{\varphi-\psi}$ because $\varphi-\psi=\sqrt{5}$ whereas $\psi-\varphi=-\sqrt{5}$.

And we finally get $\boxed{F_n = \cfrac{\varphi^n-\psi^n}{\sqrt{5}}}$

xavierm02
  • 7,495
2

If $f(X) = \sum_{k=0}^{\infty} F_k X^k$ as a formal power series, where $F_k$ is the $k$-th Fibonacci number, i.e. $$F_0 = 0, F_1 = 1, F_k = F_{k-1} + F_{k-2} \; (k \ge 2),$$ then $$f(X) = X + \sum_{k=0}^{\infty} F_{k+2} X^{k+2} = X + \sum_{k=0}^{\infty} F_k X^{k+2} + \sum_{k=0}^{\infty} F_k X^{k+1}$$ $$= X + X^2 f(X) + X f(X).$$ Thus $$f(X) = \frac{X}{X^2 - X - 1}$$ and this gives a connection. Using partial fractions decomposition and comparing coefficients, you can get an explicit formula as well.

Cocopuffs
  • 10,307
1

If you start with $x^2 - x - 1$ and make it homogeneous, $x^2 - x y - y^2,$ the result relates to Fibonacci numbers in that $$ F_{n+1}^2 - F_{n+1} F_n - F_n^2 = (-1)^n. $$ This uses numbering $$ F_0 = 0, \; F_1 = 1, \; F_2 = 1, \; F_3 = 2, \; F_4 = 3, \; F_5 = 5, \ldots $$ and $$ x = F_{n+1}, \; y = F_n. $$

It's just one of those things. $x^2 - x y - y^2$ is called an (indefinite) quadratic form.

Will Jagy
  • 139,541