本讲要解决的问题

上一讲用 Dyck 路径算出了 Catalan 数。这一讲把生成函数当成一台翻译机器：一边是组合对象，一边是幂级数；组合上的「并」「拼接」「排成序列」分别对应幂级数的「加」「乘」「$1/(1-A)$」。

机器造好之后，拿它去攻一个经典问题：长度为 $n$ 的电报码有多少种？答案是 Fibonacci 数。再往下问一步——第 $n$ 个 Fibonacci 数到底有多大？ 生成函数会给出一个闭式公式，进而给出信息的传输速率。

时间轴

三条基本操作

设第 $n$ 个对象有 $a_n$ 个，生成函数是

$$A(x)=\sum_{n\ge 0}a_nx^n .$$

并：相加

若 $C$ 是 $A$ 与 $B$ 的不交并（两种来源互不重叠），则 $c_n=a_n+b_n$，于是

$$C(x)=A(x)+B(x).$$

积：相乘

若 $C$ 中的对象由一个 $A$ 对象和一个 $B$ 对象拼成，且大小相加，则

$$c_n=\sum_{i=0}^{n}a_i\,b_{n-i}, \qquad C(x)=A(x)B(x).$$

「大小相加」是关键：卷积的下标 $i+(n-i)=n$ 正是这一条的代数表现。

序列：取倒数

设 $A$ 中每个对象大小至少为 $1$。由 $A$ 的对象排成的有限序列（可以为空）构成集合 $S$。则

$$S(x)=1+A(x)+A(x)^2+A(x)^3+\cdots=\frac{1}{1-A(x)} .$$

第一项 $1$ 是空序列；$A(x)^k$ 是长度恰为 $k$ 的序列。为什么要求大小为 $1$ 以上？ 因为若存在大小为 $0$ 的对象，就能往任意序列里塞任意多个而大小不变，于是每个大小都有无穷多个序列，系数失去意义。

例如 $A=\{0,1\}$，则 $A(x)=2x$（长度为 $1$ 的串有两个），二进制串的生成函数是

$$S(x)=\frac{1}{1-2x}=1+2x+4x^2+8x^3+\cdots,$$

系数 $2^n$ 正是长度为 $n$ 的二进制串个数。

点划电报码：Fibonacci 数登场

用点「·」和划「—」发电报，点占 $1$ 个单位时间，划占 $2$ 个单位。问：长度为 $n$ 的消息有多少条？

逐个列出：

• $n=1$：只有「·」，$f_1=1$。
• $n=2$：「· ·」「—」，$f_2=2$。
• $n=3$：「· · ·」「· —」「— ·」，$f_3=3$。
• $n=4$：五种；$n=5$：八种。

这正是 Fibonacci 数。递推的理由只有一句话：看最后一段是点还是划。

$$f_n=f_{n-1}+f_{n-2}.$$

末尾是点，前面是长度 $n-1$ 的任意消息；末尾是划，前面是长度 $n-2$ 的任意消息。

本课约定

$$f_0=1,\quad f_1=1,\quad f_2=2,\quad f_3=3,\quad f_4=5,\dots$$

$f_0=1$ 对应「空消息」——什么都不发也是一种发法，这让后面的公式最简洁。注意这与维基百科的约定 $F_0=0,F_1=1$ 整体差一位：本讲的 $f_n$ 等于通常的 $F_{n+1}$。

用生成函数解递推

建立方程

设 $F(x)=\sum_{n\ge0}f_nx^n$。把递推对所有 $n\ge2$ 乘以 $x^n$ 求和：

$$\sum_{n\ge2}f_nx^n=\sum_{n\ge2}f_{n-1}x^n+\sum_{n\ge2}f_{n-2}x^n .$$

左边是 $F(x)-f_0-f_1x=F(x)-1-x$；右边第一项是 $x\big(F(x)-f_0\big)=x(F(x)-1)$，第二项是 $x^2F(x)$。代入：

$$F-1-x=x(F-1)+x^2F .$$

整理得

$$F(x)\,(1-x-x^2)=1, \qquad F(x)=\frac{1}{1-x-x^2}.$$

