The Lumenary · Early undergraduate

Recurrences and generating functions

Name: ______________________

Date: ______________________

You will learn to

Solve linear recurrences with constant coefficients using the characteristic polynomial, including repeated roots and inhomogeneous terms, and prove that the solution is determined by its initial values
Prove Binet's formula $F_n = (\varphi^n - \psi^n)/\sqrt5$ in two ways, by characteristic roots and by generating functions
Work with ordinary generating functions as formal power series, and use them to solve recurrences and counting problems
Prove that the Catalan numbers $\binom{2n}{n}/(n+1)$ count balanced bracket sequences, by a reflection argument and by a generating function
Compare growth rates with $O$ , $\Omega$ , $\Theta$ , $o$ and $\sim$ , and solve the divide-and-conquer recurrence $T(n) = 2T(n/2) + n$ on powers of two

1.
In how many ways can a $1 \times 9$ strip be tiled by $1 \times 1$ squares and $1 \times 2$ dominoes?
2.
Find the characteristic roots of the recurrence $a_{n+2} = a_{n+1} + 6a_n$ . Enter them as a set, e.g. 4, -1.
3.
The sequence $(a_n)$ satisfies $a_{n+2} = a_{n+1} + 6a_n$ with $a_0 = 2$ and $a_1 = 1$ . Find a closed formula for $a_n$ and use it to compute $a_5$ .
4.
Which formula describes all solutions of $a_{n+2} = 6a_{n+1} - 9a_n$ (with $A$ , $B$ arbitrary constants)?
- A. $a_n = (A + Bn)\,3^n$
- B. $a_n = A\,3^n + B\,3^n$
- C. $a_n = A\,3^n + B(-3)^n$
- D. $a_n = (A + Bn^2)\,3^n$
5.
The power series $\sum_{n \ge 0} n!\,x^n$ converges only at $x = 0$ . Which statement about it, as an element of the ring $\Q[[x]]$ of formal power series, is true?
- A.It has a multiplicative inverse in $\Q[[x]]$ .
- B.It is not a valid element of $\Q[[x]]$ , because it diverges.
- C.It can be added to other series but not multiplied, because products would diverge.
- D.It is invertible only if we restrict to $x = 0$ .
6.
Which of these statements are true? (Choose all that apply.)
- A. $n^2 = O(n^3)$
- B. $n^3 = O(n^2)$
- C. $2^{n+1} = O(2^n)$
- D. $4^n = O(2^n)$
- E. $\log_2 n = \Theta(\ln n)$
- F. $n \log n = \Omega(n)$
7.
In the proof of Lemma 2 (two solutions of $a_{n+2} = p\,a_{n+1} + q\,a_n$ with the same $a_0$ and $a_1$ agree everywhere), the induction proves the statement " $a_n = b_n$ and $a_{n+1} = b_{n+1}$ " rather than just " $a_n = b_n$ ". Why?
- A.To deduce $a_{n+2} = b_{n+2}$ from the recurrence we need equality at two consecutive indices, so the inductive hypothesis must carry both.
- B.Because $p$ or $q$ might be zero.
- C.Because ordinary induction is not valid for sequences.
- D.Because the characteristic roots might be repeated.
8.
Using the lesson's definition IsSol p q a (meaning ∀ n, a (n + 2) = p * a (n + 1) + q * a n), which Lean statement correctly formalises: every real sequence satisfying $a_{n+2} = a_{n+1} + a_n$ with $a_0 = 0$ and $a_1 = 1$ is the Fibonacci sequence?
- A.∀ a : ℕ → ℝ, IsSol 1 1 a → a 0 = 0 → a 1 = 1 → ∀ n, a n = Nat.fib n
- B.∀ a : ℕ → ℝ, IsSol 1 1 a → ∀ n, a n = Nat.fib n
- C.∃ a : ℕ → ℝ, IsSol 1 1 a ∧ a 0 = 0 ∧ a 1 = 1
- D.∀ a : ℕ → ℝ, a 0 = 0 → a 1 = 1 → ∀ n, a n = Nat.fib n
9.
In how many ways can the product $x_1 x_2 x_3 x_4 x_5 x_6$ be fully bracketed, keeping the factors in order? (For three factors there are two: $(x_1x_2)x_3$ and $x_1(x_2x_3)$ .)
10.
Write series_inverse(a, N) that returns the first N coefficients of $1/A(x)$ , where a is the list of coefficients of a power series $A(x)$ with a[0] == 1 (missing coefficients count as $0$ ). Use the recursion from the Proposition on inverses: $b_0 = 1$ and $b_n = -\sum_{i=1}^{n} a_i b_{n-i}$ . Then check that $1/(1 - x - x^2)$ gives the Fibonacci numbers $F_{n+1}$ .
Computational — Practice

