A formal power series essentially is a sequence of numbers indexed by natural numbers written in series form \[ \sum_{n\in {\mathbb N}} a_n t^n \] What makes them interesting is the ring structure.
Scaling a power series with a number, or adding two series term by term is not that interesting. Multiplication is more interesting. One can multiply two such series as follows \[ \left(\sum_{n\in {\mathbb N}} a_n t^n\right) \left(\sum_{n\in {\mathbb N}} b_n t^n\right) = \left(\sum_{n\in {\mathbb N}}\sum_{m=0}^n a_{n-m}b_m t^n\right) \]
Formal power series appear in interesting places. One such place is
when one does counting depending on a single parameter \(n\). In such situations, one standard
method one can use is to write a generating function. Assume
count(n) is our function counting the number of certain
objects depending on a natural number parameter \(n\). The corresponding generating functions
is \[ \sum_{n=0}^\infty {\tt
count(n)} t^n \] In this note I will concentrate on formal power
series with integer coefficients, but most of what I will do below
applies to the case with real or imaginary coefficients.
Imagine we have an integer sequence \(a_n\) for \(n\in {\mathbb N}\) and I formed a generating function \(\sum_{n\in{\mathbb N}} a_n t^n\). What I want to do is to invert the series with respect to multiplication. That is, I want another formal power series \(\sum_{n\in{\mathbb N}} b_n t^n\) such that \[ 1 = \sum_{n=0}^\infty \delta^0_n t^n = \left(\sum_{n\in {\mathbb N}} a_n t^n\right) \left(\sum_{n\in {\mathbb N}} b_n t^n\right) \] where \(\delta^0_n\) is the Kronecker \(\delta\)-function at \(n=0\).
If we expand the multiplication on the right hand side for every \(n\>0\) we will see \[ 0 = \sum_{m=0}^n a_{n-m}b_m \] Note that we know the sequence \(a_n\) but we do not know the sequence \(b_n\). Re-writing the equation as \[ a_0 b_n = - \sum_{m=0}^{n-1} a_{n-m}b_m \quad\Rightarrow\quad b_n = - \frac{1}{a_0} \sum_{m=0}^{n-1} a_{n-m}b_m \] may not look like much, but if you look at carefully you see a recursive solution provided that \(a_0\) is non-zero. The value of \(b_n\) is calculated using previously calculated values \(b_0,\ldots,b_{n-1}\) and the values of \(a_0,\ldots,a_n\). The other thing we can notice is that if \(a_n\) is an integer sequence with \(a_0=1\) then the inverse sequence \(b_n\) is also an integer sequence.
Let us implement this in python
def inv(n,A):
if A[0]==1:
if n == 0:
res = 1
elif n == 1:
res = -A[1]
else:
m = min(len(A),n+1)
res = - sum ([ inv(n-i,A)*A[i] for i in range(1,m) ])
else:
res = 0
return(res)Let us check the algorithm on few known cases. Let us start with \(f(t) = 1 - t\) whose inverse is the geometric series \(\sum_{n=0}^\infty t^n\). I will print only the first 24 coefficients. Since this the recursion tree is complex, the computation time is abysmal.
print [inv(i,[1,-1]) for i in range(24)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]Modify this series a bit \(f(t) = 1 - t^3\)
print [inv(i,[1,0,0,-1]) for i in range(24)]
[1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]Consider \(f(t) = 1 + t + t^2\). When we invert we get \[ \frac{1}{1+t+t^2} = \frac{1-t}{1-t^3} = (1-t)\sum_{n=0}^\infty t^{3n} = \sum_{n=0}^\infty b_n t^n \] where \(b_n = 1\) when \(n\equiv 0\) modulo 3, \(b_n = -1\) when \(n\equiv 1\) modulo 3 and finally \(b_n = 0\) when \(n\equiv 2\) modulo 3
print [inv(i,[1,1,1]) for i in range(24)]
[1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1,
0, 1, -1, 0]Memoization would be a nice way to cut down the computation time.
invStack = {}
def inv(n,A):
try:
res = invStack[tuple([n]+A)]
except:
if A[0]==1:
if n == 0:
res = 1
elif n == 1:
res = -A[1]
else:
m = min(len(A),n+1)
res = - sum ([ inv(n-i,A)*A[i] for i in range(1,m) ])
else:
res = 0
invStack.update({tuple([n]+A):res})
return(res)Let us see a large number of coefficients:
A = [1,4,6,4,1]
print [ inv(i,A) for i in range(60) ]
[1, -4, 10, -20, 35, -56, 84, -120, 165, -220, 286, -364, 455, -560,
680, -816, 969, -1140, 1330, -1540, 1771, -2024, 2300, -2600, 2925,
-3276, 3654, -4060, 4495, -4960, 5456, -5984, 6545, -7140, 7770,
-8436, 9139, -9880, 10660, -11480, 12341, -13244, 14190, -15180,
16215, -17296, 18424, -19600, 20825, -22100, 23426, -24804, 26235,
-27720, 29260, -30856, 32509, -34220, 35990, -37820]Here is the same algorithm implemented in lisp:
(setq InvPow-stack (make-hash-table :test #'equal))
(defun InvPow-lookup (x) (gethash x InvPow-stack))
(defun InvPow-push (x y) (setf (gethash x InvPow-stack) y))
;;
;; A must be an array NOT a list
;;
(defun InvPow (n A)
(cond ((or (< n 0) (< (length A) 1) (not (= (aref A 0) 1))) nil)
((= n 0) 1)
((= n 1) (* -1 (aref A 1)))
(t (or (InvPow-lookup (list n A))
(InvPow-push (list n A)
(let ((m (min (length A) (1+ n))))
(* -1 (loop for i from 1 below m sum (* (InvPow (- n i) A) (aref A i))))))))))