# Recovering two first terms from sequence $f(n)=f(n-1)+f(n-2)$

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

-
You only have one term? Then your problem's underdetermined. – J. M. Dec 17 '11 at 9:15
Sorry, i have n-th term and it's value. – Spinach Dec 17 '11 at 10:08
Yes, but you need two terms to completely determine a Fibonacci-like sequence. – J. M. Dec 17 '11 at 10:11
But i can brute-force for possible first and second term. Why there doesn't exist solution? – Spinach Dec 17 '11 at 10:18
Alright. Try the initial conditions $f(0)=11,f(1)=8$ and $f(0)=21,f(1)=2$. Check $f(5)$ for both sequences. – J. M. Dec 17 '11 at 11:19

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.