Generalised Fibonacci Sequence & Linear Algebra

Question

Consider a generalised fibonacci $G$ sequence $1, 1, 1, 3, 5, 9, 17...$ that's created by summing the last 3 entries in the sequence together:

$G_0 = 1, G_1 = 1, G_2 = 1$ and $G_{n+1} = G_n + G_{n-1} + G_{n-2}$ for $n \ge 2$.

1) Find a $3 \times3$ matrix M such that, for any $k \ge 2$, $$\begin{pmatrix} G_{k+1} \\ G_k \\ G_{k-1} \end{pmatrix} = M \begin{pmatrix} G_{k} \\ G_{k-1} \\ G_{k-2} \end{pmatrix}$$

I figured out that $M = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ from the given equation.

2) Find a numerical value for $G_{25}$

With a bit of thinking, I came up with the equation $$\begin{pmatrix} G_{k+1} \\ G_k \\ G_{k-1} \end{pmatrix} = M^k \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$$ Hence $G_{25}$ would be obtained by the first element from $M^{24}$ times [1, 1, 1]. Using a calculator, I got $3311233$, which apparently is wrong. Was my equation above wrong? How could I approach this?

Find limit of $\frac{\ln G_n}{n}$ to 10 decimal places as $n$ goes to $\infty$.

I have no idea how to approach this. I thought of using eigenvalues and eigenvectors, but since the M I found only gives me one real value of 1.83929... I don't quite see how that's going to be useful. Any help would be really appreciated.

Answer 1

The provided equation is wrong, as you should have

$$\begin{bmatrix}G_{k+2}\\G_{k+1}\\G_k\end{bmatrix}=M^k\begin{bmatrix}1\\1\\1\end{bmatrix}$$

which matches when $k=0$. The computation of $G_k$ from this can be done in several ways. One way is to diagonalize $M$, which would reduce computing $M^k$ down to computing $\lambda^k$ for each eigenvalue $\lambda$. The largest eigenvalue, the supergolden ratio $\psi$, then determines the asymptotic behavior

$$\lim_{n\to\infty}\frac{\ln(G_n)}n=\lim_{n\to\infty}\ln\frac{G_{n+1}}{G_n}=\ln(\psi)\simeq3822450858$$

of the supergolden sequence. The characteristic polynomial of the matrix

$$\det(M-\lambda I)=\det\begin{bmatrix}1-\lambda&1&1\\1&-\lambda&0\\0&1&-\lambda\end{bmatrix}=1+\lambda+\lambda^2-\lambda^3$$

matches the characteristic equation of the recurrence. The eigendecomposition is given by

$$M=Q\Lambda Q^{-1}$$

where

$$Q\simeq\begin{bmatrix}3.38298&-0.191488-0.508852i&-0.191488+0.508852i\\1.83929&-0.419643+0.606291i&-0.419643-0.606291i\\1&1&1\end{bmatrix}$$

are the eigenvectors and

$$\Lambda\simeq\begin{bmatrix}1.83929&0&0\\0&-0.419643+0.606291i&0\\0&0&-0.419643-0.606291i\end{bmatrix}$$

are the eigenvalues. Only 6 significant figures are shown here, but in order to compute $M^{23}$ accurately enough, more figures are probably needed.

Without involving non-integral values, the computation of $G_n$ can be done quickly using exponentiation by squaring. For $G_{25}$, we get