检验常数项：$f_0-f_{-1}-f_{-2}$ 没有定义，但直接看等式右边，$n=0$ 时只剩 $f_0=1$，正是分子上的 $1$。

部分分式

把分母因式分解。令

$$1-x-x^2=(1-\phi_+x)(1-\phi_-x),$$

比较系数得 $\phi_++\phi_-=1$、$\phi_+\phi_-=-1$，所以

$$\phi_+=\frac{1+\sqrt5}{2},\qquad \phi_-=\frac{1-\sqrt5}{2}.$$

于是设

$$\frac{1}{1-x-x^2}=\frac{A}{1-\phi_+x}+\frac{B}{1-\phi_-x}.$$

通分后分子为 $A(1-\phi_-x)+B(1-\phi_+x)$，要求它恒等于 $1$。比较常数项与一次项：

$$A+B=1,\qquad A\phi_-+B\phi_+=0 .$$

由第一式 $B=1-A$，代入第二式：

$$A\phi_-+(1-A)\phi_+=0 \iff A(\phi_--\phi_+)=-\phi_+ \iff A=\frac{\phi_+}{\phi_+-\phi_-}=\frac{\phi_+}{\sqrt5}.$$

同理

$$B=\frac{-\phi_-}{\sqrt5}.$$

课程口述时把 $B$ 的符号说反了；用 $n=0$ 一验就知道必须是负号（见下）。

Binet 公式

利用

$$\frac{1}{1-\phi x}=\sum_{n\ge0}\phi^nx^n,$$

得到

$$F(x)=\frac{1}{\sqrt5}\sum_{n\ge0}\left(\phi_+^{n+1}-\phi_-^{n+1}\right)x^n,$$

即

$$f_n=\frac{\phi_+^{n+1}-\phi_-^{n+1}}{\sqrt5}.$$

验算 $n=0$：$(\phi_+-\phi_-)/\sqrt5=\sqrt5/\sqrt5=1$ ✓。$n=1$：$(\phi_+^2-\phi_-^2)/\sqrt5$，而 $\phi_+^2=\phi_++1$、$\phi_-^2=\phi_-+1$，差为 $\phi_+-\phi_-=\sqrt5$，得 $1$ ✓。

增长率与信息率

因为 $|\phi_-|<1$，第二项随 $n$ 指数衰减，可以忽略：

$$f_n\approx\frac{\phi_+^{\,n+1}}{\sqrt5}.$$

$\phi_+=(1+\sqrt5)/2\approx1.618$。长度为 $n$ 时可发送的消息数约为 $\phi_+^n/\sqrt5$，所以每单位时间能传递的信息量是

$$\frac{\log_2 f_n}{n}\to\log_2\phi_+\approx0.694\ \text{bit/单位时间}.$$

常数因子 $1/\sqrt5$ 与 $n+1$ 只影响低阶项，不改变指数增长率。这正是后面信息论部分要一般化的结论：信道的容量由「增长率的对数」决定。

铺砖问题：序列公式的直接应用

用两种可以翻转的骨牌铺 $2\times n$ 的条带，问有多少种铺法。按课程的定义，先数不可再分的基本块 $a_n$：不存在一条竖线把条带切成两段各自可铺。

逐一检查可得

$$a_3=2,\qquad a_5=2,\qquad a_7=2,\qquad a_{2k}=0,$$

即基本块只能出现在奇数长度 $3,5,7,\dots$，且每种长度恰有两种（互为镜像）。于是

$$A(x)=2x^3+2x^5+2x^7+\cdots=\frac{2x^3}{1-x^2}.$$

任意铺法都是基本块的一个序列，由序列公式

$$B(x)=\frac{1}{1-A(x)} =\frac{1}{1-\dfrac{2x^3}{1-x^2}} =\frac{1-x^2}{1-x^2-2x^3}.$$

展开系数：

$$B(x)=1+2x^3+2x^5+4x^6+2x^7+8x^8+\cdots$$

例如长度 $6$ 的铺法是把两个长度 $3$ 的基本块并排，各有 $2$ 种，共 $2\times2=4$ 种。

从生成函数读出递推

分母 $1-x^2-2x^3$ 给出递推，分子给出初值。把 $B(x)(1-x^2-2x^3)=1-x^2$ 逐项比较：

