Fibonacci Calculation using a larger matrix So the formula to generate the fibonacci sequence in matrix form is:
$$
   \begin{pmatrix}
   1 & 1 \\
   1 & 0 \\
\end{pmatrix}^n = 
   \begin{pmatrix}
   F_{n+1} & F_n \\
   F_n & F_{n-1} \\
\end{pmatrix}
$$
So, is there a way to generalize it to a larger matrix, a 4x4 for example?
 A: An attempt at a direct generalization gives the cubes of the Fibonacci numbers:
$\pmatrix{
3&6&-3&-1\\
1&0&0&0\\
0&1&0&0\\
0&0&1&0
}^n\pmatrix{
2197&512&125&27\\
512&125&27&8\\
125&27&8&1\\
27&8&1&1
}=\pmatrix{
F_{n+7}^3&F_{n+6}^3&F_{n+5}^3&F_{n+4}^3\\
F_{n+6}^3&F_{n+5}^3&F_{n+4}^3&F_{n+3}^3\\
F_{n+5}^3&F_{n+4}^3&F_{n+3}^3&F_{n+2}^3\\
F_{n+4}^3&F_{n+3}^3&F_{n+2}^3&F_{n+1}^3\\
}
$
It's not as clean as the original because there's an "accident" in the original where the coefficients of the recurrence relation are also the first two terms in the series. No such luck here.
A: Try looking at:
$$\begin{pmatrix}
   1 & 0 & 1 & 1 \\
   1 & 0 & 0 & 0 \\
   0 & 1 & 0 & 0 \\
   0 & 0 & 1 & 0 \\
\end{pmatrix}^n \begin{pmatrix}
   2 \\
   1 \\
   1\\
   0 \\
\end{pmatrix}
   $$
A: I suppose a natural generalization would be $$\begin{pmatrix} 1&1&0&0 \\ 1&0&1&0 \\ 0&0&0&1 \\ 0&0&0&0\end{pmatrix}^n$$ This adds the first two columns and then shifts everything over to the right, just as in the $2\times 2$ case. It is not hard to see how this would extend to a $k\times k$ matrix. 
On the other hand, this is a little "lame"; the bottom row is never even used.
A: $$
   \begin{pmatrix}
   1 & 1 & 0 & 0 \\
   1 & 0 & 0 & 0 \\
   0 & 0 & 2 & 1 \\
   0 & 0 & 1 & 1 \\
\end{pmatrix}^n = 
   \begin{pmatrix}
   F_{n+1} & F_n & 0 & 0 \\
   F_n & F_{n-1} & 0 & 0 \\
   0 & 0 & F_{2n+1} & F_{2n} \\
   0 & 0 & F_{2n} & F_{2n-1} \\
\end{pmatrix}
$$
The point is you're asking for something very arbitrary
