本文为知乎文章关于线性代数的应用，一道还算有意思的题的镜像备份，由于WordPress与
知乎所支持的markdown语法并不完全相同，原始链接可能会有更好的体验。

我们知道, 一棵二叉树 (Binary tree) 如果按照左子树的关键值均小于根结点的关键值, 右子树的关键值均大于根节点的关键值的顺序构造的话. 那么这棵二叉树便是一棵二叉排序树 (BST) . 而如果我们再做如下限制: 二叉排序树中任一结点的左右子树高度差不超过1, 那么我们称这种二叉排序树为平衡二叉树 (AVL) .

我们显然就能得出如下结论, 平衡二叉树的高度为1时, 其最少结点数为1; 高度为2时, 其最少结点为2.

我们同时还能得出以下不太显而易见的结论: 如果我们用 $a_h$ 表示深度为 $h$ 的二叉平衡树中的最少结点, 则我们有如下递推关系式:
$$ah = a{h-1} + a_{h-2} + 1 \qquad h > 2\ a_1 = 1; a_2 = 2$$

好了, 以上是引子, 接下去的才是本文的问题: 我们该如何求出 $a_h$ 的通项公式呢?

问题十分跳跃, 本文不是数据结构的文章, 本文是一篇关于线性代数应用的文章, 虽然这个应用场景一般情况也不会遇到, 但这的的确确可以看作是线性代数的一个微小的应用场景.

我们可以这么做, 将 $(ah , a{h-1})^\mathrm{T}$ 看作一个向量, 这样根据矩阵乘法的运算法则, 我们就能得到如下等式:
$$\begin{pmatrix} a{h} \ a{h-1} \ \end{pmatrix} =
\begin{pmatrix}
1 & 1 \
1 & 0 \
\end{pmatrix}
\begin{pmatrix} a{h-1} \ a{h-2} \ \end{pmatrix} +
\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\tag{1}
$$

上式其实就已经是本文的核心了, 本文接下去的内容完全就是围绕着解这个方程而展开的了.

在继续解这个方程之前还是得先说一下我们的思路, 毕竟学习主要学习的是思路. 其实思路很简单, 这个递推关系式的形式很像斐波那契数列 (Fibonacci sequence) $Fn = F{n-1}+F_{n-2}$ , 而我在几个月前又正好刷到过这么一篇关于斐波那契数列通项公式的推导过程的文章, 那篇文章里用了好几种方法推导斐波那契数列的通项公式, 包括且不限于矩阵法与级数法. 只是级数法我忘了怎么推的了, 若是我还记得的话可能本文就变成高数的应用了...

当然, 这么解释显然是种很敷衍的做法, 但更为深层次的原因我也说不出啊, 毕竟本人也不过是个底边考研人啊, 对这种东西的理解不比各位多到哪里去啊...

不过我个人理解吧, 这可能是因为矩阵的存在可以使我们将多个数字作为一个数组(向量)整体进行计算操作. 我们的递推关系式是一个关于前两项的关系式, 通过矩阵我们可以实现在初等数学中难以实现的同时对多个数字进行操作. 其次还有一部分原因是我们的递推公式的存在, 这使得我们的数列自身是递归定义的, 递归定义使用定义对象为自己下定义, 这往往会预示着一种自相似性, 我们接下去马上就会看到了.

我们继续解 $(1)$ 式, 由于我们的数列是递归定义的, 所以我们显然会有:
$$\begin{pmatrix} a{h-1} \ a{h-2} \ \end{pmatrix} =
\begin{pmatrix}
1 & 1 \
1 & 0 \
\end{pmatrix}
\begin{pmatrix} a{h-2} \ a{h-3} \ \end{pmatrix} +
\begin{pmatrix} 1 \ 0 \ \end{pmatrix}$$

回代到 $(1)$ 式:
$$\begin{align}
\begin{pmatrix} a{h} \ a{h-1} \ \end{pmatrix} &=
\begin{pmatrix}
1 & 1 \
1 & 0 \
\end{pmatrix}
\begin{bmatrix}
\begin{pmatrix}
1 & 1 \
1 & 0 \
\end{pmatrix}
\begin{pmatrix} a{h-2} \ a{h-3} \ \end{pmatrix} +
\begin{pmatrix} 1 \ 0 \ \end{pmatrix}
\end{bmatrix} +
\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=\begin{pmatrix}
1 & 1 \
1 & 0 \
\end{pmatrix}^2
\begin{pmatrix} a{h-2} \ a{h-3} \ \end{pmatrix}
+\begin{pmatrix}
1 & 1 \
1 & 0 \
\end{pmatrix}\begin{pmatrix} 1 \ 0 \ \end{pmatrix}+
\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=A^2\begin{pmatrix} a{h-2} \ a{h-3} \ \end{pmatrix}+ (A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}
\end{align}\tag{2}$$

在上式中, 我们记$\begin{pmatrix}1 & 1 \ 1 & 0 \ \end{pmatrix} = A, \begin{pmatrix}1 & 0 \ 0 & 1 \ \end{pmatrix} = I$. (在接下去的内容中, 我们依旧会使用这里的记号)

我们继续对 $(2)$ 式进行递归展开, 会有:
$$\begin{align}
\begin{pmatrix} a{h} \ a{h-1} \ \end{pmatrix} &=
A^2\begin{pmatrix} a{h-2} \ a{h-3} \ \end{pmatrix}+ (A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&= A^3\begin{pmatrix} a{h-3} \ a{h-4} \ \end{pmatrix} + (A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix} \
&= A^4\begin{pmatrix} a{h-4} \ a{h-5} \ \end{pmatrix} + (A^3+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&= ...\
&=A^{h-2} \begin{pmatrix} a{2} \ a{1} \ \end{pmatrix} + (A^{h-3}+A^{h-4}+...+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=A^{h-2} \begin{pmatrix} 2 \ 1 \ \end{pmatrix} + (A^{h-3}+A^{h-4}+...+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}
\end{align} \tag{3}$$

其实到此为止已经可以了, 但, 明眼人都能看出来我们马上就能凑出一个等比数列了, 那两个列向量实在碍眼, 我们仔细观察我们最开始的递推关系式, 其实我们可以另添一个 $a_0 = 0$ . 添加 $a_0$ 显然是合理的, 无论是从计算便利的角度来说还是从初始二叉平衡树的定义上来说都是十分合理的.

这样我们就能得出:
$$\begin{align}
\begin{pmatrix} a{h} \ a{h-1} \ \end{pmatrix} &=
A^{h-2} \begin{pmatrix} a{2} \ a{1} \ \end{pmatrix} + (A^{h-3}+A^{h-4}+...+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=A^{h-1} \begin{pmatrix} a_1 \ a_0 \ \end{pmatrix} + (A^{h-2}+A^{h-3}+...+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=(A^{h-1}+A^{h-2}+A^{h-3}+...+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}
\end{align} \tag{4}$$

都已经做到这里了, 我们接下去该做啥应该都能看出来了吧, $A$ 是实对称矩阵, 给它相似对角化啊!

我们知道 $A$ 一定可以被相似对角化, $P^{-1}AP=\Lambda$ . 我们根据特征值与特征向量的定义: $A\alpha = \lambda \alpha$, 移项后可得 $$(A-\lambda I)\alpha = 0\alpha\tag{5.1}$$

这个式子等价于 $$|A-\lambda I|=0\tag{5.2}$$

由此我们便可通过行列式算出矩阵 $A$ 的特征多项式: $\lambda^2-\lambda-1=0$, 计算可得特征值为:
$$\begin{cases}\lambda_1=\frac{1+\sqrt{5}}{2}\\lambda_2 = \frac{1-\sqrt{5}}{2}\end{cases}\tag{6}$$

这如果还记得中学数学的话就会发现两个特征值其实就是黄金分割比例 (或者说与黄金分割比例有关) , 如果你知道斐波那契数列的通项公式的话就会知道, 这两个特征值其实也是斐波那契数列的通项公式的特征值.

计算出特征值后我们便应该计算特征向量, 从定义的方式计算特征向量是比较繁琐的, 我们接下去用个比较取巧的方式进行计算:

根据式 $(5.2)$ 的行列式等于 $0$ ,我们其实可以知道 $A-\lambda I$ 一定是不满秩的, 而这个矩阵很显然又不可能是 $O$ 矩阵, 故这个矩阵的秩只能是 $1$ ,即 $\mathrm{r}(A-\lambda I) = 1$.

这个事实告诉我们矩阵 $A -\lambda I$ 一定会行等价于 $\begin{pmatrix}a{\cdot1} & a{\cdot2} \0 & 0 \\end{pmatrix}=A\lambda'$ , 我们又根据式 $(5.1)$ 可以得到 $A'\lambda \alpha = 0\alpha$ 其中 $\alpha$ 就是 $A$ 的特征向量, 这是因为如果我们把前面的式子看作是个齐次线性方程组的话, 由于 $A-\lambda I$ 与 $A'_\lambda$ 是行等价的, 所以这两个方程组是同解的, 其解就是 $\alpha$ .

如此一来, 我们将求解特征向量的工作给转变成了求解齐次线性方程组的一个特解的工作了, 也就是解这么个方程组:
$$\begin{cases}a_{\cdot1}\alpha1+a{\cdot2}\alpha_2 &= 0\0\alpha_1+0\alpha2 &= 0\end{cases}$$
其中 $a{\cdot1}, a_{\cdot2}$ 是已知的值, $(\alpha_1, \alpha_2)^\mathrm{T}$ 就是我们要的特征向量. 当然, 这个特征向量只是原方程组中的一个特解, 或者说是一个基础解系.

我们来实践一下吧: $A-\lambda I = \begin{pmatrix}1-\lambda & 1 \1 & -\lambda \\end{pmatrix}$ , 根据上文的分析, 我们可以直接得出结论:
$$A-\lambda I \cong \begin{pmatrix}0 & 0 \1 & -\lambda \\end{pmatrix}$$

对上式求基础解系, 也就是求:
$$x_1-\lambda x_2 = 0$$

我们很容易就能得出我们所需的基础解系(特征向量):
$$\begin{cases}\xi_1 = (\lambda_1, 1)^\mathrm{T}\\xi_2 = (\lambda_2, 1)^\mathrm{T}\end{cases}\tag{7}$$

我们令 $P=\begin{pmatrix}\lambda_1 & \lambda_2 \1 & 1 \\end{pmatrix}$ , 根据二阶矩阵逆矩阵的公式, 我们很快能得出 $P^{-1}=\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}1 & -\lambda_2 \-1 & \lambda_1 \\end{pmatrix}$ .然后我们有:
$$P^{-1}AP=\Lambda=\begin{pmatrix}\lambda_1 & 0 \0 & \lambda_2 \\end{pmatrix}\tag{8.1}$$
$$P\Lambda P^{-1}=A\tag{8.2}$$

由此, 式(4)可以变成:
$$\begin{align}
\begin{pmatrix} a{h} \ a{h-1} \ \end{pmatrix}
&=(A^{h-1}+A^{h-2}+A^{h-3}+...+A^2+A+I)\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=P(\Lambda^{h-1}+\Lambda^{h-2}+...+\Lambda^2+\Lambda+I)P^{-1}\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=P\begin{pmatrix} \lambda_1^{h-1}+...+\lambda_1+1 & 0\ 0 & \lambda_2^{h-1}+...+\lambda_2+1\ \end{pmatrix}P^{-1}\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=P\begin{pmatrix} \frac{1-\lambda_1^h}{1-\lambda_1} & 0 \ 0 & \frac{1-\lambda_2^h}{1-\lambda_2} \ \end{pmatrix}P^{-1}\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix} \lambda_1 & \lambda_2 \ 1 & 1 \ \end{pmatrix}\begin{pmatrix} \frac{1-\lambda_1^h}{1-\lambda_1} & 0 \ 0 & \frac{1-\lambda_2^h}{1-\lambda_2} \ \end{pmatrix}\begin{pmatrix} 1 & -\lambda_2 \ -1 & \lambda_1 \ \end{pmatrix}\begin{pmatrix} 1 \ 0 \ \end{pmatrix}\
&=\frac{1}{\lambda_1-\lambda_2}
\begin{pmatrix} \frac{\lambda_1(1-\lambda_1^h)}{1-\lambda_1} & \frac{\lambda_2(1-\lambda_2^h)}{1-\lambda_2} \ ... & ... \ \end{pmatrix}
\begin{pmatrix} 1 \ -1 \ \end{pmatrix}
\end{align}\tag{9}$$

最后, 我们便得到了我们要的通项公式:
$$\begin{align}
a_h &= \frac{1}{\lambda_1 - \lambda_2}[\frac{\lambda_1(1-\lambda_1^h)}{1-\lambda_1}-\frac{\lambda_2(1-\lambda_2^h)}{1-\lambda_2}]\
&= \frac{\lambda_1 \lambda_2}{\lambda_1 - \lambda_2}[\frac{1-\lambda_1^h}{\lambda_2(1-\lambda_1)}-\frac{1-\lambda_2^h}{\lambda_1(1-\lambda_2)}]
\end{align}\tag{10}$$

上式中的 $\lambda$ 见式 (6) .

最后我们来留个课后作业吧, 其实本来想留斐波那契数列的通项公式证明作为作业, 但转念一想, 我在本文中已经提到几次斐波那契数列了, 读者看到后应该也会搜搜看看, 那这么一来这课后作业也就留的没有意义了. 我也只能退而求其次, 给读者带来了道相对比较简单的题目.

汉诺塔 (Hanoi) 问题也是一个经典的递归问题, 它是说:

假设有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动?

这个问题之所以是个递归问题, 是因为我们可以将这个问题抽象成三步.

第一步是将A柱子上除最底下圆盘外的n-1个圆盘移动到C柱子上.
第二步是将A住子上最底下的圆盘移动到B柱子上.
第三步是将C柱子上的n-1个圆盘移动到B柱子上.

如此一来我们便完成了把A柱子上所有圆盘均移动到B柱上的操作.

显然的是, 假设只有一个圆盘的情况下, 我们只需要移动一次就可以将它从A柱子移动到B柱子了.

假设n个圆盘的汉诺塔问题的移动次数为 $H_n$ , 则根据我们上面的分析, 有:

$$Hn=\begin{cases}2H{n-1}+1\quad &\text{if n > 1}\ 1 &\text{if n = 1}\end{cases}.$$

请根据以上递推关系式求出汉诺塔问题最少移动次数 $H_n$ 的通项公式.

P.S. 请最好使用本文中介绍的矩阵法计算, 虽然我知道这题用矩阵法做反而是把简单问题复杂化了.

最后, 感谢各位能读到这里, 再次感谢.