$$b_n-b_{n-2}-2b_{n-3}= \begin{cases} 1,&n=0,\\ -1,&n=2,\\ 0,&\text{其他}. \end{cases}$$

因此在初值之后，

$$b_n=b_{n-2}+2b_{n-3}.$$

这也解释了一个看似奇怪的事实：$b_2=0$ 而不是 $1$。递推若从 $n=2$ 就开始用，会给出 $b_2=b_0+2b_{-1}=1$，但分子在 $x^2$ 处多了一个 $-1$，把 $b_2$ 修正为 $0$。用组合语言说：空铺法不能「加上一个基本块」变成长度 $2$ 的铺法，因为最短的基本块长度是 $3$。

同一递推也可以直接看出来：任何非空铺法，要么在末尾接一个长度 $2$ 的竖放块（$b_{n-2}$ 种），要么接一个长度 $3$ 的基本块（两种朝向，$2b_{n-3}$ 种）。

Pascal 三角形与 Fibonacci 数

Pascal 三角形的二维生成函数。设

$$P(x,y)=\sum_{a,b\ge0}\binom{a+b}{a}x^ay^b .$$

先按行求和：固定 $n=a+b$，一行之和为

$$\sum_{a=0}^{n}\binom{n}{a}x^ay^{n-a}=(x+y)^n .$$

再对所有行求和：

$$P(x,y)=\sum_{n\ge0}(x+y)^n=\frac{1}{1-x-y}.$$

对角线

沿「斜对角线」求和会得到 Fibonacci 数：

$$1+1=2,\qquad 1+3+1=5,\qquad 1+6+5+1=13,\dots$$

做法是代入 $x=z^2,\ y=z$。此时 $x^ay^b=z^{2a+b}$，于是

$$P(z^2,z)=\frac{1}{1-z-z^2}=F(z).$$

也就是说，把 Pascal 三角形的二维生成函数限制在这条抛物线上，得到的恰好是 Fibonacci 生成函数；$z^n$ 的系数就是 $f_n$。展开系数即得恒等式

$$f_n=\sum_{k\ge0}\binom{n-k}{k}.$$

验算 $n=5$：$\binom50+\binom41+\binom32=1+4+3=8=f_5$ ✓。

组合证明：数两遍

同一个恒等式可以完全不靠生成函数，只用「数两遍」证明。

长度为 $n$ 的点划消息共有 $f_n$ 条。换个方式数：按划的个数 $k$ 分类。若有 $k$ 个划，它们占用 $2k$ 个时间单位，剩下的 $n-2k$ 个单位由点填满，于是符号总数是

$$k+(n-2k)=n-k .$$

在 $n-k$ 个位置中选 $k$ 个放划，其余放点，方案数为 $\binom{n-k}{k}$。对所有可能的 $k$ 求和：

$$f_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}.$$

这与生成函数得到的是同一个恒等式——两条完全不同的路径在同一处汇合，是组合数学里很典型的验证方式。

本节结论

• 三条操作：不交并 $\to$ 相加；大小相加的拼接 $\to$ 相乘；序列 $\to 1/(1-A(x))$，且不能有大小为 $0$ 的对象。
• 点划消息数满足 $f_n=f_{n-1}+f_{n-2}$，$f_0=1$，生成函数 $F(x)=1/(1-x-x^2)$。
• 部分分式给出 Binet 公式 $f_n=(\phi_+^{n+1}-\phi_-^{n+1})/\sqrt5$。
• 增长率为 $\phi_+$，每单位时间可传 $\log_2\phi_+\approx0.694$ bit。
• 铺砖问题的生成函数为 $(1-x^2)/(1-x^2-2x^3)$，对应递推 $b_n=b_{n-2}+2b_{n-3}$。
• Pascal 三角形生成函数 $1/(1-x-y)$，代入 $x=z^2,y=z$ 得到 Fibonacci 生成函数。
• 恒等式 $f_n=\sum_k\binom{n-k}{k}$ 既有生成函数证明，也有「数两遍」证明。

理解检验

