線性代數/主題：線性遞推/解

解

問題 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$。) 如果每秒鐘移動一個圓盤，漢諾塔的僧侶要多少年才能完成這項工作？