Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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. –  Chris 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? –  Chris 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
add comment

1 Answer

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|improve this answer
    
Thanks you, that cleared it for me :) –  Chris Dec 17 '11 at 14:09
add comment

Your Answer

 
discard

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.