1. 为什么有限序列的生成函数是 $1/(1-A(x))$？为什么必须假设 $A$ 中没有大小为 $0$ 的对象？

参考答案：序列 $(\alpha_1,\dots,\alpha_k)$ 的大小是各对象大小之和。若 $A$ 只有大小 $\ge1$ 的对象，那么大小为 $n$ 的序列只能是长度不超过 $n$ 的序列，$A(x)^k$ 中 $x^n$ 的系数正是「$k$ 个对象大小和为 $n$」的方案数，因此总生成函数是 $\sum_{k\ge0}A(x)^k=1/(1-A(x))$。若存在大小为 $0$ 的对象，就可以在任意序列中插入任意多个它而大小不变，于是每个大小都有无穷多个序列，系数发散，生成函数不再是形式幂级数。

2. 为什么本讲取 $f_0=1$？如果改用 $F_0=0,F_1=1$，生成函数会变成什么？

参考答案：$f_0=1$ 对应空消息——一个字符都不发也算一种「消息」，这样递推 $f_n=f_{n-1}+f_{n-2}$ 从 $n=2$ 起成立，且 $F(x)(1-x-x^2)=1$ 的右端是最简单的常数 $1$。若用通常约定 $F_0=0,F_1=1$，则 $F_n=f_{n-1}$，生成函数变为 $xF(x)=x/(1-x-x^2)$，分母不变，只是分子多了一个 $x$。

3. 完整解出部分分式中的 $A$ 与 $B$，并说明为什么 $B$ 必须带负号。

参考答案：由 $A+B=1$ 与 $A\phi_-+B\phi_+=0$，消去 $B$：

$$A\phi_-+(1-A)\phi_+=0\Longrightarrow A(\phi_--\phi_+)=-\phi_+ \Longrightarrow A=\frac{\phi_+}{\phi_+-\phi_-}=\frac{\phi_+}{\sqrt5}.$$

再得 $B=1-A=\dfrac{\sqrt5-\phi_+}{\sqrt5}$。因为 $\sqrt5=\phi_+-\phi_-$，所以 $B=\dfrac{-\phi_-}{\sqrt5}$。$B$ 必须为负，是因为 $\phi_-<0$，而若取正号，$n=0$ 时 $A+B=(\phi_++\phi_-)/\sqrt5=1/\sqrt5\ne1$，与 $f_0=1$ 矛盾。

4. 为什么 $f_n$ 的增长率是 $\phi_+$ 而不是 $\phi_-$？这与「每单位时间传多少 bit」有什么关系？

参考答案：$f_n=(\phi_+^{n+1}-\phi_-^{n+1})/\sqrt5$，而 $|\phi_-|\approx0.618<1$，所以 $\phi_-^{n+1}\to0$，主导项是 $\phi_+^{n+1}/\sqrt5$。长度 $n$ 上可用的消息数约为 $\phi_+^n$，若把消息看作等可能的编码，能区分的消息数的对数就是可传信息量，故每单位时间 $\log_2 f_n/n\to\log_2\phi_+\approx0.694$ bit。$\phi_-$ 项只影响低阶修正，不影响指数增长率。

5. 用「数两遍」证明 $f_n=\sum_k\binom{n-k}{k}$。

参考答案：一边，长度为 $n$ 的点划消息数按定义就是 $f_n$。另一边，按划的个数 $k$ 分类：$k$ 个划占 $2k$ 个时间单位，余下 $n-2k$ 个点，符号总数为 $n-k$；在 $n-k$ 个位置中选 $k$ 个放划即可，方案数 $\binom{n-k}{k}$。$k$ 的取值范围是 $0\le k\le\lfloor n/2\rfloor$。两种数法数的是同一个集合，故相等。

6. 从 $B(x)=(1-x^2)/(1-x^2-2x^3)$ 读出递推与初值，并解释为什么 $b_2=0$ 而 $b_0=1$。

