线性代数/主题：线性递推/解

解

问题 1

求解每个齐次线性递推关系。

1. $f(n+1)=5f(n)-6f(n-1)$
2. $f(n+1)=4f(n)$
3. $f(n+1)=6f(n)+7f(n-1)+6f(n-2)$

答案

1. 我们将关系用矩阵形式表示。

   ${\begin{pmatrix}5&-6\\1&0\end{pmatrix}}{\begin{pmatrix}f(n)\\f(n-1)\end{pmatrix}}={\begin{pmatrix}f(n+1)\\f(n)\end{pmatrix}}$

   矩阵的特征方程

   ${\begin{vmatrix}5-\lambda &-6\\1&-\lambda \end{vmatrix}}=\lambda ^{2}-5\lambda +6$

   的根为$2$ 和 $3$。任何形式为$f(n)=c_{1}2^{n}+c_{2}3^{n}$ 的函数满足该递推关系。
2. 这与前面的部分类似，但更简单。该关系的矩阵表达式为

   ${\begin{pmatrix}4\end{pmatrix}}{\begin{pmatrix}f(n)\end{pmatrix}}={\begin{pmatrix}f(n+1)\end{pmatrix}}$

   而矩阵的特征方程

   ${\begin{vmatrix}4-\lambda \end{vmatrix}}=4-\lambda$

   只有一个根$4$。任何形式为$f(n)=c4^{n}$ 的函数满足该递推关系。
3. 用矩阵形式表示该关系

   ${\begin{pmatrix}6&7&6\\1&0&0\\0&1&0\end{pmatrix}}{\begin{pmatrix}f(n)\\f(n-1)\\f(n-2)\end{pmatrix}}={\begin{pmatrix}f(n+1)\\f(n)\\f(n-1)\end{pmatrix}}$

   给出这个特征方程。

   ${\begin{vmatrix}6-\lambda &7&6\\1&-\lambda &0\\0&1&-\lambda \end{vmatrix}}=-\lambda ^{3}+6\lambda ^{2}+7\lambda +6$

问题 2

给出一个公式来表示先前练习的关系，并附上这些初始条件。

1. $f(0)=1$, $f(1)=1$
2. $f(0)=0$, $f(1)=1$
3. $f(0)=1$, $f(1)=1$, $f(2)=3$.

问题 3

检查给定的$S$和$\mathbb {R} ^{k}$之间的同构是否是一个线性映射。上面已经论证过这个映射是一对一的。它的逆是什么？

问题 4

证明矩阵的特征方程如上所述，即与该关系相关的多项式。（提示：沿最后一列展开，并使用归纳法。）

问题 5

给定一个齐次线性递推关系$f(n+1)=a_{n}f(n)+\dots +a_{n-k}f(n-k)$，令$r_{1}$，…，$r_{k}$是相关多项式的根。

1. 证明每个函数$f_{r_{i}}(n)=r_{k}^{n}$ 满足递归关系（不包括初始条件）。
2. 证明没有$r_{i}$ 是$0$。
3. 证明集合$\{f_{r_{1}},\dots ,f_{r_{k}}\}$ 是线性无关的。

问题 6

(这指的是下面计算机代码中给出的值 $T(64)=18,446,744,073,709,551,615$。) 如果每秒钟移动一个圆盘，汉诺塔的僧侣要多少年才能完成这项工作？