# Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive formula that we know from Fibonacci $a(n) = a(n-1) + a(n-2)$, where $n \ge 2$ and $a(0) \le a(1) \le \dots \le a(n)$. So let's say $a(n) = k$. Now I have to find $a(0)$, $a(1)$ that are initial number of this sequence, however the sequence should be longest possible and in case there are many of them which are of the same length $a(0)$ should be smallest possible. Some example:

$k = 10$

I can simply say $a(0) = 0$, $a(1) = 10$ so $a(n) = k$ is a part of this sequence since $a(0) + a(1) = a(2) = 10$. But it's not the longest possible. For instance choose $a(0) = 0$, $a(1) = 2$, now $a(2) = 2$, $a(3) = 4$, $a(4) = 6$, $a(5) = 10$, it's also valid sequence and length is $6$ and as far as I know it cannot be longer.

Any idea how to do so for any $k$? Might be math formula or some algorithm.

• Isn't it one longer if you start with $a_0=2$, $a_1=0$? – HSN Jul 1 '13 at 13:44
• It should be Fibonacci-like so a(0) <= a(1) <= a(2) <= ... <= a(n) – Kostek Jul 1 '13 at 13:45