参考答案：比较 $B(x)(1-x^2-2x^3)=1-x^2$ 两端 $x^n$ 的系数，得 $b_n-b_{n-2}-2b_{n-3}=0$（$n\ne0,2$），即 $b_n=b_{n-2}+2b_{n-3}$；$n=0$ 给出 $b_0=1$，$n=2$ 给出 $b_2-b_0=-1$，即 $b_2=0$。组合上，$b_0=1$ 是空铺法，而长度为 $2$ 的条带无法用最短长度为 $3$ 的基本块铺成，所以 $b_2=0$；递推在 $n=2$ 处尚未进入「可用」区间，分子中的 $-x^2$ 正是对这一段的修正。

与前后课的关系

上一讲的 Catalan 数用「满二叉树分解」和「Dyck 路径分解」两次得到 $C(x)=1+xC(x)^2$。本讲把同一套语言推到线性递推，得到闭式公式与增长率。

下一讲把生成函数用在 Catalan 数上：先用递推解出 $C(x)=(1-\sqrt{1-4x})/(2x)$，再用二项式定理展开得到 $C_n=\frac{1}{n+1}\binom{2n}{n}$。之后课程转向概率，届时生成函数会以「矩母函数」的形式再次出现。

What this lecture is for

The previous lecture counted Catalan numbers with generating functions. This one turns the method into a translation machine: on one side sit combinatorial objects, on the other formal power series. Union, size-additive concatenation and sequences become addition, multiplication and $1/(1-A)$.

With the machine in hand we attack a classical question: how many dot-and-dash messages of length $n$ are there? The answer is a Fibonacci number. Then we push one step further — how large is the $n$-th Fibonacci number? The generating function yields a closed formula, and the formula yields an information rate.

Timeline

Three operations

Let $a_n$ count the objects of size $n$ and let

$$A(x)=\sum_{n\ge 0}a_nx^n .$$

Disjoint union: add

If $C$ is the disjoint union of $A$ and $B$, then $c_n=a_n+b_n$ and

$$C(x)=A(x)+B(x).$$

Product: multiply

If an object of $C$ is a pair consisting of one $A$-object and one $B$-object whose sizes add, then

$$c_n=\sum_{i=0}^{n}a_i\,b_{n-i}, \qquad C(x)=A(x)B(x).$$

Size additivity is what makes the convolution index $i+(n-i)=n$ line up.

Sequences: invert

Suppose every object in $A$ has size at least $1$. Finite sequences of $A$-objects, including the empty one, have generating function

$$S(x)=1+A(x)+A(x)^2+A(x)^3+\cdots=\frac{1}{1-A(x)} .$$

The leading $1$ is the empty sequence; $A(x)^k$ counts sequences of exactly $k$ objects. Why exclude size $0$? Because a size-zero object could be inserted any number of times without changing the size, so every size would have infinitely many sequences and the coefficients would be meaningless.

For example, with $A=\{0,1\}$ we have $A(x)=2x$ (two strings of length one), so binary strings have generating function

$$S(x)=\frac{1}{1-2x}=1+2x+4x^2+8x^3+\cdots,$$

whose coefficient $2^n$ is the number of binary strings of length $n$.

Dot-and-dash messages: Fibonacci appears

Send messages over a telegraph channel using a dot (one time unit) and a dash (two time units). How many messages last exactly $n$ units?

Enumerating:

• $n=1$: only a dot, $f_1=1$.
• $n=2$: dot-dot or dash, $f_2=2$.
• $n=3$: dot-dot-dot, dot-dash, dash-dot, $f_3=3$.
• $n=4$: five messages; $n=5$: eight.

These are the Fibonacci numbers, and the reason is a single observation: look at the final symbol.

$$f_n=f_{n-1}+f_{n-2}.$$

If the message ends in a dot, the first $n-1$ units form any message; if it ends in a dash, the first $n-2$ units do.

The course uses the convention

$$f_0=1,\quad f_1=1,\quad f_2=2,\quad f_3=3,\quad f_4=5,\dots$$

Here $f_0=1$ is the empty message — sending nothing is one way to send — and this choice keeps later formulas clean. It is shifted by one from the Wikipedia convention $F_0=0,F_1=1$: here $f_n=F_{n+1}$.

Solving the recurrence with generating functions

Setting up the equation

Let $F(x)=\sum_{n\ge0}f_nx^n$. Multiply the recurrence by $x^n$ and sum over $n\ge2$:

