[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)³ f² - (1 + x)² 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².

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)ⁿ + ((-3)ⁿ √π Hypergeometric2F1[3/2, -n, 3/2 - n, -(1/3)])/(4 n! Gamma[3/2 - n])