So I recently thought of a cool way to represent the Fibonacci sequence, which provides many identities really interestingly. The key is to define
$$x^2=x+1$$
And consider the integer sequences given by
$$x^n=a_nx+b_n$$
These sequences satisfy $F_{n+2}=F_{n+1}+F_n$ and $a_1=a_2=b_2=b_3=1$, thus producing the Fibonacci sequence. This is easily verifiable:
\begin{align}\color{blue}{a_{n+2}}x+\color{green}{b_{n+2}}&=x^{n+2}\\&=x^nx^2\\&=x^n(x+1)\\&=x^{n+1}+x^n\\&=a_{n+1}x+b_{n+1}+a_nx+b_n\\&=(\color{blue}{a_{n+1}+a_n})x+(\color{green}{b_{n+1}+b_n})\end{align}
One can also come up with a simple $\mathcal O(\log(n))$ algorithm to compute $F_n$ using exponentiation by squaring:
\begin{align}\color{blue}{a_{2n}}x+\color{green}{b_{2n}}&=x^{2n}\\&=(x^n)^2\\&=(a_nx+b_n)^2\\&=a_n^2x^2+2a_nb_nx+b_n^2\\&=a_n^2(x+1)+2a_nb_nx+b_n^2\\&=\color{blue}{a_n(a_n+2b_n)}x+\color{green}{a_n^2+b_n^2}\end{align}
And similarly for $x^{2n+1}$. This also quickly gives some other cool identities using the fact that $x^{n+k}=x^nx^k$, for example.
I was thinking, however, that this is just way too convenient. I'm unsure how to generalize this. For example, what if I wanted to start at different integers?
I'm also curious to know if there's something more to this. Some deeper math behind the scenes that can explain why I'm able to write the Fibonacci sequence like this aside from just brute force showing it satisfies the definition.
As far as starting at different integers goes, we can consider the sequences given by
$$x^n(a_0x+a_1-a_0)=a_nx+b_n$$
which preserves the recurrence relation and lets us choose what we want $a_0$ and $a_1$ to be.
As far as I can tell, it is possible to do this to any recurrence relation of the form
$$x_{n+k}=y_1x_{n+k-1}+\dots+y_kx_n$$
by considering the corresponding
$$x^k=y_1x^{k-1}+\dots+y_k$$
and considering the sequences given by
$$x^nP(x)=a_nx+b_n$$
for some polynomial $P$ which corresponds to the initial conditions, provided $x$ is irrational to ensure uniqueness.
So this leaves me the question of whether or not there's more math relevant here aside from my just stumbling upon this. I ask this because I think this kind of identity is just "too good to be true", especially for me to not have noticed this kind of thing despite having seen plenty of recurrence relations before.