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.
Best Answer
You have builŠµ a Fibonacci (?) field $Q[x]/(x^2-x-1)$. Every element of this field can be written as binomial, so it has representation in 2x2 matrices: $$ ax+b\qquad\Leftrightarrow\quad \begin{pmatrix}a+b & a\\ a & b\end{pmatrix} = aF+bI $$ You can check that $F^2=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^2=F+I $
You $O(\log n)$ algorithm is a well known the Doubling Method, which is essentially fast multiplication algorithm for matrix $F$.
To generalize, you should just select right first element. So in ordinary fibonacci, you start with (1,0), which is $X_1=1x+0$, next element is $X_2=x X_1$, then $X_3=x^2 X_1$ and so on. If you want to start with (-1, 2), then $Y_1=-1x+2$, $Y_2=x Y_1$, $y_3=x^2 Y_1$ and so on. You can use the same algorithm of fast multiplication to find $Y_n$.
Edit. As an example, I want to show how to build a tribonacci field $Q[x]/(x^3-x^2-x-1)$.
If we have $y=\alpha x^2+\beta x+\gamma$, then $$xy = \alpha x^3+\beta x^2+\gamma x = (\beta+\alpha)x^2 + (\gamma+\alpha)x+\alpha$$ So element $x$ is equivalent to matrix: $$ T = \begin{pmatrix}1 & 1& 1\\ 1 & 0&0\\0&1&0\end{pmatrix}. $$ So our field can be represented with $Q[I, T]$