8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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]$

$\endgroup$
  • $\begingroup$ +1 I like the matrix interpretation. I usually see it as $$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$$ but it makes me wonder. Doesn't your doubling method require saving 4 values (or 3 values I guess) on each step, whereas mine only requires 2 values? In general, all of my identities only require 2 values, $a_n$ and $b_n$, whereas going through yours uses 4 values, so are these really the same o.o $\endgroup$ – Simply Beautiful Art Jul 2 at 15:20
  • $\begingroup$ How does your matrices handle something like $$x^{mn}=(x^m)^n=(F_mx+F_{m-1})^n=\sum_{k=0}^n\binom nkF_m^kF_{m-1}^{n-k}x^k\Rightarrow F_{mn}=\sum_{k=0}^n\binom nkF_m^kF_{m-1}^{n-k}F_k$$? Seeing as matrix binomial expansion fails in general? $\endgroup$ – Simply Beautiful Art Jul 2 at 15:32
  • $\begingroup$ As for storage, you are right if you want to keep matrices as they are. But you can store just the first row (and calculate the second one), $\endgroup$ – Vasily Mitch Jul 2 at 15:40
  • $\begingroup$ The matrices are just a standard representation. They are absolutely equivalent to your polynomial field. In all your calculations you can replace $x$ with $F$ and everything will hold true. There is no problem because $F$ and $I$ commute, which is what the answer in your link is about. $\endgroup$ – Vasily Mitch Jul 2 at 15:44
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Vasily Mitch Jul 2 at 16:01
0
$\begingroup$

There is a beautiful general theory of linear difference equations, i.e. recursions of the form $x_n = M(x_{n-1},...,x_{n-k})$ where $M$ is a $k \times k$ matrix. For example, there is an explicit solution for $x_n$ expressed in terms of the characteristic roots of $M$.

$\endgroup$
  • $\begingroup$ I already know how to solve linear difference equations using the characteristic roots, but this doesn't provide any way to form identities like I was able to here. $\endgroup$ – Simply Beautiful Art Jul 2 at 15:09
-3
$\begingroup$

Good for you on discovering these.

As you suspected, these are already known as Fibonacci polynomials.

Here is a reasonable place to start:

https://en.wikipedia.org/wiki/Fibonacci_polynomials

$\endgroup$
  • $\begingroup$ Hm I honestly don't see the relevance. Could you elaborate? $\endgroup$ – Simply Beautiful Art Jul 2 at 15:07
  • $\begingroup$ Because there is none. What you found has nothing to do with Fibonacci polynomials $\endgroup$ – Vasily Mitch Jul 2 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.