\begin{align}\begin{bmatrix}G_{25}\\G_{24}\\G_{23}\end{bmatrix}&=\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}^{23}\begin{bmatrix}1\\1\\1\end{bmatrix}=\left(\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}^2\right)^{11}\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}\begin{bmatrix}1\\1\\1\end{bmatrix}\\&=\begin{bmatrix}2&2&1\\1&1&1\\1&0&0\end{bmatrix}^{11}\begin{bmatrix}3\\1\\1\end{bmatrix}=\left(\begin{bmatrix}2&2&1\\1&1&1\\1&0&0\end{bmatrix}^2\right)^5\begin{bmatrix}2&2&1\\1&1&1\\1&0&0\end{bmatrix}\begin{bmatrix}3\\1\\1\end{bmatrix}\\&=\begin{bmatrix}7&6&4\\4&3&2\\2&2&1\end{bmatrix}^5\begin{bmatrix}9\\5\\3\end{bmatrix}=\left(\begin{bmatrix}7&6&4\\4&3&2\\2&2&1\end{bmatrix}^2\right)^2\begin{bmatrix}7&6&4\\4&3&2\\2&2&1\end{bmatrix}\begin{bmatrix}9\\5\\3\end{bmatrix}\\&=\begin{bmatrix}81&68&44\\44&37&24\\24&20&13\end{bmatrix}^2\begin{bmatrix}105\\57\\31\end{bmatrix}=\begin{bmatrix}81&68&44\\44&37&24\\24&20&13\end{bmatrix}\begin{bmatrix}13745\\7473\\4063\end{bmatrix}\\&=\begin{bmatrix}\color{#ef3322}{1800281}\\978793\\532159\end{bmatrix}\end{align}

Answer 2

Let $\lambda_1$, $\lambda_2$, $\lambda_3$ be the eigenvalues of $M=\begin{bmatrix}1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{bmatrix}$, then they all satisfy the characteristic equation $\lambda^3=\lambda^2+\lambda+1$.

Also, the eigenvector $v_1$ corresponding to the eigenvalue $\lambda_1$ belongs to the Nullspace of $M-\lambda_1I=\begin{bmatrix}1-\lambda_1 & 1 & 1 \\ 1 & -\lambda_1 & 0 \\ 0 & 1 & -\lambda_1\end{bmatrix}\leftrightarrow \begin{bmatrix}1-\lambda_1 & 1 & 1 \\ 0 & -\lambda_1 - \frac{1}{1-\lambda_1} & - \frac{1}{1-\lambda_1} \\ 0 & 1 & -\lambda_1\end{bmatrix}\leftrightarrow \begin{bmatrix}1-\lambda_1 & 1 & 1 \\ 0 & \frac{-\lambda_1+\lambda_1^2-1}{1-\lambda_1} & - \frac{1}{1-\lambda_1} \\ 0 & 0 & \frac{\lambda_1^2 + \lambda_1 +1-\lambda_1^3}{-\lambda_1+\lambda_1^2-1}\end{bmatrix}\leftrightarrow \begin{bmatrix}1-\lambda_1 & 1 & 1 \\ 0 & \frac{-\lambda_1+\lambda_1^2-1}{1-\lambda_1} & - \frac{1}{1-\lambda_1} \\ 0 & 0 & 0\end{bmatrix}$

and setting the free variable to $1$ and from $(M-\lambda_1I)v_1=0$, we obtain $v_1=\begin{bmatrix}\lambda_1^2\\\lambda_1\\1\end{bmatrix}$.

Similarly, we have $v_2=\begin{bmatrix}\lambda_2^2\\\lambda_2\\1\end{bmatrix}$ and $v_3=\begin{bmatrix}\lambda_3^2\\\lambda_3\\1\end{bmatrix}$

Now, $\begin{bmatrix}1\\1\\1\end{bmatrix} \in Span(v_1, v_2,v_3)$, hence $\begin{bmatrix}1\\1\\1\end{bmatrix}=a.\begin{bmatrix}\lambda_1^2\\\lambda_1\\1\end{bmatrix}+b.\begin{bmatrix}\lambda_2^2\\\lambda_2\\1\end{bmatrix}+c.\begin{bmatrix}\lambda_3^2\\\lambda_3\\1\end{bmatrix}$, for some $a,b,c$, solving which we get

$a=\frac{(1-\lambda_2)(1-\lambda_3)}{(\lambda_1-\lambda_2)(\lambda_1-\lambda_3)}$, $b=\frac{(1-\lambda_1)(1-\lambda_3)}{(\lambda_2-\lambda_1)(\lambda_2-\lambda_3)}$ $c=\frac{(1-\lambda_1)(1-\lambda_2)}{(\lambda_3-\lambda_1)(\lambda_3-\lambda_2)}$

Also, we have,

$\begin{bmatrix}G_{n}\\G_{n-1}\\G_{n-2}\end{bmatrix}=M^{n-2}\begin{bmatrix}1\\1\\1\end{bmatrix}$

$\begin{align}=&M^{n-2}(a.v_1+b.v_2+c.v_3)\\=&a.M^{n-2}v_1+b.M^{n-2}v_2+c.M^{n-2}v_3\\=&a.\lambda_1^{n-2}v_1+b.\lambda_2^{n-2}v_2+c.\lambda_3^{n-2}v_3\\=&a.\lambda_1^{n-2}\begin{bmatrix}\lambda_1^2\\\lambda_1\\1\end{bmatrix}+b.\lambda_2^{n-2}\begin{bmatrix}\lambda_2^2\\\lambda_2\\1\end{bmatrix}+c.\lambda_3^{n-2}\begin{bmatrix}\lambda_3^2\\\lambda_3\\1\end{bmatrix}\end{align}$

(since $M^k$ has same eigenvector $v_1$ and eigenvalue $\lambda_1^k$, for $k \in \mathcal{Z}^+$)

From the first equation, we get

$G_n=a.\lambda_1^n+b.\lambda_2^n+c.\lambda_3^n$

Now, $M$ has a real eigenvalue and two complex eigenvalues (conjugate to each other). Let $\lambda_1$ be the real one (W.L.O.G).

By evaluating the eigenvalues (we get $\lambda_1=1.839286755214161$), we observe that at $b.\lambda_2^n+c.\lambda_3^n \approx 0$, for large $n$.

Hence, we have $G_n \approx a.\lambda_1^n \implies ln G_n \approx ln a + n ln \lambda_1 \implies \frac{ln G_n}{n} \approx \frac{ln(a)}{n} + ln \lambda_1$

$\implies \lim\limits_{n\to\infty} \frac{ln G_n}{n} = 0 + ln(1.8392868) \approx 0.60938$