Generating functions [for nested patterns]

A convenient algebraic way to describe a sequence of numbers a[n]

a[n] is to give a generating function Sum[a[n] xⁿ, {n, 0, ∞}]

✖

Sum[a[n]\!\(\*SuperscriptBox[\(x\),\(n\)]\),{n,0,\[Infinity]}]. 1/(1 - x)

✖

1/(1 - x) thus corresponds to the constant sequence and 1/(1 - x - x²)

✖

1/(1-x-\!\(\*SuperscriptBox[\(x\),\(2\)]\)) to the Fibonacci sequence (see page 890). A 2D array can be described by Sum[a[t, n] xⁿ y^t, {n, -∞, ∞}, {t, -∞, ∞}]

✖

Sum[a[t, n]\!\(\*SuperscriptBox[\(x\),\(n\)]\)\!\(\*SuperscriptBox[\(y\),\(t\)]\),{n,-∞,∞},{t,-∞,∞}]. The array for rule 60 is then 1/(1- (1 + x) y)

✖

1/(1- (1 + x) y), for rule 90 1/(1 - (1/x + x) y)

✖

1/(1 - (1/x + x) y), for rule 150 1/(1 - (1/x + 1 + x) y)

✖

1/(1 - (1/x + 1 + x) y) and for second-order reversible rule 150 (see page 439) 1/(1 - (1/x + 1 + x) y - y²)

✖

1/(1-(1/x+1+x)y-\!\(\*SuperscriptBox[\(y\),\(2\)]\)). Any rational function is the generating function for some additive cellular automaton.