[Generating functions for] 1D sequences

Generating functions that are rational always lead to sequences which after reduction modulo 2 are purely repetitive. Algebraic generating functions can also lead to nested sequences. (Note that to get only integer sequences such generating functions have to be specially chosen.) Sqrt[1 - 4 x]/2 yields a sequence with 1's at positions 2^{m}, as essentially obtained from the substitution system {2 {2, 1}, 1 {1, 0}, 0 {0, 0}}. Sqrt[(1 - 3 x)/(1 + x)]/2 yields sequence (a) on page 84. (1 + Sqrt[(1 - 3 x)/(1 + x)])/(2(1 + x)) (see page 890) yields the Thue–Morse sequence. (This particular generating function satisfies the equation (1 + x)^{3} f^{2} - (1 + x)^{2} f + x 0.) (1 - 9 x)^{1/3} yields almost the Cantor set sequence from page 83. EllipticTheta[3, π, x]/2 gives a sequence with 1's at positions m^{2}.

For any sequence with an algebraic generating function and thus for any nested sequence the n^{th} element can always be expressed in terms of hypergeometric functions. For the Thue–Morse sequence the result is

1/2 (-1)^{n} + ((-3)^{n} Sqrt[π] Hypergeometric2F1[3/2, -n, 3/2 - n, -(1/3)])/(4 n! Gamma[3/2 - n])