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.

Find the value of $1^2 {n\choose 1} + 2^2 {n\choose 2} + \dots + n^2 {n\choose n}$ .
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.
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}$ .
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

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$ .
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$ .
Prove that $\log 2 = 1 - \frac 1 2 + \frac 1 3 - \frac 1 4 + \frac 1 5 - \dots$ .
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.

Power Series and Generating Functions (I): Basics

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Power Series and Generating Functions (I): Basics

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages