1
$\begingroup$

Having very simple sequence $f(n)=f(n-1)+f(n-2)$ and having $n-th$ term given how can we calculate from which first two terms this $n-th$ term came?

I know the answer can be not unique so highest possible terms are OK.

My only idea was to write recursive brute-force which worked like that : Having some sum S make every possible pair and assume they are $f(n-1)$ and $f(n-2)$ and do it for every number.

Thanks for any better ideas or hints.

Chris

  • 0
    Alright. Try the initial conditions $f(0)=11,f(1)=8$ and $f(0)=21,f(1)=2$. Check $f(5)$ for both sequences.2011-12-17

1 Answers 1

4

The pair $(f(n),f(n+1))$ satisfies $ \begin{pmatrix}f(n)\\ f(n+1)\end{pmatrix}= A^n\cdot\begin{pmatrix}f(0)\\ f(1)\end{pmatrix} \qquad\text{where $A=\begin{pmatrix}0&1\\\ 1&1\end{pmatrix}$ so that $A^n=\begin{pmatrix}F_{n-1}&F_n \\ F_n& F_{n+1}\end{pmatrix}$} $ with $F_i$ denoting Fibonacci number $i$, and inverting $ \begin{pmatrix}f(0)\\ f(1)\end{pmatrix}= A^{-n}\cdot\begin{pmatrix}f(n)\\ f(n+1)\end{pmatrix} \qquad\text{where $A^{-n}=(-1)^n\begin{pmatrix}F_{n+1}&-F_n \\\ -F_n& F_{n-1}\end{pmatrix}$.} $ This shows that if you don't know anything else than $f(n)$, you can arrange $f(0)$ to be anything you like.

However, should you know that $f(0),f(1)$ are integers and not too large, than you will have for sufficiently large $n$ that $f(n+1)$ is the nearest integer to $\phi f(n)$ where $\phi=\frac{1+\sqrt5}2$, and you can then solve $f(0),f(1)$. Just what is large enough depends on how small your initial numbers are known to be (and is an instructive exercise); for instance if they are between $0$ and $50$ then I believe $n\geq10$ should be OK. But you cannot expect us to solve your enigma if you don't give all the clues.

  • 0
    Thanks you, that cleared it for me :)2011-12-17