Given a positive number, how many times can this number be found in shifted fibonacci sequences? ...For example...Number 11, can be present seven times in total, in Fn+3, Fn+6, Fn+8, Fn+9, Fn+10, Fn+10, Fn+11. Can we generalise this? –
Asked
Active
Viewed 275 times
3
-
1$11$ is not found in $F_n$ – Asinomás Feb 14 '15 at 18:26
-
Sorry yes it slipped my fingers....;-) – Anthony Feb 14 '15 at 18:58
3 Answers
4
One can even give an explicit formula for the number of occurrences of $n$ in shifted Fibonacci sequences. Call this number $a_n$; then
$$a_n=1+\left\lfloor\log_\varphi\left(n\sqrt5+\frac12\right)\right\rfloor=1+\left\lfloor\frac{\ln\left(n\sqrt5+\frac12\right)}{\ln\varphi}\right\rfloor\;,$$
where $\varphi=\frac12(1+\sqrt5)$. For example,
$$a_{11}=1+\left\lfloor\log_\varphi\left(11\sqrt5+\frac12\right)\right\rfloor\approx 1+\left\lfloor\frac{3.222738266129}{0.4812118250596}\right\rfloor\approx 1+\lfloor 6.697130241406\rfloor=7\;,$$
and
$$a_{25}=1+\left\lfloor\log_\varphi\left(25\sqrt5+\frac12\right)\right\rfloor\approx 1+\left\lfloor\frac{4.032499289921}{0.4812118250596}\right\rfloor\approx 1+\lfloor8.379884\rfloor=9\;.$$
This follows from the last formula here.
Brian M. Scott
- 616,228
-
-
-
@BrianM.Scott can you please also answer, or improve / correct the one already given, to a question of mine at this link? http://math.stackexchange.com/questions/1140878/is-this-map-uniformly-continuous-continuous – Saaqib Mahmood Feb 15 '15 at 13:00
3
I'm assuming we can only add.The Fibonacci sequence $1,2,3,5,8,13\dots$ is a strictly increasing sequence. To find in how many fibonacci sequences $n$ appears just find the largest $k$ so $f_k\leq n$. Your number can be found in $k$ shifted sequences. (The one in which $f_1$ becomes $n$, the one in which $f_2$ becomes $n$ \dots the one in which $f_k$ becomes $n$).
Asinomás
- 105,651
-
Yes well done thank you I agree it is k times it agrees with my empirical way. Thank you modded Bear. – Anthony Feb 14 '15 at 18:43
-
-
The second sentence isn’t entirely correct: the Fibonacci sequence $\langle f_k:k\in\Bbb N\rangle$ is strictly increasing only for $k\ge 2$. – Brian M. Scott Feb 14 '15 at 19:49
-
I took the fibonaccis to be 12358... To avoid that. The argument needs slight adjustments if de take 0,1,1,2,3,5 – Asinomás Feb 14 '15 at 19:53
1
I am looking for more formal answers but here is my go at it. The shifted Fibonacci sequences are: Fn Fn+1, Fn+2, Fn+3,....I did some counting and Number 0 can be found once. 1 can be found 3 times number 2, 4 times, number 3, 5 times, number 4, 5 times, number 5, 6 times,number 6, 6 times, nuumber 7, 6 times, Numbers 8,9,10,11,12, 7 times, numbers 13,14,15,16,17,18,19,20, 8 times, Numbers 21,22,23,24,25,26,27,28,...33, can be found 9 times,....etc The general rule i find is The numbers incurred are increasing by ONE every time a fibnacci number is reached. 1 found 3 times, 2 found 4 times, 3,4 found 5 times, 5,6,7 found 6 times, 8,9,10,11,12 found 7 times, 13-20 found 8 times, etc. Any takers and any good theoretical foundation to my empirical proof? Thank you very much
Anthony
- 53
-
Yes, that is exactly right. If you want $n$ to appear in a shifted fibonacci sequence it can appear in position $k$ if and only if $f_k\leq n$. if $f_k+j=n$ the shifted fibonacci sequence in which $n$ appears at position $k$ is $f_n+j$. – Asinomás Feb 14 '15 at 18:45
-
-
no, it is ok. If $n=f_k+j$ the shifted fibonacci sequence in which $n$ appears at position $k$ is $f_n+j$. – Asinomás Feb 14 '15 at 18:51
-
Thank you very much for your help. Much appreciated. Happy V. Day too. – Anthony Feb 14 '15 at 18:52