Differences

This shows you the differences between two versions of the page.

--- fibonacci_sequence [2023/07/26 13:44] – created raju
+++ fibonacci_sequence [2023/08/05 11:05] (current) – [References] raju
@@ Line 1: / Line 1: @@
-==== dummy ====
+==== Definition ====
 Recurrence relation
 $$F_0 = 0, \quad F_1 = 1$$
@@ Line 9: / Line 9: @@
 The first 20 Fibonacci numbers $F_n$ are:
-^ F_0 ^ F_1 ^ F_2 ^ F_3 ^ F_4 ^ F_5 ^ F_6 ^ F_7 ^ F_8 ^ F_9 ^ F_10 ^ F_11 ^ F_12 ^ F_13 ^ F_14 ^ F_15 ^ F_16 ^ F_17 ^ F_18 ^ F_19 ^
+^ $ F_0 $ ^ $ F_1 $ ^ $ F_2 $ ^ $ F_3 $ ^ $ F_4 $ ^ $ F_5 $ ^ $ F_6 $ ^ $ F_7 $ ^ $ F_8 $ ^ $ F_9 $ ^ $ F_{10} $ ^ $ F_{11} $ ^ $ F_{12} $ ^ $ F_{13} $ ^ $ F_{14} $ ^ $ F_{15} $ ^ $ F_{16} $ ^ $ F_{17} $ ^ $ F_{18} $ ^ $ F_{19} $ ^
 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 |
+The sequence is (0, 1, 1, 2, 3, 5, 8, 13, ... )
+==== Matrix form ====
+$$ {F_{k+2} \choose F_{k+1}} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} {F_{k+1} \choose F_{k}} $$
+$$ \vec F_{k+1} = \mathbf{A} \vec F_{k} $$
+$$ \vec F_n = \mathbf{A}^n  \vec F_0 $$
+==== Eigen values of A ====
+To get the eigen values, solve
+$$ \begin{vmatrix}
+- \lambda & 1 \\
+& -\lambda
+\end{vmatrix} = 0
+$$
+\begin{align}
+(1-\lambda)(-\lambda) - 1 & = 0 \\
+(\lambda)(\lambda - 1) - 1 & = 0 \\
+\lambda^2 - \lambda -1 & = 0
+\end{align}
+If we denote the eigen values as $ \lambda_1, \lambda_2 $, this tells us that
+$$ \lambda_1 + \lambda_2 = 1, \quad \lambda_1 \lambda_2 = -1 $$
+Solving the quadratic equation, we get
+$$
+\left( \lambda_1, \lambda_2 \right) = \left( \frac{1+\sqrt{5}}{2}, \frac{1-\sqrt{5}}{2} \right)
+$$
+Also, note
+$$ \lambda_1 - \lambda_2 = \sqrt{5} $$
+==== Eigen vectors of A ====
+To get the eigen vectors, solve
+$$
+\begin{bmatrix}
+- \lambda & 1 \\
+& -\lambda
+\end{bmatrix}
+\begin{bmatrix}
+x_1 \\
+x_2
+\end{bmatrix}
+=
+\begin{bmatrix}
+\\
+\end{bmatrix}
+$$
+Expanding
+\begin{align}
+(1-\lambda) x_1 + x_2 & = 0 \\
+x_1 & = \lambda x_2
+\end{align}
+From the characteristic equation of $ \mathbf{A} $, we know
+\begin{align}
+& (1-\lambda)(-\lambda) - 1 = 0 \\
+\Rightarrow \quad & (1-\lambda) = -\frac{1}{\lambda}
+\end{align}
+Substituting for $1-\lambda$, we get
+\begin{align}
+-\frac{1}{\lambda} x_1 + x_2 & = 0 \\
+x_1 & = \lambda x_2
+\end{align}
+So both equations simplify to
+$$ x_1 = \lambda x_2$$
+which gives the eigen vector matrix as
+$$
+\Lambda =
+\begin{bmatrix}
+\lambda_1 & \lambda_2 \\
+& 1
+\end{bmatrix}
+$$
+==== References ====
+  * https://www.dokuwiki.org/plugin:mathjax - mathjax syntax of dokuwiki
+  * https://tex.stackexchange.com/questions/162533/how-to-align-implies-that-symbols-neatly-in-equation-array - talks about alignat which can be used to align 'implies that' symbols in an equation array. I picked up ''\Rightarrow\quad'' from here.
+  * https://mathworld.wolfram.com/CharacteristicEquation.html
+  * https://www.math-linux.com/latex-26/faq/latex-faq/article/how-to-write-matrices-in-latex-matrix-pmatrix-bmatrix-vmatrix-vmatrix - nice visual representation of how various matrix environments work in latex
+  * https://tex.stackexchange.com/questions/78736/bigger-parentheses-in-equations - picked up ''\left( ... \right)'' from here.
+    * tags | big parentheses