Power Series and Generating Functions (I): Basics

[ Background required: basic combinatorics, including combinations and permutations. Thus, you should know the formulae {n\choose r} = C^n_r = \frac{n!}{r!(n-r)!} and P^n_r = \frac{n!}{(n-r)!} and what they mean. Also, some examples / problems may require calculus. ]

Note: this post is still highly relevant to competition-mathematics. 🙂

To begin, for a given finite series a_0, a_1, \dots, a_n, one can write the polynomial P_a(x) = a_0 + a_1 x + \dots + a_n x^n in x. We shall call this polynomial the generating function for the sequence. This is useful when one needs to evaluate certain identities based on the a_i‘s.

For example, for a fixed positive integer n, consider the series:

a_0 = {n\choose 0}, a_1 = {n\choose 1}, \dots, a_n = {n\choose n} \implies P_a(x) = \sum_{i=0}^n {n\choose i} x^i = (1+x)^n.

The fact that there’s a nice closed form for the generating function allows us to evaluate a large number of identities.

Example 1. Let x = 1/2. We obtain the equality:

{n\choose 0} + \frac 1 2 {n\choose 1} + \frac 1 {2^2} {n\choose 2} + \dots + \frac 1 {2^n} {n\choose n} = (\frac 3 2)^n.

Example 2. We can differentiate the polynomial identity (with respect to x) to obtain:

1 {n\choose 1} + 2 {n\choose 2}x + 3 {n\choose 3} x^2 + \dots + n {n\choose n} x^{n-1} = n(1+x)^{n-1}.

Since we also know the RHS is n( {n-1 \choose 0} + {n-1\choose 1}x + \dots + {n-1\choose n-1}x^{n-1} ) we get the following combinatorial identity by looking at the coefficient of x^{r-1}:

r {n\choose r} = n {n-1 \choose r-1}.

Not entirely impressive I know, but read on.

Example 3. From the identity (1+x)^m \times (1+x)^n = (1+x)^{m+n}, we thus obtain, by looking at the coefficient of x^r on both sides:

{m \choose 0}{n\choose r} + {m\choose 1}{n \choose r-1} + \dots + {m\choose r}{n\choose 0} = {m+n\choose r},

 where {n\choose i} is defined to be zero whenever i is not in the range 0, 1, …, n. In particular, if m = n = r, then using the equality {n\choose i} = {n \choose n-i} we obtain:

{n\choose 0}^2 + {n\choose 1}^2 + \dots + {n\choose n}^2 = {2n \choose n}. 

Exercises.

  1. Find the value of 1^2 {n\choose 1} + 2^2 {n\choose 2} + \dots + n^2 {n\choose n}.
  2. Find the value of
    • {n\choose 0} + {n\choose 2} + {n\choose 4} + \dots;
    • {n\choose 0} + {n\choose 3} + {n\choose 6} + \dots, if you know complex numbers.
  3. Find the value of {n\choose 0} + \frac 1 2 {n\choose 1} + \frac 1 3 {n\choose 2} + \dots + \frac 1 {n+1} {n\choose n}.
  4. For a given 0 \le r \le n, simplify the sum:

{n\choose 0}{n\choose r} - {n\choose 1}{n\choose r-1} + {n\choose 2}{n\choose r-2} - \dots + (-1)^r {n\choose r}{n\choose 0}.

But why stop at finite series? Can we not do this for an infinite series a_0, a_1, a_2, \dots? Answer is yes! We can, at least, define the power series:

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

Once again, this is called the generating function of the infinite sequence a_i. Whether this series is meaningful, however, is an entirely different story. There’re two ways to approach this:

  • we explicitly refrain from substituting values into x, and just manipulate the power series;
  • if we insist on substituting values, however, we’d better make sure the series converges.

Let’s look at the second approach first. The following theorem is helpful:

Theorem. For any power series P(x) = \sum_{n=0}^\infty a_n x^n, there is a unique non-negative real number R (or possibly +∞) such that:

  • if |x| < R, then the series converges for x;
  • if |x| > R, then the series does not converge for x.

We call R the radius of convergence for the power series.

The proof of this is another story for another day, so we’ll skip it for now. The theorem, in fact, works for the complex domain as well, i.e. if the a_i‘s and x are complex. Two questions immediate skip to one’s mind:

  • What happens at the boundary case where |x|=R? Answer: it may or may not converge. One can only decide on a case-by-case basis.
  • How do we calculate R? Answer: there’s a nice formula for this:

R = \left(\lim_{n\to\infty} |a_n|^{1/n}\right)^{-1}

if the limit exists. Actually, there’s a nicer formula which replaces lim with limsup – the advantage of this new formula is that the limsup of a sequence is guaranteed to exist. But since that’s beyond the syllabus, let’s stick to the above formula for now.

Example 1. Consider the case a_n = n^n. Then by the above formula R = 0. So the only value of x for which \sum_{n=0}^\infty a_n x^n converges is x = 0.

Example 2. Let a_n = 1. By the above formula R = 1, so the series 1 + x + x^2 + \dots converges for all x < 1. In fact, you should know that this is \frac 1 {1-x}.

Example 3. Let a_n = n. We can apply l’Hôpital’s rule to the above formula to obtain R = 1. In fact, we can differentiate example 2 with respect to x to obtain:

1 + x + x^2 + \dots = \frac 1 {1-x} \implies 1 + 2x + 3x^2 + \dots = \frac 1 {(1-x)^2}.

[ Warning: there’s a little subtlety here involving fine points of infinite sums of infinite sums, which we’ll conveniently sweep under the rug. ]

Example 4. Let F_n be the Fibonacci sequence defined by F_0 = 0, F_1 = 1 and F_{n+1} = F_n + F_{n-1} for n \ge 1. We can calculate the radius of convergence thanks to Binet’s formula:

F_n = \frac 1 {\sqrt 5} \left( \left( \frac{1 + \sqrt 5} 2\right)^n - \left(\frac{1-\sqrt 5} 2\right)^n \right).

Thus we get \lim_{n\to\infty} |F_n|^{1/n} = \frac {1+\sqrt 5} 2. [ Exercise: prove it; hint: use (a^n + b^n)^{1/n} = a (1 + (\frac b a)^n)^{1/n}. ]  So the radius of convergence is

R = \left( \frac {1 + \sqrt 5} 2\right)^{-1} = \frac{\sqrt 5 - 1} 2.

In fact, we can have a nice closed expression for the power series P(x) = F_0 + F_1 x + F_2 x^2 + \dots. Using the identity F_{n+1} = F_n + F_{n-1}, we have:

(1 - x -x^2) P(x) = x + (F_2 - F_1 - F_0)x^2 + (F_3 - F_2 - F_1)x^3 + \dots = x.

Now, both sides are equal within the radius of convergence |x| < \frac{\sqrt 5 - 1}2. Hence, P(x) = \frac x {1 - x - x^2} for all such x. In particular, when x=1/2, we obtain:

F_0 + \frac 1 2 F_1 + \frac 1 4 F_2 + \dots + \frac 1 {2^n} F_n + \dots = 2.

Example 5. Let a_n = \frac 1 {n!}. By bounding the value of n! (e.g. by using integration, as we covered earlier), we get lim_{n\to\infty} (n!)^{1/n} = +\infty. Thus, the radius of convergence is +∞ and the sequence

P(x) = \sum_{n=0}^\infty \frac{x^n}{n!}

is convergent for all x (even complex values, if you care). Now you may or may not recognise this function, but we’ll spend a minute to derive it anyway: letting y = P(x), we have \frac{dy}{dx} = \sum_n \frac{n x^{n-1}}{n!} = y. To solve for y, we invert the derivative to obtain \frac{dx}{dy} = y^{-1} so x = \log(y)+c.  Substituting x=0, y=1 gives us c=0. So in short:

1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!} + \dots = e^x.

Example 6. Take the power series P(x) = x - \frac {x^3} 3 + \frac {x^5} 5 - \frac{x^7} 7 + \dots. Problem arises when we attempt to use the \lim_n |a_n|^{1/n} formula: since the even terms are zero while the odd terms are not, the limit does not exist! However, the main theorem still holds, i.e. the radius of convergence R must exist, regardless of whether the above limit does.

Writing t = x^2, we get P(x) = x (1 - \frac {t}3 + \frac{t^2}5 - \frac{t^3}7 + \dot), we see that the bracketed term converges for |t|<1 and diverges for |t|>1. Hence, P(x) converges for |x|<1 and diverges for |x|>1, so the radius of convergence is 1.

By integrating (1 + x^2)^{-1} = 1 - x^2 + x^4 - x^6 + \dots, we see that this power series is precisely the arc-tangent:

x - \frac {x^3}3 + \frac{x^5} 5 - \frac{x^7}7 + \dots = \tan^{-1} x.

What happens at the boundary of |x|=1? The LHS is 2 (\frac 1 {1\times 3} + \frac 1 {5\times 7} + \frac 1{9\times 11} + \dots) and the bracketed term is less than \sum_{n=1}^\infty \frac 1 {n^2} < \infty. So the power series does converge at x=1 and x=-1, and we get:

1 - \frac 1 3 + \frac 1 5 - \frac 1 7 + \dots = \tan^{-1} 1 = \frac\pi 4.

Exercises

  1. Find the value of 1^2 + \frac 1 2 2^2 + \frac 1 4 3^2 + \dots + \frac 1 {2^{n-1}} n^2 + \dots.
  2. Express the following as multiples of e (the resulting sequence forms the Bell numbers and has a combinatoric interpretation(!) – we will hopefully cover that a few posts later):
    • \frac {1^2}{1!} + \frac {2^2}{2!} + \frac {3^2}{3!} + \frac {4^2}{4!} + \dots;
    • \frac {1^3}{1!} + \frac {2^3}{2!} + \frac {3^3}{3!} + \frac {4^3}{4!} + \dots;
    • \frac {1^4}{1!} + \frac {2^4}{2!} + \frac {3^4}{3!} + \frac {4^4}{4!} + \dots.
  3. Prove that \log 2 = 1 - \frac 1 2 + \frac 1 3 - \frac 1 4 + \frac 1 5 - \dots.
  4. Calculate F_0^2 + \frac 1 2 F_1^2 + \frac 1 4 F_2^2 + \dots + \frac 1 {2^n} F_n^2 + \dots.

Coming up next: formal power series, where we manipulate power series as mere expressions, without substituting any explicit values for x. In particular, we’ll see how Catalan numbers come about.

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