0
$\begingroup$

I'm stuck on a question that was given to me on a list of problems. It's to do with the fibonacci sequence such that if I have the $a=f(n)$ and $b=f(n+1)$ of a sequence that is a fibonacci sequence, find the 1st and 2nd term of that sequence. I'm not given the value of $n$.

Initially I thought that perhaps using a generalisation formula could be used to find n, and then extrapolation the answer from there but honestly I'm stuck where to even begin. I'm using python to program the solution

$\endgroup$
0
$\begingroup$

If you're not given any information on the starting values or $n$, it's impossible to extrapolate what term of the sequence you're in.

For example, suppose you're given $(50, 85)$. Who's to say that these aren't the starting terms? The starting terms could have also been $(35, 50)$, or $(15, 35)$, or whatever else. All of these answers are equally valid without further exposition.

$\endgroup$
0
$\begingroup$

As Michael Tong indicates, the question as stated has no unique solution. There is no way to tell that the given pair of numbers aren't themselves the seed.

However, one might resolve that by asking instead for the smallest seed terms that are positive. Then, one can answer that by working backwards. For instance, starting from Michael's example of $(50, 85)$, we get $(35, 50)$, then $(15, 35)$, then $(20, 15)$. Working further back would yield $(-5, 20)$, which contains a non-positive number, so we can stop with $(20, 15)$.

It is not difficult to show that if one starts with $(a, b)$ with integers $b > a > 0$, this process must terminate.

$\endgroup$
  • $\begingroup$ I knew a there'd be a glaringly obvious solution thank you $\endgroup$ – nash Jul 26 '16 at 18:17
0
$\begingroup$

Since you are trying to program a solution into Python, I assume you're looking for an algorithm to find the successive possible elements backwards from $a$ and $b$. Using the Fibonacci sequence definition: $$f(n+1)=f(n)+f(n-1)$$ $$f(n-1)=f(n+1)-f(n)$$ $$c=b-a$$ Having found $c$ you set $b\leftarrow a$ and then $a\leftarrow c$ and repeat the process until the stopping criterion is met. This criterion might be reaching a negative number for example.

$\endgroup$
0
$\begingroup$

If you knew $n,$ this would be solvable as follows. Let $F_k$ denote the $k^\text{th}$ Fibonacci number. Then

$$f(1) = (-1)^{n+1} (a F_n - b F_{n-1})$$ and $$f(2) = (-1)^n (a F_{n-1} - b F_{n-2}).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.