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.
This entry was posted in Notes and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s