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.

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.

share|improve this question
    
Your recursion is missing its two (why?) initial conditions; what are they? –  J. M. 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? –  J. M. 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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
I suppose the complete prescription is $\left\lfloor\frac{F_n}{\phi}\right\rfloor$? –  J. M. Apr 17 '12 at 12:38
    
Choose the integer for which we can best approach the ratio. –  Wonder Apr 17 '12 at 12:45
1  
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

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.