[seqfan] Re: SIAM Rev problem 89-19
David Wilson
davidwwilson at comcast.net
Tue Oct 18 02:39:55 CEST 2011
That was back when the SIAM review was hardcopy and ran a problem section.
I originally posted the problem in sci.math. A SIAM editor got it from
there and
played around with it, getting the strange non-repeating Maclaurin
series that you
got.
You omitted the constant term in your Maclaurin series, which is 0. Had
you included
it, you would have gotten
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,..
which is A010060, the Thue-Morse sequence. If you let F(0) = a, F'(0) =
b as in
the problem statement, you get the Maclaurin series by replacing each 0
with a
and each 1 with b.
One solver gave a formula:
F(x) = ((a+b)/2) (1/(1-x)) + ((a-b)/2) PROD(k = 0..inf) (1-x^(2^k)).
Let S be a b-automatic set (subset of Z+ whose base-b representations
form a regular language).
Let f_S be the indicator function for S on Z+, that is
For n in Z+, f_S(n) = 1 if n in S, 0 otherwise
Then the series
F_S(x) = SUM(k = 0..inf, f_S(k) x^k)
satisfies an equation of the form
SUM(k = 0..m, p_k(x) F(x^(b^k))
with finite m, where p_k is a polynomial.
So let S = A000069, the odious numbers. The indicator function of S is
f_A000069 = A000060,
the Thue-Morse sequence. S happens to be a 2-automatic set, whose base-2
representations
form the regular language 1(0*10*1)0*. Thus the series
F(x) = F_A000069(x) = SUM(k = 0..inf, f_A000069(k) x^k) = SUM(k =
0..inf, A000060(k) x^k)
satisfies the equation
[1] x*F(x) + (x+1) F(x^2) + (x^4-1) F(x^4) = 0
given in the problem.
A000069 is about the simplest example of a 2-automatic sequence S that
is not periodic
(a periodic S would lead to an uninteresting rational function F_S). But
there are many
other examples of b-automatic sets, such as A004215 (2-automatic with
base-2 regular set
1(0+1)*111(00)*, or A051003 (10-automatic with base-10 regular set
[0-9]*666[0-9]*).
Any such set S would have an F_S satisfying an equation similar to [1]
(but in general much
bigger).
On 10/17/2011 6:15 PM, Richard Mathar wrote:
> In problem 89-19 of SIAM Review vol 31 no 4 (1989) on page 676
> a certain David W. Wilson orders: "Find the MacLaurin series
> expansion of F(x) that satisfies the funcional equation
> (x^4-1)*F(x^4)+(x+1)*F(x^2)-x*F(x)=0, F(0)=a, F'(0)=b
> This problem arose in a study of the acceptance of binary numerical
> strings by finite automata."
> I did not find any "solution" page on this question in the journal.
> Are any of these series coefficients in the OEIS? Are they "interesting"?
> The one that starts linearly, F(0)=0, F'(0)=1 seems to
> have the Taylor coefficients 1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,...
> (leading 0 from the absolute term omitted).
>
> http://www.jstor.org/stable/2031547
> http://dx.doi.org/10.1137/1031135
>
> RJM
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list