Problem set 8: Generating Functions

1 Generating Functions

1.1 Definition: Generating Functions

Recall that, for a sequence

\[ x_0,x_1,x_2,\ldots, \]

the infinite series

\[ \sum_{n=0}^{\infty}x_n \]

is defined as the limit of its partial sums

\[ S_n=x_0+x_1+\cdots+x_n. \]

The series is called convergent if the limit

\[ \lim_{n\to\infty}S_n \]

exists, and divergent otherwise.

Given a sequence \((a_n)_{n\geq 0}\), its ordinary generating function is the formal power series

\[ A(t)=\sum_{n=0}^{\infty}a_nt^n. \]

Generating functions are useful for proving combinatorial identities and solving recurrence relations.

If we substitute a real or complex number for the formal variable \(t\), we must consider whether the resulting infinite series converges.

1.2 Theorem: Cauchy–Hadamard Formula

Consider the power series

\[ A(t)=\sum_{n=0}^{\infty}a_nt^n. \]

Its radius of convergence \(R\) is determined by

\[ \boxed{ \frac{1}{R} = \limsup_{n\to\infty}\sqrt[n]{|a_n|}. } \]

The series:

  • Converges absolutely when \(|t|<R\).
  • Diverges when \(|t|>R\).
  • May converge or diverge when \(|t|=R\).

The set

\[ \{t\in\mathbb C:|t|<R\} \]

is called the disk of convergence.

1.3 Problems

Find the radius of convergence of each of the following power series.

(a)

\[ \sum_{n=0}^{\infty}t^n. \]

(b)

\[ \sum_{n=0}^{\infty}(-1)^nt^n. \]

(c)

\[ \sum_{n=0}^{\infty}\lambda^nt^n, \qquad \lambda\in\mathbb R. \]

(d)

\[ \frac{1}{1-t^2}. \]

Give examples of power series with radius of convergence \(R>0\) such that, at the boundary points \(t=\pm R\):

(a) The series converges at both points.

(b) The series diverges at both points.

(c) The series converges at one point and diverges at the other.

Consider the sequence

\[ a_n=C_1\lambda_1^n+C_2\lambda_2^n, \]

where \(C_1,C_2,\lambda_1,\lambda_2\) are constants.

(a) Find its generating function

\[ A(t)=\sum_{n=0}^{\infty}a_nt^n. \]

(b) Determine its radius of convergence.

Determine all real numbers \(t\) for which the power series

\[ \sum_{n=0}^{\infty}a_nt^n \]

converges, where the coefficients are defined by

\[ a_n= \begin{cases} 3(-6)^n+4\cdot 3^n, & n=3k,\\[4pt] 5(-14)^n+2\cdot 2^n, & n=3k+1,\\[4pt] 6(-3)^n, & n=3k+2, \end{cases} \]

for nonnegative integers \(k\).

Find the radius of convergence of the generalized binomial series

\[ (1+t)^\alpha = \sum_{n=0}^{\infty} \binom{\alpha}{n}t^n \]

for an arbitrary real number

\[ \alpha\in\mathbb R. \]

Suppose a sequence \((a_n)\) satisfies the recurrence relation

\[ a_n=ka_{n-1}+la_{n-2}, \qquad n\geq 2, \]

where \(k,l\) are constants.

Assume that the characteristic polynomial

\[ x^2-kx-l \]

has two distinct roots.

(a) Prove that the generating function

\[ A(t)=\sum_{n=0}^{\infty}a_nt^n \]

can be written in the form

\[ \boxed{ A(t)=\frac{At+B}{1-kt-lt^2}. } \]

Express the constants \(A\) and \(B\) in terms of

\[ k,l,a_0,a_1. \]

(b) Prove that the generating function can also be represented as

\[ \boxed{ A(t)= \frac{E}{1-\alpha_1t} + \frac{F}{1-\alpha_2t}. } \]

Find the constants

\[ E,F,\alpha_1,\alpha_2. \]

(c) Reformulate and prove the results of parts (a) and (b) when the characteristic polynomial has a repeated root.

Evaluate the following expressions.

(a)

\[ \sum_{k=0}^{n} \frac{1}{2^k}\binom{n}{k}. \]

(b)

\[ \sum_{n=0}^{\infty}\frac{F_n}{2^n}, \]

where \(F_n\) denotes the \(n\)-th Fibonacci number.

The Lucas numbers \((L_n)_{n\geq 0}\) are defined by

\[ L_0=2,\qquad L_1=1, \]

and

\[ L_n=L_{n-1}+L_{n-2}, \qquad n\geq 2. \]

Find the following quantities.

(a)

\[ \lim_{n\to\infty}\frac{L_n}{2^n}. \]

(b)

\[ \sum_{n=0}^{\infty}\frac{L_n}{2^n}. \]

Suppose we have coins with denominations of

\[ 1,\quad 2,\quad 5 \]

rubles.

(a) Find the generating function for the number of ways to obtain a total of \(n\) rubles using these coins.

Assume that an unlimited number of coins of each denomination is available.

(b) Find the generating function if there are only three 5-ruble coins available, while the numbers of 1-ruble and 2-ruble coins remain unlimited.

Find the generating function for the number of:

(a) Ordered partitions of \(n\) into exactly \(k\) positive summands.

(b) Ordered partitions of \(n\) into positive summands.

(c) Unordered partitions of \(n\).

(d) Unordered partitions of \(n\) into odd positive summands.

(e) Unordered partitions of \(n\) into pairwise distinct positive summands.

(f) Prove that the generating functions obtained in parts (d) and (e) are equal.

Let

\[ f(t)=\sum_{n=0}^{\infty}a_nt^n \]

be the generating function of the sequence \((a_n)_{n\geq 0}\).

Find the generating function of each of the following sequences.

(a) The sequence of partial sums

\[ s_n=a_0+a_1+\cdots+a_n. \]

(b) The sequence of consecutive differences

\[ d_n=a_n-a_{n-1}, \qquad n\geq 1. \]

2 Additional Problems

(a) Prove the combinatorial identity

\[ \boxed{ 4^n = \sum_{i=0}^{n} \binom{2i}{i} \binom{2(n-i)}{n-i}. } \]

(b) Evaluate the alternating sum

\[ \binom{n}{0}^2 - \binom{n}{1}^2 + \binom{n}{2}^2 -\cdots+ (-1)^n\binom{n}{n}^2. \]

How many polynomials \(P(x)\) with coefficients belonging to the set

\[ \{0,1,2,3\} \]

satisfy

\[ P(2)=n? \]

Let \(a_n\) denote the number of permutations of \(n\) elements that contain no cycles of length 1 or 2.

Find the limit

\[ \boxed{ \lim_{n\to\infty}\frac{a_n}{n!}. } \]

Let \(p\) be an odd prime number.

How many subsets of cardinality \(p\) of the set

\[ \{1,2,\ldots,2p\} \]

have the property that the sum of their elements is divisible by \(p\)?

Let \(k\) be a fixed positive integer.

For every nonnegative integer \(n\), define \(f(n)\) as the number of integer vectors

\[ (x_1,\ldots,x_k)\in\mathbb Z^k \]

satisfying

\[ |x_1|+\cdots+|x_k|\leq n. \]

Prove that

\[ \boxed{ f(n)^2\geq f(n-1)f(n+1) } \]

for every integer \(n\geq 1\).