$$\sum_{n\ge2}f_nx^n=\sum_{n\ge2}f_{n-1}x^n+\sum_{n\ge2}f_{n-2}x^n .$$

The left side is $F(x)-f_0-f_1x=F(x)-1-x$. The first term on the right is $x\big(F(x)-f_0\big)=x(F(x)-1)$, the second is $x^2F(x)$. Hence

$$F-1-x=x(F-1)+x^2F,$$

so

$$F(x)\,(1-x-x^2)=1, \qquad F(x)=\frac{1}{1-x-x^2}.$$

Partial fractions

Factor the denominator by writing

$$1-x-x^2=(1-\phi_+x)(1-\phi_-x).$$

Comparing coefficients gives $\phi_++\phi_-=1$ and $\phi_+\phi_-=-1$, so

$$\phi_+=\frac{1+\sqrt5}{2},\qquad \phi_-=\frac{1-\sqrt5}{2}.$$

Now set

$$\frac{1}{1-x-x^2}=\frac{A}{1-\phi_+x}+\frac{B}{1-\phi_-x}.$$

The numerator after clearing denominators is $A(1-\phi_-x)+B(1-\phi_+x)$, which must equal $1$ identically. Comparing the constant and linear terms:

$$A+B=1,\qquad A\phi_-+B\phi_+=0 .$$

Substituting $B=1-A$ into the second equation,

$$A\phi_-+(1-A)\phi_+=0 \iff A(\phi_--\phi_+)=-\phi_+ \iff A=\frac{\phi_+}{\phi_+-\phi_-}=\frac{\phi_+}{\sqrt5}.$$

Likewise

$$B=\frac{-\phi_-}{\sqrt5}.$$

The lecture states the sign of $B$ incorrectly on the board; testing $n=0$ shows the negative sign is required.

Binet's formula

Using

$$\frac{1}{1-\phi x}=\sum_{n\ge0}\phi^nx^n,$$

we get

$$F(x)=\frac{1}{\sqrt5}\sum_{n\ge0}\left(\phi_+^{n+1}-\phi_-^{n+1}\right)x^n,$$

that is,

$$f_n=\frac{\phi_+^{n+1}-\phi_-^{n+1}}{\sqrt5}.$$

Check $n=0$: $(\phi_+-\phi_-)/\sqrt5=1$. Check $n=1$: using $\phi_\pm^2=\phi_\pm+1$, the numerator is $\phi_+-\phi_-=\sqrt5$, so $f_1=1$.

Growth rate and information rate

Since $|\phi_-|<1$, the second term decays exponentially and can be ignored:

$$f_n\approx\frac{\phi_+^{\,n+1}}{\sqrt5}.$$

With $\phi_+=(1+\sqrt5)/2\approx1.618$, the number of messages of length $n$ grows like $\phi_+^n$. Hence the information carried per unit time is

$$\frac{\log_2 f_n}{n}\to\log_2\phi_+\approx0.694\ \text{bits per time unit}.$$

The constant factor $1/\sqrt5$ and the shift $n+1$ affect only lower-order terms. This is the seed of the later information-theory unit: channel capacity is governed by the logarithm of the growth rate.

A tiling problem: the sequence formula at work

Tile a $2\times n$ strip with two shapes of tiles that may be reflected. Following the lecture, first count indecomposable pieces $a_n$: tilings that cannot be split by a vertical line into two separately tileable strips.

Checking small cases gives

$$a_3=2,\qquad a_5=2,\qquad a_7=2,\qquad a_{2k}=0,$$

so indecomposable pieces occur only at odd lengths $3,5,7,\dots$, with exactly two at each length (mirror images). Therefore

$$A(x)=2x^3+2x^5+2x^7+\cdots=\frac{2x^3}{1-x^2}.$$

Every tiling is a sequence of indecomposable pieces, so

$$B(x)=\frac{1}{1-A(x)} =\frac{1}{1-\dfrac{2x^3}{1-x^2}} =\frac{1-x^2}{1-x^2-2x^3}.$$

Expanding:

$$B(x)=1+2x^3+2x^5+4x^6+2x^7+8x^8+\cdots$$

A strip of length $6$, for instance, is two length-$3$ pieces side by side, with $2\times2=4$ choices.

