You have already answered your own question, essentially. The space $E$ of sequences $\{a_n\}_{n\geq 0}$ fulfilling $a_{n+2}=a_{n+1}+a_n$ is a vector space with dimension $2$; any sequence belonging to $E$ is fixed by its initial values $a_0$ and $a_1$. The initial values of the Fibonacci sequence are $0,1$; the initial values of the Lucas sequence are $2,1$; since $(0,1)$ and $(2,1)$ are linearly independent each sequence in $E$ can be represented through $a_n = f\cdot F_n + l\cdot L_n$ for some constants $f,l$. For instance, this applies to the shifted Fibonacci and Lucas sequences: $$ L_{n+1} = \frac{5}{2}F_n+\frac{1}{2}L_n,\qquad F_{n+1}=\frac{1}{2}F_n+\frac{1}{2}L_n $$ and you may also take $\{F_n\}_{n\geq 0},\{F_{n+1}\}_{n\geq 0}$ or $\{L_n\}_{n\geq 0},\{L_{n+1}\}_{n\geq 0}$ as a base for $E$.
A sequence with a moderate growth can be associated to an analytic function via $$ \{a_n\}_{n\geq 0}\quad \mapsto\quad g(x)=\sum_{n\geq 0}a_n x^n $$ (the RHS is known as the ordinary generating function (OGF) of the sequence) and this gives a tight relation between linear recurrent sequences, linear differential equations and the elements of $M^n$ with $M$ being a fixed matrix. You guessed it correctly: they all appear to be the same problem because they actually are the same problem.