fibonacci_sequence
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
fibonacci_sequence [2023/07/26 13:49] – raju | fibonacci_sequence [2023/08/05 11:05] (current) – [References] raju | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ==== dummy ==== | + | ==== Definition |
Recurrence relation | Recurrence relation | ||
$$F_0 = 0, \quad F_1 = 1$$ | $$F_0 = 0, \quad F_1 = 1$$ | ||
Line 13: | Line 13: | ||
The sequence is (0, 1, 1, 2, 3, 5, 8, 13, ... ) | 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 | ||
+ | |||
+ | ==== Eigen values of A ==== | ||
+ | To get the eigen values, solve | ||
+ | $$ \begin{vmatrix} | ||
+ | 1 - \lambda & 1 \\ | ||
+ | 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}, | ||
+ | $$ | ||
+ | Also, note | ||
+ | $$ \lambda_1 - \lambda_2 = \sqrt{5} $$ | ||
+ | |||
+ | ==== Eigen vectors of A ==== | ||
+ | To get the eigen vectors, solve | ||
+ | $$ | ||
+ | \begin{bmatrix} | ||
+ | 1 - \lambda & 1 \\ | ||
+ | 1 & -\lambda | ||
+ | \end{bmatrix} | ||
+ | \begin{bmatrix} | ||
+ | x_1 \\ | ||
+ | x_2 | ||
+ | \end{bmatrix} | ||
+ | = | ||
+ | \begin{bmatrix} | ||
+ | 0 \\ | ||
+ | 0 | ||
+ | \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$, | ||
+ | |||
+ | \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 & 1 | ||
+ | \end{bmatrix} | ||
+ | $$ | ||
+ | |||
+ | |||
+ | ==== References ==== | ||
+ | * https:// | ||
+ | * https:// | ||
+ | * https:// | ||
+ | * https:// | ||
+ | * https:// | ||
+ | * tags | big parentheses | ||
fibonacci_sequence.1690379388.txt.gz · Last modified: 2023/07/26 13:49 by raju