0

Determining nth value of the Fibonacci series or Fibonacci like series is well known and easy to calculate. Can that be reversed?

Can we calculate 1st and 2nd element of the series by giving the value of nth element?

for example, for non Fibonacci series number: 1398 the first and second element of that series is 6: 6 6 12 18 30 48 78 126 204 330 534 864 1398

by knowing only 1398, are we able to compute that it is 13th element in the series where first two elements are 6 an 6?

  • 2
    Welcome to Math.SE! ... Since the terms of ${m,m,2m,3m,\ldots}$ are simply multiples of the Fibonacci numbers, you're effectively asking: Given $M$ and divisor $m$, is $M/m$ a Fibonacci number (and, if so, what is its index)? It is known (see Wikipedia) that $x$ is Fibonacci if and only if at least one of $5x^2+4$ or $5x^2-4$ is a perfect square; if it is, then the index can be computed as $[\log_\phi (x\sqrt{5})]$, where $\phi=1.618\ldots$ is the Golden Ratio, and $[\cdot]$ represents rounding. (continued) – Blue Oct 13 '23 at 13:41
  • 1
    (continuing) Of course, there's some ambiguity in the question. Not only is $1398$ the $13$th term of ${6,6,\ldots}$, it's the $4$th term of ${466,466,\ldots}$, the $3$rd term of ${699,699,\ldots}$, and the $1$st and $2$nd terms of ${1398,1398,\ldots}$. – Blue Oct 13 '23 at 13:45
  • yes, that is correct, this term could have different position in different series, but still, is there a way, an algorithm to calculate it? the 1.618 is not the way as it does not work all the time (it does not work for first couple of terms in the series, for ex. 18/12 is 1.5) – Jacek R. Oct 13 '23 at 14:20
  • The algorithm is called subtraction. It is like addition, only the other way around. Now we may consider some meaningful questions to ask. Is 1398 the 13th term of any Fibonacci-like sequence with positive terms? (You know the answer, since this is your example question.) Is it the only such sequence? (Yes.) What is the smallest number that is the 13th term of two different such sequences? That would be 13049. – Ivan Neretin Oct 14 '23 at 02:12
  • @Blue You should write your comments as an answer. – jjagmath Oct 15 '23 at 02:03
  • @JacekR. What do you mean when you say Blue method doesn't work? You gave the example $18/12$ but Blue method talks about taking $m$ a divisor of M. – jjagmath Oct 15 '23 at 02:10

2 Answers2

0

First, let's clarify that the thirteenth element in the recurrence is really $f_{12}$ since the first element is $f_0$. Now that said, I am assuming that by Fibonacci-like you mean that $f_n=f_{n-1}+f_{n-2}$, as opposed to the more general $f_n=af_{n-1}+bf_{n-2}$. The general solution to your Fibonacci-like equation is given by

$$ f_n=\bigg(f_1-\frac{f_0}{2}\bigg)F_n+\frac{f_0}{2}L_n $$

where

$$ F_n=\frac{\varphi^n-\psi^n}{\varphi-\psi}\\ L_n=\frac{\varphi^n+\psi^n}{\varphi+\psi} $$

where, of course, $\varphi,\psi=(1\pm\sqrt{5})/2$.

For your particular case, given $f_{12}=1398$, we seek to find $f_{0,1}$ from

$$ f_{12}=\bigg(f_1-\frac{f_0}{2}\bigg)F_{12}+\frac{f_0}{2}L_{12} $$

Alas, we have one equation in two unknowns, so we cannot find a solution unless $f_0=f_1$. I believe this will always give a solution, although it may turn out to be a non-integer.

Cye Waldman
  • 7,524
0

The first two terms of the regular Fibonacci series (RFS) are $1$. A more general case is that the first two terms are positive integers $a$ and $b$ respectively. For convenience, we may call it "generalized Fibonacci series" (GFS), and denote its $n$-th term by $g_n$.

It is possible to find the first two term $a$ and $b$ of the GFS with the known $n$-th term as follows. When $n$ is sufficiently large, the ratio of two adjacent terms is well approximate to $c=\frac{1+\sqrt5}{2}\approx1.618034...$. Thus, for example, with given $g_{13}=1398$, we can get $g_{12}=round(1398/1.618034)=864$. Then by iterative subtractions, $g_{k}=g_{k+2}-g_{k+1}$, for $k=n-2, n-3, ..., 2,1$, we can finally get $(a,b)=(6,6)$ .

This method has a limitation that the value of $n$ for the known $g_n$ should be sufficiently large with respect to the initial values $(a,b)$. That means, if $a$ and $b$ are quite large, $n$ also needs to be quite large.

Below is another possible method to avoid this problem. While the $n$-th term of the regular Fibonacci series can be expressed as

$f_n=\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n]$,

the $n$-th term of the generalized Fibonacci series can be expressed as

$g_n=af_{n-2}+bf_{n-1}$.

This is a linear Diophantine equation (DEQ) with known $g_n$, $f_{n-2}$ and $f_{n-1}$. For example, with $g_{13}=1398$, $f_{12}=144$, $f_{11}=89$, we have the DEQ

$89a+144b=1398$.

This DEQ has a unique positive integer solution for both $a$ and $b$, i.e., $(a,b)=(6, 6)$.

  • that one looks fine, however for some integers it sort of "breaks": like for 1748101075, where the n-1 element is 1080385872 or 1080385873 (depends how we round it), we will get to smth like this: 1748101075 1080385873 667715202 412670671 255044531 157626140 97418391 60207749 37210642 22997107 14213535 8783572 5429963 3353609 2076354 1277255 799099 478156 320943 157213 163730 -6517 – Jacek R. Oct 16 '23 at 14:24
  • @Jacek R The problem is that the value of $n$ is not sufficiently large, with respect to the initial values of $a$ and $b$. That means if the initial values are large, then the $n$ value needs to be more large to make this method work. See another method just added in my above answer.. – user295357 Oct 16 '23 at 14:40
  • @Jack R Another issue is about the accuracy. More accurately, 1.618034... should be $c=\frac{1+\sqrt5}{2}$. Your number of $g_n=1748101075$ is quite large. In this case, try to use the accurate value of $c$, not the approximate value of $1.618034$. – user295357 Oct 16 '23 at 16:23
  • the size of c does not change much, for c=1.618033988749894 we got: 1748101075 1080385880 667715195 412670685 255044510 157626175 97418335 60207840 37210495 22997345 14213150 8784195 5428955 3355240 2073715 1281525 792190 489335 302855 186480 116375 70105 46270 23835 22435 1400 21035 -19635 – Jacek R. Oct 16 '23 at 23:16
  • @Jack When you used $c=1.618034$, you got the $n-1$ term $1080385872$ (or $1080385873$), while now you got $1080385880$. So it already changed a lot. Could you please tell the value of $n$ associated with $g_n=1748101075$ ? We need to know $n$ to decide when to stop the iterative subtraction. – user295357 Oct 16 '23 at 23:51
  • the n associated with gn=1748101075 is just 1.618, I know it was too short, and the one above is more accurate but still the result is 1400 and 22435, which could be the real f0 and f1 actually, just looks ugly :) – Jacek R. Oct 17 '23 at 07:23
  • @Jack $n$ must be a positive integer. When you said "the n associated with gn=1748101075 is just 1.618", is it a typo ? – user295357 Oct 17 '23 at 12:49
  • sorry, I meant that c was 1.618, n isn't known – Jacek R. Oct 17 '23 at 13:18