Some divide-and-conquer sequences with (relatively) simple ordinary generating functions
Some divide-and-conquer sequences with (relatively) simple ordinary generating functions
Version 2004-01-1
Ralf Stephan <ralf(at)ark.in-berlin.de>
Introduction
In the following, about 100 sequences are collected that are
generated by ordinary generating functions
of form 1/(1-x)^m * sum(k=0, inf, C^k*R(x^2^k)), where m=0,1,2, C is
integer, and R is
a rational function. That the given recurrences are indeed
generated by the mentioned functions (and that most of the sequences
are fractal) is clarified in the
section below.
For all recurrences, a link into their
OEIS
entry, as well as, where possible, a mnemonic and a 'closed form' is
given. Parentheses around a link means the entry can be derived from
the recurrence by an elementary operation like shift. Used abbreviations are
[log2(n)] for A000523(n),
v2(n) for A007814(n),
e1(n) for A000120(n),
and e0(n) for A023416(n). Where the parameter is left out, it is
understood to be n. Recurrence start value a(0) is always 0.
Of form a(2n) = C*a(n) + P(n), a(2n+1) = Q(n) (1)
Here and thereafter, P and Q are functions of n expressible by
a rational generating function, C integer.
Recurrences of form a(2n) = C*a(n) + P(n), a(2n+1) = Q(n)
Of form a(2n) = C*(a(n)+a(n-1)) + P(n), a(2n+1) = 2C*a(n) + Q(n) (3)
P and Q are functions of n expressible by a rational generating
function, C integer. The sequences are all partial sums of sequences of
the previous form (2), a(0)=0.
Recurrences of form a(2n) = C(a(n)+a(n-1)) + P(n), a(2n+1) = 2Ca(n) + Q(n)
Lemma. Let A(z) an infinite sum of rational functions of form
A(z) = sum (k=0, inf, C^k * B(z^(2^k))),
B rational, C integer. Then A(z) generates an integer sequence of
divide-and-conquer type satisfying
a(0)=0, a(2n) = Ca(n)+b(2n), a(2n+1) = b(2n+1),
where b(n) is the sequence generated by B(z).
The summation term with k=0 fills both bisections of a(n)
since C^k and 2^k reduce to 1. Any other term contributes
only to a(2n) as all exponents to z are even. Moreover, other subsequences from
single terms of the sum
are increasingly sparse (spread out by a factor of 2), and have values
multiplied with C, with respect
to each other. This is essentially the reason for the fractality of a(n).
Note the proof of the lemma is easy because having no reference to a(n) in the
odd bisection of the recurrence amounts to a cutoff of the recursion,
leaving computation
of v2(n) steps in the even bisection.
Additional insight might be gained from the
collection of generating functions in
this Postscript file (6 pages).
An open question would be whether all sequences here discussed are 2-regular.
