Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
Thanks you, that cleared it for me :) – Spinach Dec 17 '11 at 14:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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