Add Me!Close Menu Navigation

Analytical Fibonacci

We derive Binet’s equation for the nth Fibonacci number as

     $$ F_n = \frac{1}{\sqrt 5}\left( \left(\frac{1+\sqrt 5}{2}\right)^n -  \left(\frac{1-\sqrt 5}{2}\right)^n  \right) $$

Using the method derived in the previous article, we first solve the characteristic polynomial associated with the linear recurrence

    \begin{align*} F_0 &= 0 \\ F_1 &= 1 \\ F_n &= 1 \times F_{n-1} + 1 \times F_{n-2} \end{align*}

described by

    \[p_A(\lambda) = \lambda^2 - \lambda - 1\]

Via the quadratic equation, we see that the solution to p_A(\lambda) = 0 gives solutions \lambda_1, \lambda_2 = \frac{1 \pm \sqrt 5}{2}.

Therefore, the coefficients \alpha of x_n = \alpha_1 \left(\frac{1 + \sqrt 5}{2}\right)^n + \alpha_2 \left(\frac{1 - \sqrt 5}{2}\right)^n are

    \begin{align*} \left(\begin{array}{c} \alpha_1 \\ \alpha_2 \end{array}\right) &= \left(\begin{array}{cc} 1 & 1 \\ \frac{1 + \sqrt 5}{2}\right & \frac{1 - \sqrt 5}{2}\right \end{array}\right)^{-1}\left(\begin{array}{c} 0 \\ 1 \end{array}\right) \\ &= \left(\begin{array}{c} \frac{1}{\sqrt 5} \\ -\frac{1}{\sqrt 5} \end{array}\right)  \end{align*}

therefore giving x_n = \frac{1}{\sqrt 5}\left( \left(\frac{1+\sqrt 5}{2}\right)^n -  \left(\frac{1-\sqrt 5}{2}\right)^n  \right). \blacksquare

Posted By Lee

Woosh

Recent Comments