# Lecture 6: More on Generating Functions

Source: https://www.youtube.com/watch?v=XfRe9i3FR1U
Recap page: https://rapidrecap.app/video/XfRe9i3FR1U
Generated: 2025-12-17T16:37:46.946+00:00

---
## Quick Overview

Peter Shor reviews fundamental operations on generating functions, including addition for disjoint unions and multiplication for direct products, before demonstrating how to derive closed-form expressions for sequences like binary strings and Fibonacci numbers using recurrence relations and partial fraction decomposition.

**Key Points:**
- The generating function for the disjoint union of two classes of things, $C = A \cup B$, is $C(x) = A(x) + B(x)$, while the generating function for the direct product, $C = A \times B$, is $C(x) = A(x)B(x)$.
- The generating function $S(x)$ for the set of finite sequences of things in set $A$, where $A(x)$ is the generating function for $A$, is $S(x) = 1 + A(x) + A(x)^2 + A(x)^3 + \dots = 1 / (1 - A(x))$.
- The number of messages that can be sent using dots (length 1, represented by $x$) and dashes (length 2, represented by $x^2$) follows the Fibonacci sequence, leading to the generating function $f(x) = 1 / (1 - x - x^2)$ using the sequence definition $f_0=1, f_1=1$.
- Shor derives the closed form for the Fibonacci numbers using partial fractions on $f(x) = 1 / (1 - x - x^2)$, identifying roots $\phi_+$ and $\phi_-$ of $y^2 - y - 1 = 0$, resulting in $f_n = a\phi_+^{n+1} + b\phi_-^{n+1}$.
- The information transmission rate for the dot/dash channel is determined by the growth rate of the Fibonacci numbers, approximately $\log_2(\phi_+)$.
- Shor demonstrates deriving the generating function for tiling a $2 \times n$ strip using specific tiles as $g(x) = 1 / (1 - x^2 - 2x^3)$ by recognizing the tiling structure corresponds to the sequence formula $1 / (1 - 2x^3 / (1 - x^2))$.
- Sums along the diagonals of Pascal's triangle yield Fibonacci numbers; substituting $x=z^2$ and $y=z$ into the 2D generating function $1 / (1 - x - y)$ produces the generating function for these diagonal sums: $1 / (1 - z - z^2)$.

**Context:** This lecture, titled "Lecture 6: More on Generating Functions," continues the discussion on using generating functions to solve combinatorial problems, building upon previous material. Peter Shor reviews basic generating function operations for set combinations (union/disjoint union, direct product) and then applies these concepts to derive closed-form solutions for more complex sequences, specifically focusing on binary strings and the Fibonacci numbers derived from a telegraph coding problem involving dots (length 1) and dashes (length 2).

## Detailed Analysis

The lecture begins by formalizing generating function manipulations: $C(x) = A(x) + B(x)$ for disjoint unions and $C(x) = A(x)B(x)$ for direct products, where the latter corresponds to the convolution of coefficients. Shor then introduces the generating function for the set of finite sequences, $S(x) = 1 / (1 - A(x))$, illustrating this with binary strings where $A(x) = 2x$, yielding $S(x) = 1 / (1 - 2x)$. The core of the lecture focuses on Fibonacci numbers derived from counting dot/dash sequences; this recurrence, $f_n = f_{n-1} + f_{n-2}$, leads to the generating function $f(x) = 1 / (1 - x - x^2)$ using the initial conditions $f_0=1, f_1=1$. Shor solves this using partial fractions after transforming the denominator into a quadratic equation involving the golden ratio roots $\phi_+$ and $\phi_-$, resulting in Binet's formula structure for $f_n$, which determines the information transmission rate of the channel. Finally, Shor uses the sequence formula $S(x) = 1 / (1 - A(x))$ to quickly find the generating function for dot/dash sequences, $1 / (1 - x - x^2)$, circumventing the recurrence derivation. He also analyzes the diagonal sums of Pascal's triangle, showing they are Fibonacci numbers by substituting $x=z^2$ and $y=z$ into the 2D generating function $1 / (1 - x - y)$, resulting in $1 / (1 - z - z^2)$.

### Generating Function Algebra

- $C(x) = A(x) + B(x)$ for disjoint union
- $C(x) = A(x)B(x)$ for direct product
- $S(x) = 1 / (1 - A(x))$ for finite sequences of A

### Binary String Example

- Generating function $A(x) = 2x$ for length 1 sequences
- Sequence generating function $S(x) = 1 + 2x + 4x^2 + \dots = 1 / (1 - 2x)$

### Telegraph Channel Problem

- Messages follow Fibonacci numbers ($f_n = f_{n-1} + f_{n-2}$) due to length 1 dots and length 2 dashes
- Generating function $f(x) = 1 / (1 - x - x^2)$ based on $f_0=1, f_1=1$

### Fibonacci Closed Form Derivation

- Solved $f(x)$ using partial fractions after relating $1 - x - x^2$ to roots $\phi_+, \phi_-$ of $y^2 - y - 1 = 0$
- Resulting formula $f_n = a\phi_+^{n+1} + b\phi_-^{n+1}$ gives growth rate $\log_2(\phi_+)$

### Alternative Derivation for Dot/Dash

- Used sequence formula $S(x) = 1 / (1 - A(x))$ where $A(x) = x + x^2$ (dot + dash) to immediately obtain $1 / (1 - x - x^2)$

### Pascal's Triangle Diagonals

- Diagonal sums yield Fibonacci numbers
- 2D generating function $P(x, y) = 1 / (1 - x - y)$
- Substitution $x=z^2, y=z$ yields Fibonacci GF $1 / (1 - z - z^2)$

### Alternative Fibonacci Proof via Counting

- Grouping sequences by number of dots and dashes maps directly to sums of binomial coefficients found on Pascal's triangle diagonals