2

Fibonacci sequence is defined by $\phi_{n+2} = \phi_n+\phi_{n+1}$ with $\phi_0 =0$ and $\phi_1 = 1$. I saw a proof of explicit form of $\phi_n$ that uses matrices and diagonalisation : $$\begin{bmatrix}\phi_{n+2}\\\phi_{n+1}\end{bmatrix} = A\begin{bmatrix}\phi_{n+1}\\\phi_{n}\end{bmatrix} = A^n\begin{bmatrix}1\\0\end{bmatrix}$$ Then we find $A$ from first equality and from second equality we Binet's formula.

I wonder if this technique can be used to solve other recurrence relations like 1, 2 and 3. I tried this method for 2, but I got a non-diagonalisable matrix; I did the following :

$$\begin{bmatrix}F(n+2)\\F(n+1)\\F(n) \end{bmatrix} = A\begin{bmatrix}F(n+1)\\F(n)\\1 \end{bmatrix} = A^n\begin{bmatrix}2\\4\\1 \end{bmatrix}$$

I got $$A = \begin{bmatrix}4&-3&+16\\1&0&0\\0&1&0\end{bmatrix}$$ which is not diagonalisable according to Symbolab.

Questions :

Is this method applicable to other recurrence than just Fibonacci sequence ? Is there a special name to these recurrence relations ?

user8277998
  • 2,666
  • 3
    A simple introduction here: https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_recurrence_relation.htm. But googling solving linear recurrence relations will lead you to plenty of resources on the subject. Solving with matrices is just another presentation for this technique. – zwim Dec 17 '17 at 21:46

2 Answers2

2

Yes, ultimately, the reason why we end up with diagonalization is because we ended up exponentiation of a matrix $A$, that is we want to compute $A^n$ efficiently.

Suppose the matrix $A$ is diagonalizable, then it can be written as $A=PDP^{-1}$ and $A^n = PD^nP^{-1}$.

Suppose it is not diagonalizable, we still have other decomposition, for instance, we have Jordan canonical form, $A=PJP^{-1}$ and $A^n=PJ^nP^{-1}$.

Formula for exponent of Jordan canonical form can be found here.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
0

Building on Siong's answer, with Jordan normal form we can efficiently exponentiate $A$, but the $A$ in your question with respect to the second example is not quite correct. You should instead be looking for a matrix $A$ such that $$ \begin{bmatrix} F(n + 2) \\ F(n + 1) \\ 1 \end{bmatrix} = A \begin{bmatrix} F(n + 1) \\ F(n) \\ 1 \end{bmatrix} = A^n \begin{bmatrix} 2 \\ 4 \\ 1 \end{bmatrix}. $$ In this case, we have $A = \begin{bmatrix} 4 & -3 & 16 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, J = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix}, P = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & \frac{1}{3} \\ 0 & -\frac{1}{8} & 0 \end{bmatrix}$.

incertia
  • 307