Whats the intuitive explanation that matrix multiplication of first 4 recurrence value solves linear recurrence relationship?

Question

For example in this pdf https://bpb-ca-c1.wpmucdn.com/sites.uoguelph.ca/dist/8/175/files/2021/04/Fib_lin_alg.pdf

The author created a matrix from the output of Fibonacci sequence in group of $2$, and take $2$ of the group

Fibonacci sequence 0 1 1 2 3 5 8 13 21 34
Group of 2 

fi     0 1 1 2 3
fi+1   1 1 2 3 5

Take first $2$ group, make it into matrix

0 1
1 1

And you can just multiply the matrix $n$ times to get $F(n)$.

Whats the intuitive explanation or proof of that?

Does that work with any recurrence sequence?

What topic or textbook should I read to learn more about this?

Answer 1

Suppose you were generating the Fibonnaci sequence term-by-term. Consider the ordered pair $(x,y)$ where $x$ is the "current" Fibonacci number and $y$ is the "previous" Fibonacci number. Then the task of generating the next Fibonnaci number amounts to the transformation $$ x\mapsto x+y,\quad y\mapsto x$$ That is, we update the "current" Fibonnaci number and reassign $x$ as the previous one. But this is a linear transformation on $(x,y)$, which the matrix given in the problem implements.

This works more generally for an $n$th-order linear recurrence: If you start with one term in the sequence along with the previous $n-1$ terms, then the transformation which "updates" this set of $n$ values is a linear transformation and hence can be implemented using a matrix.