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

  • 2
    You only have one term? Then your problem's underdetermined.2011-12-17
  • 0
    Sorry, i have n-th term and it's value.2011-12-17
  • 0
    Yes, but you need two terms to completely determine a Fibonacci-like sequence.2011-12-17
  • 0
    But i can brute-force for possible first and second term. Why there doesn't exist solution?2011-12-17
  • 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