Answer key — Recurrences and generating functions

1.
Let $t_n$ be the number of tilings of a $1 \times n$ strip. The last tile is a square (leaving $t_{n-1}$ possibilities) or a domino (leaving $t_{n-2}$ ), so $t_n = t_{n-1} + t_{n-2}$ , with $t_1 = 1$ and $t_2 = 2$ . The values are $1, 2, 3, 5, 8, 13, 21, 34, 55$ , so $t_9 = 55 = F_{10}$ .
2.
The characteristic polynomial is $\chi(x) = x^2 - x - 6 = (x - 3)(x + 2)$ , so the roots are $3$ and $-2$ . Every solution is $a_n = A\,3^n + B(-2)^n$ .
3.
From $a_n = A\,3^n + B(-2)^n$ : $a_0 = A + B = 2$ and $a_1 = 3A - 2B = 1$ . Substituting $B = 2 - A$ gives $5A - 4 = 1$ , so $A = 1$ , $B = 1$ and $a_n = 3^n + (-2)^n$ . Hence $a_5 = 243 - 32 = 211$ . Check with the recurrence: $a_2 = 1 + 12 = 13$ , $a_3 = 13 + 6 = 19$ , $a_4 = 19 + 78 = 97$ , $a_5 = 97 + 114 = 211$ .
4.
The characteristic polynomial $x^2 - 6x + 9 = (x - 3)^2$ has a double root $r = 3$ . By Theorem 2, the solutions are exactly $(A + Bn)3^n$ : both $3^n$ and $n\,3^n$ are solutions, and their initial values $(1, 3)$ and $(0, 3)$ are linearly independent, so every pair $(a_0, a_1)$ can be matched.
5.
In $\Q[[x]]$ a series is invertible if and only if its constant term is non-zero; the coefficients of the inverse are found one at a time from $\sum_{i=0}^{n} a_i b_{n-i} = 0$ . The constant term here is $0! = 1$ , so the series is invertible; its inverse begins $1 - x - x^2 - 3x^3 - 13x^4 - 71x^5 - \cdots$ . This is the Lean theorem factorial_series_isUnit.
6.
True: (a) $n^2 \le 1 \cdot n^3$ ; (c) $2^{n+1} = 2 \cdot 2^n$ ; (e) $\log_2 n = (1/\ln 2)\ln n$ ; (f) $n \log n \ge n$ for $n \ge e$ . False: (b) $n^3/n^2 = n \to \infty$ ; (d) $4^n/2^n = 2^n \to \infty$ .
7.
The recurrence determines a term from the two previous ones. To show $a_{n+2} = b_{n+2}$ we need both $a_{n+1} = b_{n+1}$ and $a_n = b_n$ . Strengthening the statement to a pair of consecutive equalities makes the inductive step go through; this is the same as strong induction with two base cases. The Lean proof isSol_unique does exactly this.
8.
Option (a) quantifies over all sequences and assumes the recurrence and both initial values. Option (b) drops the initial values (the Lucas numbers are a counterexample), (c) is only an existence statement, and (d) drops the recurrence ( $a_n = n$ is a counterexample). Formal statements make every hypothesis visible — leaving one out usually makes the statement false, and Lean will refuse to prove it.
9.
The last multiplication splits $x_1 \cdots x_m$ into $(x_1 \cdots x_i)(x_{i+1} \cdots x_m)$ , so $b_m = \sum_{i=1}^{m-1} b_i b_{m-i}$ with $b_1 = 1$ . This is Segner's recurrence shifted by one, so $b_m = C_{m-1}$ , and $b_6 = C_5 = \frac{1}{6}\binom{10}{5} = \frac{252}{6} = 42$ .
10.
```
def series_inverse(a, N):
    b = []
    for n in range(N):
        if n == 0:
            b.append(1)
            continue
        s = sum(a[i] * b[n - i] for i in range(1, n + 1) if i < len(a))
        b.append(-s)
    return b
```
The coefficient of $x^n$ in $A(x)B(x)$ is $\sum_{i=0}^{n} a_i b_{n-i}$ ; setting it to $0$ for $n \ge 1$ (and using $a_0 = 1$ ) gives $b_n = -\sum_{i=1}^{n} a_i b_{n-i}$ . For $A = 1 - x - x^2$ this reads $b_n = b_{n-1} + b_{n-2}$ with $b_0 = b_1 = 1$ : the Fibonacci recurrence, so $b_n = F_{n+1}$ . The tests are finite checks; the Proposition is the proof that the method always works when $a_0 \ne 0$ .