Reading the recurrence off the generating function

The denominator $1-x^2-2x^3$ encodes the recurrence; the numerator encodes initial conditions. Comparing coefficients in $B(x)(1-x^2-2x^3)=1-x^2$ gives

$$b_n-b_{n-2}-2b_{n-3}= \begin{cases} 1,&n=0,\\ -1,&n=2,\\ 0,&\text{otherwise}. \end{cases}$$

After the initial terms,

$$b_n=b_{n-2}+2b_{n-3}.$$

This also explains the curious value $b_2=0$. Applied at $n=2$, the recurrence would give $b_2=b_0+2b_{-1}=1$, but the numerator contributes a $-1$ at $x^2$ that corrects it. Combinatorially, the empty tiling cannot be extended to length $2$ by adding an indecomposable piece, since the shortest such piece has length $3$.

The recurrence is also visible directly: any nonempty tiling either ends with a vertical piece of length $2$ ($b_{n-2}$ ways) or with a length-$3$ indecomposable piece in one of its two orientations ($2b_{n-3}$ ways).

Pascal's triangle and Fibonacci numbers

Consider the two-variable generating function

$$P(x,y)=\sum_{a,b\ge0}\binom{a+b}{a}x^ay^b .$$

Sum first along a row: for fixed $n=a+b$,

$$\sum_{a=0}^{n}\binom{n}{a}x^ay^{n-a}=(x+y)^n .$$

Summing over rows,

$$P(x,y)=\sum_{n\ge0}(x+y)^n=\frac{1}{1-x-y}.$$

Diagonals

Shallow diagonal sums give Fibonacci numbers:

$$1+1=2,\qquad 1+3+1=5,\qquad 1+6+5+1=13,\dots$$

The reason: substitute $x=z^2,\ y=z$. Then $x^ay^b=z^{2a+b}$, so

$$P(z^2,z)=\frac{1}{1-z-z^2}=F(z).$$

In words, restricting the Pascal generating function to this parabola produces the Fibonacci generating function; the coefficient of $z^n$ is $f_n$. Expanding yields

$$f_n=\sum_{k\ge0}\binom{n-k}{k}.$$

Check $n=5$: $\binom50+\binom41+\binom32=1+4+3=8=f_5$.

A double-counting proof

The same identity can be proved without generating functions.

A dot-and-dash message of length $n$ is one of $f_n$ objects. Count them by the number of dashes $k$. Each dash occupies two time units, so with $k$ dashes the remaining $n-2k$ units are dots, and the number of symbols is

$$k+(n-2k)=n-k .$$

Choose the $k$ positions of the dashes among $n-k$ slots; the rest are dots. This gives $\binom{n-k}{k}$ messages, and summing over $k$:

$$f_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}.$$

Two independent routes meet at the same identity — a typical sanity check in combinatorics.

What this lecture establishes

• Three operations: disjoint union $\to$ add; size-additive product $\to$ multiply; sequences $\to 1/(1-A(x))$, with no size-zero objects.
• Dot-and-dash counts satisfy $f_n=f_{n-1}+f_{n-2}$ with $f_0=1$, and $F(x)=1/(1-x-x^2)$.
• Partial fractions give Binet: $f_n=(\phi_+^{n+1}-\phi_-^{n+1})/\sqrt5$.
• The growth rate is $\phi_+$, giving $\log_2\phi_+\approx0.694$ bits per time unit.
• The tiling generating function is $(1-x^2)/(1-x^2-2x^3)$, i.e. $b_n=b_{n-2}+2b_{n-3}$.
• Pascal's triangle has generating function $1/(1-x-y)$; setting $x=z^2,y=z$ gives Fibonacci.
• The identity $f_n=\sum_k\binom{n-k}{k}$ has both a generating-function proof and a double-counting proof.

Comprehension check

1. Why is the generating function for finite sequences $1/(1-A(x))$? Why must $A$ contain no object of size zero?

