[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-4x]/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 - 3x)/(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 - 9x)^{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])