# Finding previous term in sequence

I'm afraid this problem fits more to stackoverflow, but maybe it fits also here.

For a given $F_n$ (but we don't know $n$) find $F_{n-1}$, knowing that $\forall_{n>1}F_n=F_{n-1}+F_{n-2}$. Also $\forall_{n\in\mathbb{N}}F_n\in\mathbb{N}, \ F_{n+1}\ge F_{n}\ge 0$. I know, it's not clear, but we are looking for such number $F_{n-1}$ that $n$ is the highest. For example:

for $F_n = 10$; $F_{n-1}=6$

for $F_n = 17$; $F_{n-1}=11$

for $F_n = 4181$; $F_{n-1}=2584$

because for these values, number $n$ is the highest. I think it is a mathematical problem, but the answer can also be in the form of algorithm. Anyone has an idea how to find $F_{n-1}$ for a given $F_n$?

[EDIT]: when we can find more than one value of $F_{n-1}$ we have to chose this for which the value of $F_0$ is the lowest. I add this just in case. But I think it's not necessary, because my friend claims that it is not very hard to find $F_{n-1}$ and quite intuitive.

-
Your recursion is missing its two (why?) initial conditions; what are they? –  Guess who it is. Apr 17 '12 at 12:21
That's the problem, we do not know $F_0$ and $F_1$. In other case it would be an easy problem. We are given one term $F_n$ and have to find the previous one. I was told that it can be done (quite easily). –  xan Apr 17 '12 at 12:23
What do you know about the growth rate of terms in this sequence? –  Mark Bennet Apr 17 '12 at 12:33
Okay, so we consider the sequences $a_k$ and $b_k$ satisfying that Fibonacci recursion you have, with $a_1=4,a_2=3$, and $b_1=1,b_2=5$. Both $a_5$ and $b_5$ are equal to $17$, but you want the answer to be $b_4$. Do I understand you correctly? –  Guess who it is. Apr 17 '12 at 12:36
@Mark, I know nothing. I know only $F_n$ and the information in my question. –  xan Apr 17 '12 at 12:41

You just have to divide $F_n$ by the golden ratio. To see why, look at http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
I suppose the complete prescription is $\left\lfloor\frac{F_n}{\phi}\right\rfloor$? –  Guess who it is. Apr 17 '12 at 12:38
yes, $\left[ \frac{F_n}{\phi} \right]$ was a solution, thanks a lot! :-) that is interesting, $\lim_{n \to +\infty}\frac{F_{n+1}}{F_n}=\phi$ for all sequences $F_n$ with 'Fibonacci rule'. I never thought about it this way, thanks again. –  xan Apr 17 '12 at 13:05