Power Series and Generating Functions (II): Formal Power Series

For today’s post, we shall first talk about the Catalan numbers. The question we seek to answer is the following.

Let n be a positive integer. Given a non-associative operation *, find the number of ways to bracket the expression $x_1 * x_2 * x_3 * \dots * x_n$ while preserving the order of the variables. For example, if n = 4, we have 5 possible expressions:

w*(x*(y*z)), w*((x*y)*z), (w*x)*(y*z), (w*(x*y))*z, ((w*x)*y)*z.

Write $C_{n-1}$ for the number of such expressions; the slightly shifted index is so that we get a nice expression in $C_n$ . Using the technique of divide-and-conquer, it is not hard to obtain a recurrence relation in the sequence. Indeed, if we pick an expression with n+1 variables, it must be of the form: (expr1) * (expr2), where the two expressions have (say) i and n+1-i variables respectively, where i = 1, 2, …, n. Hence we have:

$C_n = C_0 C_{n-1} + C_1 C_{n-2} + \dots + C_{n-1} C_0$ , $C_0 = 1$ . (*)

This enables us to easily compute $C_n$ until pretty large values of n, so in practice it’s already quite good. But in this case, we can go even further by obtaining an explicit formula for $C_n$ . Indeed, let $P(x) = C_0 + C_1 x + C_2 x^2 + \dots$ . Then the coefficient of $x^{n-1}$ in $P(x)^2$ is precisely the expression on the right of (*). Hence we have:

$x\cdot P(x)^2 + 1 = P(x) \implies P(x) = \frac{1 \pm \sqrt{1 - 4x}} {2x}.$

Now we apply the generalised binomial expansion on $\sqrt{1 - 4x} = (1-4x)^{1/2}$ . For n > 1, the coefficient of $x^n$ in its Taylor expansion is:

$\frac {(-4)^n} {n!} \left(\frac 1 2 \cdot \left(-\frac 1 2\right) \cdot \dots \cdot \left(\frac 1 2 - (n-1)\right)\right)$ = $-\frac{2^n \cdot 1 \cdot 3 \cdot \dots \cdot (2n-3)}{n!}$ .

Multiplying the numerator and denominator by (n-1)!, a bit of algebraic manipulation gives us the final answer: $-\frac 2 n {2n-2 \choose n-1}$ . Since the $C_n$ are all positive, we have:

$C_n = \frac 1 {n+1} {2n \choose n}$ .

Note: the above computations all hold since the power series has a positive radius of convergence, also the generalised binomial theorem holds for all $|x| < 1$ :

$(1 + x)^r = 1 + rx + \frac{r(r-1)}{2!}x^2 + \frac{r(r-1)(r-2)}{3!}x^3 + \dots$

More Appearances of Catalan Numbers.

1. Consider an $n \times n$ grid. We wish to count the number of paths from the southwest corner to the northeast along the edges of the grid which are (i) shortest, and (ii) remain below the line joining the southwest and northeast corner. E.g. when n=3, we have 5 possible paths:

The number of such paths is precisely $C_n$ .

2. Fix a convex (n+2)-gon on a plane. The number of triangulations of the polygon is exactly $C_n$ . E.g. for n=3, we have 5 possibilities.

Formal Power Series

[ Important note: only the main definitions and properties are listed here, hopefully enough to give the reader a gist of the underlying theory. Loads of details have been omitted as including them would have spanned about ten pages or so. ]

As mentioned previously, we will also look at the case where we have power series of the form:

$P(x) = a_0 + a_1 x + a_2 x^2 + \dots$

without explicitly substituting values in x. For instance, if $a_n = n^n$ , then the series doesn’t converge except at x = 0, but it still makes sense to talk about the series purely in notational form. We shall call such a power series a formal power series.

Definition. A formal power series is an expression of the form $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ , where each $a_i$ is a real (or complex) number.

At the risk of appearing repetitive, we re-iterate that f(x) is merely a notation and we have no intention of letting x take any value. In fact, we could have just as easily expressed it as an infinite-tuple: $f = (a_0, a_1, a_2, \dots)$ without any loss of data. However, the power series notation appeals more to our intuition due to the definitions which are about to follow.

Definitions. Let $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ , $g(x) = b_0 + b_1 x + b_2 x^2 + \dots$ be any two formal power series. Then their sum and product are power series defined respectively as follows:

$s(x) = c_0 + c_1 x + c_2 x^2 + \dots$ , $p(x) = d_0 + d_1 x + d_2 x^2 + \dots$ ,

where $c_n = a_n + b_n$ and $d_n = a_n b_0 + a_{n-1} b_1 + \dots + a_0 b_n$ .

