[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 positions2^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 page84.(1 + Sqrt[(1 - 3 x)/(1 + x)])/(2(1 + x)) (see page890) 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 page83.EllipticTheta[3,π, x]/2 gives a sequence with 1's at positionsm².

For any sequence with an algebraic generating function and thus for any nested sequence then^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])