[seqfan] Re: "near-Fibonacci sequences" and interval [0,1]

Marc LeBrun mlb at well.com
Wed Jul 7 02:24:46 CEST 2010

>="Vladimir Shevelev" <shevelev at bgu.ac.il>
> Dear Seq Fans,
I would like to discuss the following construction.
It is
> easy to prove that, for n>=1, the Fibonacci sequence {F(n)}={1,1,2,3,5,8,...}
> (A000045) one can reproduce by the recursion: F(n)=1 and, for n>=2,
> F(n)=floor(\phi*F(n-1)), if n is even, and F(n)=ceil(\phi*F(n-1)), if n is
> odd, where \phi=Golden ratio.
  Let x belong to [0,1] with the binary
> expansion x=0.x_1x_2...x_n..., where x_k, k=0,1,..., is in {0,1}.  Define
> sequence {F_x(n)} by the recursion F_x(0)=1 and, for n>=2,
> F_x(n)=foor((\phi*F_x(n-1)), if x_(n-1)=0, and  F_x(n)=ceil((\phi*F_x(n-1)),
> if x_(n-1)=1.
Then sequence {F_(n)} of Fobonacci numbers corresponds to
> x=0.010101...=1/3.
In case of x=2/3=0.10101...we obtain sequence
> {1,2,3,5,8,...}, i.e. a shift of {F(n)}, while in case of x=1=0.111111...we
> obtain sequence {1,2,4,7,12,20,...}, i.e. {F(n+2)-1}_(n>=1)-cf. A000071. Thus
> sequences {F_x(n)}, when 1/3<=x<=1, it is natural to call "near-Fibonacci
> sequences". The growth of every near-Fibonacci sequence is O(\phi^n) with the
> constant C in O(...) in interval [1/sqrt(5), \phi^2/sqrt(5)].
On the other
> hand, for x decreases from 1/3 to 0, we have a more complicated law with
> essentially decreasing growth.  What is this?
 In case of the ternary
> expansion y=0.y_1y_2,,,y_n..., where y belongs to the Cantor's set, i.e. y_k
> is in {0,2}, we obtain "near-Fibonacci sequences" for the part of  Cantor's
> set in [1/4,1].
Vladimir Shevelev

[Terminology note: in the OEIS (and elsewhere) these "control programs" of
0s and 1s are often referred to as "characteristic" sequences or functions.]

Agreed: characteristic sequences can nicely encode the "choices" for a 2-way
branching process, such as the rounding direction here.

But characteristic sequences and binary expansions aren't naturally quite
1-to-1.  A program with an infinite tail of 0s maps to the same value as
another program with an infinite tails of 1s.

So--unless the process always computes equal outputs when fed "numerically
equivalent" programs--beware that x is just an informal shorthand for a
certain characteristic sequence X, rather than a real magnitude, lest
glitchy technicalities intrude.


Anyway, all that aside, F(n+1)/F(n) being the continued fraction convergents
to phi, I'm guessing that CFs might shed some light here?

Recall the process for extracting the CF terms for ANY real number p is to
emit floor(p), then subtract and reciprocate.

The reciprocation reflects the direction of the real p-line and thus swaps
the effects of floor and ceiling.  This induces the observed alternation and
relates to how the convergents of p's CF are alternately above and below p.

Hence: each characteristic sequence X defines a "variant CF expansion
process".  Where the Xn deviates from the "classic" alternation, then the
extraction process uses ceiling instead of floor.


BTW instead of mapping 0 to floor and 1 to ceiling we could have built the
alternation into the process itself, implementing a new interpretation of
characteristic sequences wherein 0 means "do the vanilla CF thing" for this
step, while 1 means "do the opposite".

To switch processors we simply convert between these programming languages
by "XORing with 1/3".

Similarly, consider another kind of expansion where instead we try to
preserve direction by reflecting in TWO different ways, taking 1/(1-p)
versus 1/p.  Is there a characteristic sequence for a CF variant that will
produce the same expansions as this process?


Lastly, recall that the vanilla CF expansion of a quadratic root is
periodic, and vice versa.  Is this equally true for all variant expansions
based on periodic programs?

More information about the SeqFan mailing list