1
$\begingroup$

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.

  • 0
    Your recursion is missing its two (why?) initial conditions; what are they?2012-04-17
  • 0
    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).2012-04-17
  • 0
    What do you know about the growth rate of terms in this sequence?2012-04-17
  • 0
    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?2012-04-17
  • 0
    @Mark, I know nothing. I know only $F_n$ and the information in my question.2012-04-17
  • 0
    @J.M. look at my question. There is a condition that this sequence have to be non decreasing. But without it - exactly that's the point :-)2012-04-17

1 Answers 1

1

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

  • 0
    I suppose the complete prescription is $\left\lfloor\frac{F_n}{\phi}\right\rfloor$?2012-04-17
  • 0
    Choose the integer for which we can best approach the ratio.2012-04-17
  • 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.2012-04-17