Combinatorics

8 Recurrence Relations and Generating Functions

Theorem 8.1
#

The Fibonacci numbers satisfy the formula:

\[ f_n = \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n, \quad (n \geq 0).\tag {7.8} \]
Theorem 8.2
#

The sums of the binomial coefficients along the diagonals of Pascal’s triangle running upward from the left are Fibonacci numbers. More precisely, the \(n\)th Fibonacci number \(f_n\) satisfies

\[ f_n = \binom {n-1}{0} + \binom {n-2}{1} + \binom {n-3}{2} + \cdots + \binom {n-t}{t-1}, \]

where \(t = \left\lfloor \frac{n+1}{2} \right\rfloor \) is the floor of \(\frac{n+1}{2}\).

Theorem 8.3
#

Let \(n\) be a positive integer. Then

\[ g_n(x) = 1(1 + x)(1 + x + x^2)(1 + x + x^2 + x^3) \cdots (1 + x + x^2 + \cdots + x^{n-1}) \]
\[ = \frac{\prod _{j=1}^n (1 - x^j)}{(1 - x)^n}.\tag {7.14} \]
Theorem 8.4
#

Let \(S\) be the multiset \(\{ n_1 \cdot a_1, n_2 \cdot a_2, \dots , n_k \cdot a_k\} \), where \(n_1, n_2, \dots , n_k\) are nonnegative integers. Let \(h_n\) be the number of \(n\)-permutations of \(S\). Then the exponential generating function \(g^{(e)}(x)\) for the sequence \(h_0, h_1, h_2, \dots , h_n, \dots \) is given by

\[ g^{(e)}(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x), \tag {7.18} \]

where, for \(i = 1, 2, \dots , k\),

\[ f_{n_i}(x) = 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^n}{{n_i}!}. \]
Theorem 8.5
#

Let \(q\) be a nonzero number. Then \(h_n = q^n\) is a solution of the linear homogeneous recurrence relation

\[ h_n - a_1 h_{n-1} - a_2 h_{n-2} - \cdots - a_k h_{n-k} = 0, \quad (a_k \neq 0, n \geq k) \tag {7.29} \]

with constant coefficients if and only if \(q\) is a root of the polynomial equation

\[ x^k - a_1 x^{k-1} - a_2 x^{k-2} - \cdots - a_k = 0. \tag {7.30} \]

If the polynomial equation has \(k\) distinct roots \(q_1, q_2, \dots , q_k\), then

\[ h_n = c_1 q_1^n + c_2 q_2^n + \cdots + c_k q_k^n. \tag {7.31} \]

is the general solution of (7.29) in the following sense: No matter what initial values for \(h_0, h_1, \dots , h_{k-1}\) are given, there are constants \(c_1, c_2, \dots , c_k\) so that (7.31) is the unique sequence which satisfies both the recurrence relation (7.29) and the initial values.

Theorem 8.6
#

Let \(q_1, q_2, \dots , q_t\) be the distinct roots of the following characteristic equation of the linear homogeneous recurrence relation with constant coefficients:

\[ h_n = a_1 h_{n-1} + a_2 h_{n-2} + \cdots + a_k h_{n-k}, \quad a_k \neq 0, \quad (n \geq k). \tag {7.39} \]

If \(q_i\) is an \(s_i\)-fold root of the characteristic equation of (7.39), the part of the general solution of this recurrence relation corresponding to \(q_i\) is

\[ H_n^{(i)} = c_1 q_i^n + c_2 n q_i^n + \cdots + c_{s_i} n^{s_i-1} q_i^n, \]
\[ = (c_1 + c_2 n + \cdots + c_{s_i} n^{s_i-1}) q_i^n. \]

The general solution of the recurrence relation is

\[ h_n = H_n^{(1)} + H_n^{(2)} + \cdots + H_n^{(t)}. \]
Theorem 8.7
#

Let

\[ h_0, h_1, h_2, \dots , h_n, \dots \]

be a sequence of numbers that satisfies the linear homogeneous recurrence relation

\[ h_n + c_1 h_{n-1} + \cdots + c_k h_{n-k} = 0, \quad c_k \neq 0, \quad (n \geq k). \tag {7.42} \]

of order \(k\) with constant coefficients. Then its generating function \(g(x)\) is of the form

\[ g(x) = \frac{p(x)}{q(x)}, \tag {7.43} \]
Theorem 8.8
#

Let \(h_n\) denote the number of ways of dividing a convex polygonal region with \(n+1\) sides into triangular regions by inserting diagonals that do not intersect in the interior. Define \(h_1 = 1\). Then \(h_n\) satisfies the recurrence relation

\begin{align} h_n & = h_1 h_{n-1} + h_2 h_{n-2} + \cdots + h_{n-1} h_1 \\ & = \sum _{k=1}^{n-1} h_k h_{n-k}, \quad (n \geq 2). \tag {7.54} \end{align}

The solution of this recurrence relation is

\[ h_n = \frac{1}{n} \binom {2n-2}{n-1}, \quad (n = 1, 2, 3, \dots ). \]