Tower of Hanoi sequence via eigendecomposition

The following sequence comes from the Tower of Hanoi. $$ 1, 3, 7, 15, \dots $$ Find the $64$-th term using eigendecomposition.

By general pattern, I know that the answer is obviously $2^{64} -1$. However, I am asked to solve using eigendecomposition.

$$ T(n) = 2^n - 1 $$

Let $F_k$ be the terms of the sequence.

$$F_{k+1} = 2 F_k+1$$

In matrix form..

$$\begin{bmatrix} F_{k+1} \\F_k\end{bmatrix} = \begin{bmatrix} 2&1 \\1&0\end{bmatrix}\begin{bmatrix} F_{k} \\1\end{bmatrix}$$

Please help me continue.

Solution 1:

From \begin{align}\tag{1} F_{k+1} &= 2F_k-1\\\tag{2} F_k &= 2F_{k-1}-1 \end{align} follows by substracting equation (2) from (1) \begin{align} F_{k+1}-F_k &= 2F_k-2F_{k-1}. \end{align} This leads to \begin{align} F_{k+1}&= 3F_k-2F_{k-1}. \end{align} We get \begin{align} \begin{bmatrix}F_{k+1}\\F_{k}\end{bmatrix}=\begin{bmatrix}3& -2\\ 1 &0\end{bmatrix}\begin{bmatrix}F_{k}\\F_{k-1}\end{bmatrix}. \end{align} You have to decompose $\begin{bmatrix}3& -2\\ 1 &0\end{bmatrix}$.