Reference answer: A sequence $(\alpha_1,\dots,\alpha_k)$ has size equal to the sum of its parts. If all objects have size at least $1$, a sequence of size $n$ has length at most $n$, and the coefficient of $x^n$ in $A(x)^k$ counts the ways to choose $k$ objects whose sizes sum to $n$. Summing over $k$ gives $\sum_{k\ge0}A(x)^k=1/(1-A(x))$. If a size-zero object existed, it could be inserted arbitrarily often without changing the size, so every size would have infinitely many sequences and the coefficients would diverge.

2. Why does the lecture take $f_0=1$? What happens with the convention $F_0=0,F_1=1$?

Reference answer: $f_0=1$ counts the empty message — sending nothing is one way to send — and it makes the recurrence hold from $n=2$ with the clean equation $F(x)(1-x-x^2)=1$. With $F_0=0,F_1=1$ we have $F_n=f_{n-1}$, so the generating function becomes $xF(x)=x/(1-x-x^2)$: same denominator, numerator multiplied by $x$.

3. Solve for $A$ and $B$ in the partial fractions, and explain why $B$ carries a negative sign.

Reference answer: From $A+B=1$ and $A\phi_-+B\phi_+=0$, eliminate $B$:

$$A\phi_-+(1-A)\phi_+=0\Longrightarrow A(\phi_--\phi_+)=-\phi_+ \Longrightarrow A=\frac{\phi_+}{\sqrt5}.$$

Then $B=1-A=(\sqrt5-\phi_+)/\sqrt5$, and since $\sqrt5=\phi_+-\phi_-$, $B=-\phi_-/\sqrt5$. The sign must be negative: $\phi_-<0$, and with a plus sign $A+B=(\phi_++\phi_-)/\sqrt5=1/\sqrt5\ne1$, contradicting $f_0=1$.

4. Why is the growth rate $\phi_+$ rather than $\phi_-$? What does it say about bits per time unit?

Reference answer: $f_n=(\phi_+^{n+1}-\phi_-^{n+1})/\sqrt5$ and $|\phi_-|\approx0.618<1$, so $\phi_-^{n+1}\to0$ and the dominant term is $\phi_+^{n+1}/\sqrt5$. The number of messages of length $n$ is about $\phi_+^n$; the logarithm of the number of distinguishable messages is the information carried, so per unit time it is $\log_2 f_n/n\to\log_2\phi_+\approx0.694$ bits. The $\phi_-$ term only corrects lower-order behaviour.

5. Prove $f_n=\sum_k\binom{n-k}{k}$ by counting the same set two ways.

Reference answer: On one hand, the number of dot-and-dash messages of length $n$ is $f_n$ by definition. On the other hand, classify by the number of dashes $k$: the dashes occupy $2k$ units, the remaining $n-2k$ units are dots, so there are $n-k$ symbols; choosing which $k$ of them are dashes gives $\binom{n-k}{k}$ messages. Summing over $0\le k\le\lfloor n/2\rfloor$ counts the same set, so the two expressions are equal.

6. Read off the recurrence and initial values from $B(x)=(1-x^2)/(1-x^2-2x^3)$, and explain why $b_2=0$ while $b_0=1$.

Reference answer: Comparing coefficients in $B(x)(1-x^2-2x^3)=1-x^2$ gives $b_n-b_{n-2}-2b_{n-3}=0$ for $n\ne0,2$, i.e. $b_n=b_{n-2}+2b_{n-3}$; at $n=0$, $b_0=1$; at $n=2$, $b_2-b_0=-1$, so $b_2=0$. Combinatorially $b_0=1$ is the empty tiling, while a strip of length $2$ cannot be tiled by pieces of length at least $3$, hence $b_2=0$; the numerator term $-x^2$ records exactly this correction.

Relation to neighbouring lectures

The previous lecture obtained $C(x)=1+xC(x)^2$ twice for Catalan numbers, once by decomposing full binary trees and once by decomposing Dyck paths. This lecture pushes the same language to linear recurrences, extracting closed formulas and growth rates.

The next lecture applies generating functions to Catalan numbers: solving the recurrence gives $C(x)=(1-\sqrt{1-4x})/(2x)$, and the binomial theorem turns it into $C_n=\frac{1}{n+1}\binom{2n}{n}$. After that the course turns to probability, where generating functions reappear as moment-generating functions.