Let’s go back to the example of $f(x) = 1^1 x + 2^2 x^2 + 3^3 x^3 + \dots$ which fails to converge for any non-zero x. Despite this, we can consider f(x) as a formal power series and take its square: $f(x)^2 = x^2 + 8x^3 + 70x^4 + \dots$ . Note that we can calculate any coefficient as we please, but there doesn’t seem to be a nice closed formula for the general coefficient.

It’s not hard to show that the standard arithmetical properties hold under sum and product: for any formal power series f, g and h, the following hold:

commutativity: $f+g = g+f$ , $f \times g = g\times f$ ;
associativity: $(f+g)+h = f+(g+h)$ , $(f\times g)\times h = f \times(g\times h)$ ;
distributivity: $f\times(g + h) = (f\times g) + (f\times h)$ ;
identity: the ‘0’ polynomial satisfies $0 + f = f$ , the ‘1’ polynomial satisfies $1 \times f = f$ ;
no non-zero zero divisors: (#) if $f \times g = 0$ , then f or g is zero (this will prove to be important later).

Also, addition has an inverse: namely, for any formal power series f, there is a unique power series g such that f+g = 0 (the zero-polynomial). We will denote this g by (-f). It’s easy to see that the each coefficient of g is the negation of the corresponding coefficient of f. Subtraction of formal power series is then defined by $f - g \equiv f + (-g)$ .

To recap, we have just defined addition, multiplication and subtraction on the set of all power series. [ For those who know abstract algebra, we’ve just defined a ring. ]

The next question is of interest:

When is there a multiplicative inverse of f(x)? In other words, for which f can we find a g for which $f \times g = 1$ ?

The answer may surprise you: a formal power series has a multiplicative inverse if and only if its constant term is non-zero. We’ll quickly sketch the proof: in one direction, this is easy: if $f \times g = 1$ then the constant terms of f and g must multiply to 1, so they are non-zero.

Conversely, suppose $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ , where $a_0 \ne 0$ . If $g(x) = b_0 + b_1 x + b_2 x^2 + \dots$ is its inverse, what would it look like? For starters, clearly $a_0 b_0 = 1 \implies b_0 = a_0^{-1}$ . Now suppose we have already found $b_0, b_1, \dots, b_n$ ; in order to compute the next coefficient, we need $a_0 b_{n+1} + a_1 b_n + \dots + a_{n+1} b_0 = 0$ , which gives:

$b_{n+1} = -\frac 1 {a_0} (a_1 b_n + a_2 b_{n-1} + \dots + a_{n+1} b_0).$

Hence, we can define the $b_n$ ‘s inductively from $b_0$ onwards. It follows quite easily from our definition that the resulting power series g satisfies $f(x) g(x) = 1$ .

Ok, we’re done with the definition of arithmetic operations on formal power series. Our next definition is the derivative.

Definition. The formal derivative of a formal power series $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ is defined to be the formal power series:

$\frac{d}{dx} f(x) \equiv a_1 + 2a_2 x + 3a_3 x^2 + \dots$ .

The relationship between the arithmetic operations and the formal derivative is precisely what we expect: if f and g are formal power series, then

$\frac{d}{dx} (f+g) = \frac {d}{dx} f + \frac {d}{dx} g$ ;
$\frac{d}{dx} (f\times g) = f \times \frac{d}{dx} g + \frac{d}{dx} f \times g$ ;
if f is invertible, then $\frac{d}{dx}(f^{-1}) = - \frac{d}{dx}f \times (f^{-1})^2$ (exercise: prove it, try to make use of the first two properties and avoid dealing with the explicit coefficients).

Finally, the following definition is quite important.

Let f(x) and g(x) be formal power series, where g has constant term zero and $f(x) = a_0 + a_1 x + a_2 x^2 + \dots$ . The composition f(g(x)) is defined to be:

$f(g(x)) = (f\circ g)(x) = a_0 + a_1 g(x) + a_2 g(x)^2 + \dots$ .

Note that to calculate the coefficient of $x^n$ in $f\circ g$ , one only needs to take the first n terms $a_0 + a_1 g(x) + \dots + a_n g(x)^n$ .

Quick exercise : what do we require g to have no constant term? The important properties for power series composition are:

$(f+g)\circ h = (f\circ h) + (g\circ h)$ ;
$(f\times g)\circ h = (f\circ h) \times (g\circ h)$ ;
$(f\circ g)\circ h = f\circ (g\circ h)$ ;
$\frac d {dx} (f\circ g) = \frac{df}{dx}\circ g \times \frac{dg}{dx}$ (chain law of derivative).

Now, armed with the theory of formal power series, we can define the usual power series formally without worrying on the convergence:

$\sin(x) \equiv x - \frac {x^3} {3!} + \frac {x^5} {5!} - \frac{x^7}{7!} + \dots$ ;
$\cos(x) \equiv 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \dots$ ;
$\exp(x) \equiv 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots$ ;
$\log(1+x) \equiv x - \frac{x^2} 2 + \frac{x^3} 3 - \frac{x^4} 4 + \dots$ ;
for real r, $(1+x)^r \equiv 1 + rx + \frac{r(r-1)}{2!}x^2 + \frac{r(r-1)(r-2)}{3!}x^3 + \dots$ .

Upon this definition, we find that our usual trigonometric / exponential identities hold. So our intuition carries over:

Example 1 : for any real r and s, $\exp(rx) \times \exp(sx) = \exp((r+s)x)$ .

Sketch of proof : First, show that any power series satisfying $\frac{df}{dx} = f$ is a constant multiple of exp(x) (left as an exercise; hint: find a recurrence relation among the coefficients of f). Now let $f(x) = \exp(rx) \exp(sx) - \exp((r+s)x)$ . Then its derivative satisfies, by the sum and product formulae:

$\frac{df}{dx} = r \exp(rx)\exp(sx) + s \exp(rx)\exp(sx) - (r+s)\exp((r+s)x) = (r+s) f(x)$ .

Hence, $g(x) = f((r+s)^{-1}x)$ satisfies $\frac {dg}{dx} = g$ and g is a multiple of exp(x). Since g has no constant term, it must be 0. ♦

Example 2 : $\sin(2x) = 2 \sin(x) \cos(x)$ .

Sketch of proof : (using complex numbers). Write $\cos(x) = \frac 1 2 (\exp(ix) + \exp(-ix))$ and $\sin(x) = \frac 1 {2i} (\exp(ix) - \exp(-ix))$ , where $i = \sqrt{-1}$ . Use example 1. ♦

Example 3 : for any real r and s, $(1+x)^r \times (1+x)^s = (1+x)^{r+s}$ .

Sketch of proof : let $f(x) = (1+x)^r \times (1+x)^s - (1+x)^{r+s}$ . It’s easy to show that any power series satisfying $(1+x)\frac{df}{dx} = r f$ is a constant multiple of $(1+x)^r$ (left as an exercise). Hence, the derivative of f is:

$(1+x)\frac{df}{dx} = r(1+x)^r \times (1+x)^s + (1+x)^r \times s(1+x)^s - (r+s)(1+x)^{r+s} = (r+s) f,$

so f is a constant multiple of $(1+x)^{r+s}$ . Since the constant term of f is zero, we have f = 0.

Exercise: prove that composition gives $\exp(\log(1+x)) = 1+x$ .

Having established all this background, one can now work out the arguments for the derivation of Catalan numbers by looking at formal power series alone. However, there’s one slight caveat we need to address: we found the quadratic equation $x\cdot P(x)^2 + 1 = P(x)$ satisfied by P and concluded that P can be obtained by the binomial expansion. While it’s true that the resulting binomial expansion does give Q such that $Q(x)^2 + 1 = Q(x)$ , how do we conclude that $P = \pm Q$ ?

Answer: upon completing the squares, we find that this boils down to the following deduction $R(x)^2 = S(x)^2 \implies R(x) = \pm S(x)$ . In order to derive this, we simplify $R(x)^2 - S(x)^2 = (R(x) + S(x))(R(x) - S(x))$ . The fact that there are no non-zero zero divisors (#) then says R+S or R-S is zero.

Exercises

1. Obtain Binet’s formula for the Fibonacci sequence $F_0 = 0, F_1 = 1, F_{n+1} = F_n + F_{n-1}$ for $n \ge 1$ as follows.

Define the formal power series $f(x) = F_0 + F_1 x + F_2 x^2 + \dots$ .
Prove that we have $(1 - x - x^2) f(x) = x$ , as an equality of formal power series. Hence we get $f(x) = x (1 - x - x^2)^{-1}$ .
Use partial fractions to write $\frac x {1-x-x^2} = \frac a {1-rx} + \frac b {1-sx}$ for some real constants a, b, r, s.
As power series, we thus obtain $f(x) = a(1 + rx + r^2 x^2 + \dots) + b(1 + sx + s^2 x^2 + \dots)$ . Obtain Binet’s formula.

2. Let f be the formal power series for the sequence $a_0, a_1, \dots$ .

Prove that the formal power series for the partial sums $s_n = a_0 + a_1 + \dots + a_n$ is given by $f(x)(1-x)^{-1}$ .
What is the formal power series for the sequence $s_n = a_1 + 2a_2 + \dots + na_n$ , $s_0 = 0$ ?
Express $F_1^2 + 2F_2^2 + \dots + nF_n^2$ in closed form.

Power Series and Generating Functions (II): Formal Power Series

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Power Series and Generating Functions (II): Formal Power Series

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages