# 遞迴關係式

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}$

from lingeo import random_int_list

## Main idea

Consider a sequence that satisfies
$$
\begin{aligned}
a_{n+2} &= c_1a_{n+1} + c_2a_n, \\
a_0 &= p,\quad a_1 = q,
\end{aligned}
$$
where $c_1,c_2,p,q$ are some given values.
The first line is called a **recurrence relation**, while
the second line is called the **initial conditions**.

A famous example is the **Fibonacci sequence** defined by
$$
\begin{aligned}
a_{n+2} &= a_{n+1} + a_n, \\
a_0 &= 1,\quad a_1 = 1.
\end{aligned}
$$

Such a relation can be written as
$$
\begin{bmatrix} a_{n+1} \\ a_{n+2} \end{bmatrix}
=
\begin{bmatrix}
0 & 1 \\
c_2 & c_1
\end{bmatrix}
\begin{bmatrix} a_{n} \\ a_{n+1} \end{bmatrix}.
$$

That is, by setting $\bv_n = \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}$,
there is a matrix $A$ such that
$$
\begin{aligned}
\bv_{n+1} &= A\bv_n, \\
\bv_0 &= \begin{bmatrix} p \\ q \end{bmatrix}.
\end{aligned}
$$
As long as we have a formulat for $A^n$, then we know $\bv_n = A^n\bv_0$.

## Side stories

- Fibonacci sequence
- $\mathbb{R}^\mathbb{Z}$ and the advancement operator

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False

while True:
    c1,c2 = random_int_list(2, 3)
    if c1 != 0 and c2 != 0:
        break
        
p,q = random_int_list(2, 3)

pretty_print(LatexExpr("a_{n+2} = (%s)a_{n+1} + (%s)a_{n}"%(c1,c2)))
pretty_print(LatexExpr("a_0 = %s"%p))
pretty_print(LatexExpr("a_1 = %s"%q))

A = matrix([[0,1],[c2,c1]])
pretty_print(LatexExpr("A^5 ="), A^5)

if print_ans:
    anp0,anp1 = p,q
    for k in range(2,6):
        anp2 = c2 * anp0 + c1 * anp1
        pretty_print(LatexExpr("a_{%s} = %s"%(k,anp2)))
        anp0 = anp1
        anp1 = anp2

藉由 `seed = 0` 可得，
$a_{n+2} = (-3)a_{n+1} + (3)a_{n}$
$a_0 = 1 , a_1 = 2$
$A^5 = \begin{bmatrix}
-135 & 171 \\
513 & -648
\end{bmatrix}$
##### Exercise 1(a)

依照定義依序求出 $a_2,\ldots, a_5$。

$Ans:$
依照定義可得，
$a_2 = (-3)a_{1} + (3)a_{0} = -3$，
$a_3 = (-3)a_{2} + (3)a_{1} = 15$，
$a_4 = (-3)a_{3} + (3)a_{2} = -54$，
$a_5 = (-3)a_{4} + (3)a_{3} = 207$。

##### Exercise 1(b)

令 $\bv_n = \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}$，
找到一個矩陣 $A$ 使得 $\bv_{n+1} = A\bv_n$。

:::warning

- [x] 另 --> 令
:::

$Ans:$
$$\bv_0 = \begin{bmatrix} a_0 \\ a_{1} \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$以此可以同樣情況得， $$\bv_1 = \begin{bmatrix} 2 \\ -3 \end{bmatrix} , \bv_2 = \begin{bmatrix} -3 \\ 15 \end{bmatrix} , \bv_3 = \begin{bmatrix} 15 \\ -54 \end{bmatrix} , \bv_4 = \begin{bmatrix} -54 \\ 207 \end{bmatrix}$$
令一個矩陣 $A = \begin{bmatrix} 0 & 1 \\ 3 & -3 \end{bmatrix}$ ，將矩陣 $A$ 帶入 $\bv_{n+1} = A\bv_n$ ，依序驗算可得， $$\bv_{2} = A\bv_1 = \begin{bmatrix} -3 \\ 15 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 3 & -3 \end{bmatrix} \begin{bmatrix} 2 \\ -3 \end{bmatrix} $$ $$\bv_{3} = A\bv_2 = \begin{bmatrix} 15 \\ -54 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 3 & -3 \end{bmatrix} \begin{bmatrix} -3 \\ 15 \end{bmatrix} $$ $$\bv_{4} = A\bv_3 = \begin{bmatrix} -54 \\ 207 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 3 & -3 \end{bmatrix} \begin{bmatrix} 15 \\ -54 \end{bmatrix}
$$
所以可得到矩陣 $A$ 為答案。

:::warning
驗算三個 $n$ 都對其實沒辦法說明 $A$ 就是對的；不過意思到了，沒關係。
:::

##### Exercise 1(c)

利用題目給的 $A^5$，求出 $a_5$。
比較答案是否和前面算的一樣。

:::warning

- [x] 最後那個向量裡面應該是 $a$ 不是 $\bv$。
:::

$Ans:$
$a_5 = 207$ , $A^5 = \begin{bmatrix}
-135 & 171 \\
513 & -648
\end{bmatrix}$ 。
將 $A^5$ 帶入 $A^5 \bv_0 = \begin{bmatrix}
-135 & 171 \\
513 & -648
\end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 207 \\ -883 \end{bmatrix} = \begin{bmatrix} a_5 \\ a_6 \end{bmatrix}$ 。
比較發現此次答案與前面答案一樣。
## Exercises

##### Exercise 2

解以下遞迴關係式中 $a_n$ 的一般式。

##### Exercise 2(a)

已知
$$
\begin{bmatrix}
2 & 0 \\
0 & 3
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
2 & 3
\end{bmatrix}^{-1}
\begin{bmatrix}
0 & 1 \\
-6 & 5
\end{bmatrix}
\begin{bmatrix}
1 & 1 \\
2 & 3
\end{bmatrix}.
$$
考慮遞迴關係式 $a_{n+2} = 5a_{n+1} - 6a_n$、$a_0 = a_1 = 1$。

$Ans:$
用 $D = Q^{-1} A Q$ 的形式來看, 可知 $D$ 為 $A$ 經由對角化而來的矩陣, 且 $A = Q D Q^{-1}$, 則 $A^n = Q D^n Q^{-1}$。
又由遞迴關係式可知 $\bv_2 = A \bv_1$, 推得 $\bv_n = A^{n} \bv_0$, 其中 $\bv_n = \begin{bmatrix} a_{n} \\ a_{n+1} \end{bmatrix}$, 所以只要找出 $\bv_n$ 的第一項即可。
此題的
$$
A^n =
\begin{bmatrix}
1 & 1 \\
2 & 3
\end{bmatrix}
\begin{bmatrix}
2^n & 0 \\
0 & 3^n
\end{bmatrix}
\begin{bmatrix}
1 & 1 \\
2 & 3
\end{bmatrix}^{-1} =
\begin{bmatrix}
3 \times 2^{n} -2 \times 3^{n} & 3^n - 2^n \\
c_1 & c_2
\end{bmatrix}
$$
且
$$
\bv_0 =
\begin{bmatrix}
1 \\
1
\end{bmatrix}
$$

則 $\bv_n$ 的第一項即為

$$
a_{n}
= 3 \times 2^{n} - 2 \times 3^{n} + 3^{n} - 2^{n}
= 2 \times 2^{n} - 3^{n}.
$$

##### Exercise 2(c)

已知
$$
\begin{bmatrix}
2 & 0 \\
0 & -2
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
2 & -2
\end{bmatrix}^{-1}
\begin{bmatrix}
0 & 1 \\
-4 & 0
\end{bmatrix}
\begin{bmatrix}
1 & 1 \\
2 & -2
\end{bmatrix}.
$$
考慮遞迴關係式 $a_{n+2} = 0a_{n+1} - 4a_n$、$a_0 = a_1 = 1$。

$Ans:$
經計算,
$$
A^{n} =
\begin{bmatrix}
1/2 \times (2^{n} + (-2)^{n}) & 1/4 \times (2^{n} - (-2)^{n}) \\
c_1 & c_2
\end{bmatrix}
$$
且
$$
\bv_0 =
\begin{bmatrix}
1 \\
1
\end{bmatrix}
$$
則
$\bv_n$ 的第一項為
$$
a_{n}
= 1/2 \times (2^{n} + (-2)^{n}) + 1/4 \times (2^{n} - (-2)^{n})
= 3/4 \times 2^{n} + 1/4 \times (-2)^{n}.
$$

##### Exercise 2(d)

已知
$$
\begin{bmatrix}
2 & 1 \\
0 & 2
\end{bmatrix}
=
\begin{bmatrix}
2 & -1 \\
4 & 0
\end{bmatrix}^{-1}
\begin{bmatrix}
0 & 1 \\
-4 & 4
\end{bmatrix}
\begin{bmatrix}
2 & -1 \\
4 & 0
\end{bmatrix}.
$$
考慮遞迴關係式 $a_{n+2} = 4a_{n+1} - 4a_n$、$a_0 = a_1 = 1$。

$Ans:$
經計算,
$$
A^{n} =
\begin{bmatrix}
(1-n) \times 2^{n} & n/2 \times 2^{n} \\
c_1 & c_2
\end{bmatrix}
$$
且
$$
\bv_0 =
\begin{bmatrix}
1 \\
1
\end{bmatrix}
$$
則 $\bv_n$ 的第一項為
$$
a_{n}
= (1-n) \times 2^{n} + n/2 \times 2^{n}
= ((2-n)/2) \times 2^{n}.
$$

##### Exercise 2(e)

已知
$$
\begin{bmatrix}
3 & 1 \\
0 & 3
\end{bmatrix}
=
\begin{bmatrix}
3 & -1 \\
9 & 0
\end{bmatrix}^{-1}
\begin{bmatrix}
0 & 1 \\
-9 & 6
\end{bmatrix}
\begin{bmatrix}
3 & -1 \\
9 & 0
\end{bmatrix}.
$$
考慮遞迴關係式 $a_{n+2} = 6a_{n+1} - 9a_n$、$a_0 = a_1 = 1$。

$Ans:$
經計算,
$$ A^{n} =
\begin{bmatrix}
(1-n) \times 3^{n} & n/3 \times 3^{n} \\
c_1 & c_2
\end{bmatrix}
$$
且
$$
\bv_0 =
\begin{bmatrix}
1 \\
1
\end{bmatrix}
$$
則 $\bv_n$ 的第一項為
$$
a_{n}
= (1-n) \times 3^{n} + n/3 \times 3^{n}
= ((3-2n)/3) \times 3^{n}
$$
##### Exercise 3

已知
$$
\begin{bmatrix}
3 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}^{-1}
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
6 & -11 & 6
\end{bmatrix}
\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}.
$$
考慮遞迴關係式 $a_{n+3} = 6a_{n+2} - 11a_{n+1} + 6a_n$、$a_0 = a_1 = a_2 = 1$。
解 $a_n$ 的一般式。

:::warning

- [x] $V$ --> $A$, $A_n$ --> $\bv_n$；而且你沒有解釋什麼是 $V$ 什麼是 $A_n$
- [x] $V^n \times a_1$ 是矩陣乘數字？
- [x] 最後的一堆等式用 `aligned` 排好
- [x] 最後答案應該是 $a_n = 1$
:::

$Ans:$

因為 遞迴關係式 $a_{n+3} = 6a_{n+2} - 11a_{n+1} + 6a_n$、$a_0 = a_1 = a_2 = 1$。
所以 $a_3 = 6a_2 - 11a_1 + 6a_0$， 也就是 $a_4 = 6\times1 - 11\times1 + 6\times1$。

我們可以將上面的方程式改成以矩陣方式表示，
即為
$a_4 = \begin{bmatrix}
6 & -11 & 6
\end{bmatrix}
\begin{bmatrix}
1\\
1 \\
1 \
\end{bmatrix}$
另外我們知道
$$bv_n=
\begin{bmatrix}
a_{n+1} \\
a_{n+2} \\
a_{n+3} \
\end{bmatrix}
=
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
c_3 & c_2 & c_1 \
\end{bmatrix}
\begin{bmatrix} a_{n} \\ a_{n+1} \\ a_{n+2} \end{bmatrix}.
$$

以及 $\bv_n = A\bv_{n-1} = A^{n} \bv_0$。

其中的 $\begin{bmatrix}
c_3 & c_2 & c_1 \
\end{bmatrix}$
就是 $\begin{bmatrix}
6 & -11 & 6 \
\end{bmatrix}$，
而 $\bv_n$ 也可寫成 $A^{n}\bv_1$。

為了要方便計算 $A^{n}$ ，我們可以將難看的 $A$ 矩陣對角化。

根據題幹，此矩陣可經由下列處理形成對角化矩陣
$$
\begin{bmatrix}
3 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}^{-1}
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
6 & -11 & 6
\end{bmatrix}
\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}.
$$

因此可知，
$$
A^{n} =
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
6 & -11 & 6
\end{bmatrix}^{n}
=
\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
3 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 1
\end{bmatrix}^{n}
\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}^{-1}。
$$

而 $\bv_n = A^{n} \bv_0$ 的第一項。
$$a_n = 3^{n} - 3 \times 2^{n} + 3 - 3/2 \times 3^{n} + 4 \times 2^{n} - 5/2 + 1/2 \times 3^{n} - 2^{n} + 1/2 = 1.
$$

##### Exercise 4

解費波那契數列的 $a_n$ 的一般式。

:::warning

- [x] $V_n$ --> $\bv_n$；而且你沒有解釋什麼是 $V_n$
- [x] $V^n \times a_1$ 是矩陣乘數字？
- [x] 最後的一堆等式用 `aligned` 排好
:::

$ans:$

令
$$
Q=\begin{bmatrix}
1 & 1 \\
\lambda_0 & \lambda_1 \\
\end{bmatrix},
A=\begin{bmatrix}
0 & 1 \\
1 & 1 \\
\end{bmatrix},
\bv_{n} = \begin{bmatrix}
a_{n} \\
a_{n+1} \\
\end{bmatrix}.
$$

其中 $\lambda_0,\lambda_1$ 分別為 $\frac{1-\sqrt{5}}{2},\frac{1+\sqrt{5}}{2}$，且 $A$ 為一可對角化矩陣。那麼，我們可以藉由 $Q$ 跟 $A$ 求得一個對角矩陣，即

$$
Q^{-1} A Q = \begin{bmatrix}
\lambda_0 & 0 \\
0 & \lambda_1
\end{bmatrix} = D.
$$

$\bv_n = A \cdot \bv_{n-1} = A^2 \cdot \bv_{n-2} = \cdots = A^n \cdot \bv_0$。

則
$$
\begin{array}{l}
\bv_{n} &= A^n \bv_0 = Q D^{n} Q^{-1} \bv_0 \\
&= \begin{bmatrix}
1 & 1 \\
\lambda_0 & \lambda_1 \\
\end{bmatrix}
\begin{bmatrix}
\lambda_0^{n} & 0 \\
0 & \lambda_1^{n} \\
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & -1 \\
-\lambda_0 & 1 \\
\end{bmatrix}
\cdot \dfrac{1}{\lambda_1 - \lambda_0} \bv_0
\end{array}
$$

那麼我們就求得

$$
\begin{aligned}
a_n &= \frac{1}{\lambda_1 - \lambda_0} \cdot (\lambda_1^n - \lambda_0^n) \\
&= \sqrt{5} \cdot (\lambda_1^n - \lambda_0^n).
\end{aligned}
$$

##### Exercise 5

以下提供解遞迴關係式的另一種觀點。

##### Exercise 5(a)

考慮集合
$$
\mathbb{R}^\mathbb{Z} = \{( \ldots, a_{-1}, a_0, a_1, \ldots): a_n \in \mathbb{R} \text{ for all }n\in\mathbb{Z}\}.
$$
定義向量加法與數列的純量乘法為
$$
( \ldots, a_{-1}, a_0, a_1, \ldots) + ( \ldots, b_{-1}, b_0, b_1, \ldots) = ( \ldots, a_{-1} + b_{-1}, a_0 + b_0, a_1 + b_1, \ldots),
$$
$$
k( \ldots, a_{-1}, a_0, a_1, \ldots) = ( \ldots, ka_{-1}, ka_0, ka_1, \ldots).
$$
說明 $\mathbb{R}^\mathbb{Z}$ 搭配以上定義的向量加法與純量乘法後，是一個向量空間。

:::warning

- [x] 向量空間要驗證哪些條件？

PS $a_n$ 有 $n$ 組有一個 $1$ 和其他全為 $0$ 的向量 <-- $a_n$ 到底是幾個向量？ $n_{-1}$ 又是什麼
:::

**答:**

要說明 $\mathbb{R}^\mathbb{Z}$ 為一個向量空間，以下條件必須成立:

1. 向量加法的封閉性:
對於任意的
$$(\ldots, a_{-1}, a_0 , a_1, \ldots),(\ldots, b_{-1}, b_0, b_1, \ldots) \in \mathbb{R}.$$
存在
$$(\ldots, a_{-1}, a_0 , a_1, \ldots)+(\ldots, b_{-1}, b_0, b_1, \ldots) \in \mathbb{R}
$$
由於 $a_0,b_0 \in \mathbb{R}$，所以 $a_0+b_0 \in \mathbb{R}$。

2. 向量加法的交換律:
對於任意的
$$(\ldots, a_{-1}, a_0 , a_1, \ldots),(\ldots, b_{-1}, b_0, b_1, \ldots) \in \mathbb{R}$$.
存在
$$(\ldots, a_{-1}, a_0 , a_1, \ldots)+(\ldots, b_{-1}, b_0, b_1, \ldots)
$$
$$=(\ldots, a_{-1} + b_{-1}, a_0 +b_0 , a_1 + b_1, \ldots)
$$
$$=(\ldots, b_{-1} +a_{-1} , b_0 + a_0 , b_1 + a_1 , \ldots)
$$
$$=(\ldots, b_{-1}, b_0, b_1, \ldots) + (\ldots, a_{-1}, a_0 , a_1, \ldots).
$$

3. 向量加法的結合律:
對於任意的
$$(\ldots, a_{-1}, a_0 , a_1, \ldots),(\ldots, b_{-1}, b_0, b_1, \ldots),(\ldots, c_{-1}, c_0 , c_1, \ldots) \in \mathbb{R}$$.
存在
$$(\ldots, a_{-1}, a_0 , a_1, \ldots)+［(\ldots, b_{-1}, b_0, b_1, \ldots)+(\ldots, c_{-1}, c_0 , c_1, \ldots)］
$$
$$=(\ldots, a_{-1}, a_0 , a_1, \ldots)+(\ldots, b_{-1} + c_{-1}, c_0 +c_0 , b_1 + c_1, \ldots)
$$
$$=(\ldots, a_{-1} + b_{-1} + c_{-1}, a_0 +b_0 +c_0 , a_1 + b_1 + c_1, \ldots)
$$
$$=(\ldots, a_{-1} +b_{-1} , a_0 + b_0 , a_1 + b_1 , \ldots)+(\ldots, c_{-1}, c_0 , c_1, \ldots)
$$
$$=［(\ldots, a_{-1}, a_0 , a_1, \ldots)+(\ldots, b_{-1}, b_0, b_1, \ldots)］+(\ldots, c_{-1}, c_0 , c_1, \ldots).
$$

4. 向量加法的單位元素:
存在一個零向量，使得 $\mathbb{0} \in \mathbb{R}$ ，對於任意 $(\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R}$ 都滿足
$$
(\ldots, a_{-1}, a_0 , a_1, \ldots) + \mathbb{0} = (\ldots, a_{-1}, a_0 , a_1, \ldots).
$$

5. 向量加法的反元素:
對於任意 $(\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R}$ ，都存在$(\ldots, b_{-1}, b_0 , b_1, \ldots) \in \mathbb{R}$ ，使得
$$(\ldots, a_{-1}, a_0 , a_1, \ldots)+(\ldots, b_{-1}, b_0, b_1, \ldots) = \mathbb{0}.
$$

6. 純量乘法的封閉性:
對於任意
$$
(\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R} \space \space 且 \space\space k \in \mathbb{R},
$$
$$
k \cdot (\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R}.
$$
也必定成立。

7. 純量乘法的分配律:
(1) 純量乘法對向量加法的分配律:
對於任意
$$
(\ldots, a_{-1}, a_0 , a_1, \ldots),(\ldots, b_{-1}, b_0, b_1, \ldots) \in \mathbb{R} \space \space 且 \space\space k \in \mathbb{R},
$$
$$
k \cdot ［(\ldots, a_{-1}, a_0 , a_1, \ldots)+(\ldots, b_{-1}, b_0, b_1, \ldots)］
$$
$$
=k \cdot (\ldots, a_{-1} + b_{-1}, a_0 +b_0 , a_1 + b_1, \ldots)
$$
$$
=(\ldots, k \cdot a_{-1} +
k \cdot b_{-1}, k \cdot a_0 + k \cdot b_0 , k \cdot a_1 + k \cdot b_1, \ldots)
$$
$$
=(\ldots, k \cdot a_{-1} , k \cdot a_0 , k \cdot a_1 , \ldots)+(\ldots, k \cdot b_{-1}, + k \cdot b_0 , k \cdot b_1, \ldots)
$$
$$
= k \cdot (\ldots, a_{-1}, a_0 , a_1, \ldots)+ k \cdot (\ldots, b_{-1}, b_0, b_1, \ldots).
$$
(2) 向量加法對純量乘法的分配律:
$$
(\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R} \space \space 且 \space\space k_1,k_2 \in \mathbb{R},
$$
$$
(k_1+k_2) \cdot (\ldots, a_{-1}, a_0 , a_1, \ldots)
$$
$$
=(\ldots, (k_1+k_2) \cdot a_{-1}, (k_1+k_2) \cdot a_0 , (k_1+k_2) \cdot a_1, \ldots)
$$
$$
=(\ldots, k_1\cdot a_{-1}+k_2 \cdot a_{-1}, k_1\cdot a_0+k_2 \cdot a_0 , k_1\cdot a_1+k_2 \cdot a_1, \ldots).
$$
$$
=(\ldots, k_1 \cdot a_{-1}, k_1 \cdot a_0 , k_1 \cdot a_1, \ldots)+(\ldots, k_2 \cdot a_{-1}, k_2 \cdot a_0 , k_2 \cdot a_1, \ldots)
$$
$$=k_1 \cdot(\ldots, a_{-1}, a_0 , a_1, \ldots)+k_2 \cdot(\ldots, a_{-1}, a_0 , a_1, \ldots).
$$

8. 純量乘法的交換律:
假設$k,v \in \mathbb{R}$$(\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R}$，
$$k \cdot v \cdot (\ldots, a_{-1}, a_0 , a_1, \ldots)$$
$$=k \cdot (\ldots, v \cdot a_{-1}, v \cdot a_0 , v \cdot a_1, \ldots)$$
$$=(\ldots, k \cdot v \cdot a_{-1}, k \cdot v \cdot a_0 , k \cdot v \cdot a_1, \ldots)
$$
$$=v \cdot (\ldots, k \cdot a_{-1}, k \cdot a_0 , k \cdot a_1, \ldots)$$
$$=v \cdot k \cdot (\ldots, a_{-1}, a_0 , a_1, \ldots).
$$

9. 純量乘法的單位元素:
存在一個 $1 \in \mathbb{R}$ 且 $(\ldots, a_{-1}, a_0 , a_1, \ldots) \in \mathbb{R}$ ，使得

$$
1 \cdot (\ldots, a_{-1}, a_0 , a_1, \ldots)=(\ldots, a_{-1}, a_0 , a_1, \ldots).
$$

##### Exercise 5(b)

定義一個左移函數（advanced operator） $A: \mathbb{R}^\mathbb{Z} \rightarrow \mathbb{R}^\mathbb{Z}$ 為
$$
A(\ldots, a_n, \ldots) = (\ldots, a_{n+1},\ldots).
$$
即將數列 $(\ldots, a_n, \ldots)$ 全部往左移一格。
說明 $A$ 是一個線性函數。

**答:**

利用上題定義的向量加法與數列的純量乘法:
$$
( \ldots, a_{-1}, a_0, a_1, \ldots) + ( \ldots, b_{-1}, b_0, b_1, \ldots) = ( \ldots, a_{-1} + b_{-1}, a_0 + b_0, a_1 + b_1, \ldots),
$$
$$
k( \ldots, a_{-1}, a_0, a_1, \ldots) = ( \ldots, ka_{-1}, ka_0, ka_1, \ldots).
$$

$A$ 是一個線性函數必須滿足加法、乘法先做後做效果一致，這裡先驗證加法先做後做效果一致，得
$$
A( \ldots, a_{-1}, a_0, a_1, \ldots) +A ( \ldots, b_{-1}, b_0, b_1, \ldots)
$$
$$
= ( \ldots, a_0, a_1, a_2, \ldots) + ( \ldots, b_0, b_1, b_2, \ldots)
$$
$$
= ( \ldots, a_0 + b_0, a_1 + b_1, a_2 + b_2, \ldots).
$$

另一方面，得

$$
A[( \ldots, a_{-1}, a_0, a_1, \ldots) + ( \ldots, b_{-1}, b_0, b_1, \ldots)]
$$
$$
= A( \ldots, a_{-1}+b_{-1} , a_0 +b_0 , a_1 + b_1, \ldots)
$$
$$
= ( \ldots, a_0 + b_0, a_1 + b_1, a_2 + b_2, \ldots).
$$

所以先將向量個別送進 $A$ 和先將兩個向量相加所得到的結果是一樣的

再驗證乘法先做後做效果一致，得

$$
k \cdot A( \ldots, a_{-1}, a_0, a_1, \ldots)
$$
$$
=k \cdot ( \ldots, a_0, a_1, a_2, \ldots)
$$
$$
=( \ldots, k \cdot a_0, k \cdot a_1, k \cdot a_2, \ldots).
$$

另一方面，得

$$
A \cdot k( \ldots, a_{-1}, a_0, a_1, \ldots)
$$

$$
A \cdot ( \ldots, k \cdot a_{-1}, k \cdot a_0, k \cdot a_1, \ldots)
$$

$$
=( \ldots, k \cdot a_0, k \cdot a_1, k \cdot a_2, \ldots).
$$

所以先將向量送進 $A$ 再乘 $k$ 和先乘 $k$ 再送進 $A$ 所得到的結果是一樣的。

即可確定 $A$ 為一個線性函數。

##### Exercise 5(c)

說明 $A - 3\idmap$ 也是一個線性函數且
$$
\ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}.
$$

**答:**

$A - 3\idmap$ 是一個線性函數必須滿足加法、乘法先做後做效果一致，這裡先驗證加法先做後做效果一致，得

$$
(A - 3\idmap)( \ldots, a_{-1}, a_0, a_1, \ldots) + (A - 3\idmap) ( \ldots, b_{-1}, b_0, b_1, \ldots)
$$
$$
= [( \ldots, a_0, a_1, a_2, \ldots)-( \ldots, 3a_{-1}, 3a_0, 3a_1, \ldots)] + [( \ldots, b_0, b_1, b_2, \ldots) - ( \ldots, 3b_{-1}, 3b_0, 3b_1, \ldots)]
$$
$$
= ( \ldots, a_0 + b_0, a_1 + b_1, a_2 + b_2, \ldots) - ( \ldots, 3a_{-1}+3b_{-1} , 3a_0 + 3b_0 , 3a_1 + 3b_1, \ldots).
$$

另一方面，得

$$
(A - 3\idmap)[( \ldots, a_{-1}, a_0, a_1, \ldots) + ( \ldots, b_{-1}, b_0, b_1, \ldots)]
$$
$$
= (A - 3\idmap) ( \ldots, a_{-1}+b_{-1} , a_0 +b_0 , a_1 + b_1, \ldots)
$$
$$
= ( \ldots, a_0 + b_0, a_1 + b_1, a_2 + b_2, \ldots) - ( \ldots, 3a_{-1}+3b_{-1} , 3a_0 + 3b_0 , 3a_1 + 3b_1, \ldots).
$$

所以先將向量個別送進 $A - 3\idmap$ 和先將兩個向量相加所得到的結果是一樣的。

再驗證乘法先做後做效果一致，得

$$
k \cdot (A - 3\idmap) ( \ldots, a_{-1}, a_0, a_1, \ldots)
$$
$$
=k \cdot [( \ldots, a_0, a_1, a_2, \ldots) - ( \ldots, 3a_{-1}, 3a_0, 3a_1, \ldots)]
$$
$$
=( \ldots, k \cdot a_0, k \cdot a_1, k \cdot a_2, \ldots) - ( \ldots, k \cdot 3a_{-1}, k \cdot 3a_0, k \cdot 3a_1, \ldots).
$$

另一方面，得

$$
(A - 3\idmap) \cdot k( \ldots, a_{-1}, a_0, a_1, \ldots)
$$
$$
=(A - 3\idmap) \cdot ( \ldots, k \cdot a_{-1}, k \cdot a_0, k \cdot a_1, \ldots)
$$
$$
=( \ldots, k \cdot a_0, k \cdot a_1, k \cdot a_2, \ldots) - ( \ldots, k \cdot 3a_{-1}, k \cdot 3a_0, k \cdot 3a_1, \ldots).
$$

所以先將向量送進 $A - 3\idmap$ 再乘 $k$ 和先乘 $k$ 再送進 $A - 3\idmap$ 所得到的結果是一樣的。

即可確定 $A - 3\idmap$ 為一個線性函數。

接著要解釋的是:
$$
\ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}.
$$

由於 $A - 3\idmap$ 是線性函數，所以可以將其轉換成矩陣的樣子，比較方便說明。

$\idmap$ 是將自己送到自己的矩陣，在同個向量空間就能表示成$I_n$。

:::info
$A - 3\idmap$ 真要寫起來應該是一個「無窮大的矩陣」，但這樣的東西通常不叫作矩陣，其乘法也會有收斂性的問題。
:::

所以 $A - 3\idmap$ 的矩陣形式就可以寫成
$$
\begin{bmatrix}
\cdots& \cdots & \cdots & \cdots & \cdots & \cdots\\
\vdots& -3 & 1 & 0 & 0 & \vdots\\
\vdots& 0 & -3 & 1 & 0 & \vdots\\
\vdots& 0 & 0 & -3 & 1 & \vdots\\
\cdots& \cdots & \cdots & \cdots & \cdots & \cdots
\end{bmatrix}.
$$
其中所有的 $(i,i)$項 都是 $-3$，而 $(i,i+1)$項 都是 $1$。

即
$$(A - 3\idmap) \cdot
\begin{bmatrix}
\vdots\\
a_1\\
a_2\\
a_3\\
\vdots
\end{bmatrix} = 0.
$$
等價於
$$
\begin{cases}
\space\space\space\space\space\space\space\space\space\space\space\vdots\\
-3a_1 + a_2 = 0\\
-3a_2 + a_3 = 0\\
\space\space\space\space\space\space\space\space\space\space\space\vdots
\end{cases}
$$
$$
= \begin{cases}
\space\space\space\space\space\space\space\space\vdots\\
a_2 = 3a_1\\
a_3 = 3a_2 = 3^2a_1\\
\space\space\space\space\space\space\space\space\vdots\\
a_n = 3^na_1
\end{cases}.
$$

再將此矩陣轉換回線性函數，即可得
$$
\ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}.
$$

##### Exercise 5(d)

若 $f$ 和 $g$ 為兩個 $\mathbb{R}^\mathbb{Z} \rightarrow \mathbb{R}^\mathbb{Z}$ 的函數。
我們用 $fg$ 代表函數的合成 $f(g(\cdot))$。
所以 $A^2$ 表示代入 $A$ 函數兩次。

已知 $A^2 - 5A + 6\idmap = (A - 2\idmap)(A - 3\idmap)$。
說明
$$
\ker(A^2 - 5A + 6\idmap) \supseteq \vspan \{(\ldots, 2^n, \ldots), (\ldots, 3^n, \ldots)\}.
$$
（實際上兩個集合相等，但另一個方向證明要花比較多的力氣。）

:::warning

- [ ] 這題只要確認那兩個個向量是零解就好
:::

**答:**

藉由上一題，我們知道 $A - 3\idmap$ 是線性函數，即可類推出 $A - 2\idmap$ 也是線性函數，所以 $(A - 2\idmap)(A - 3\idmap)$ 是線性函數，依題確定 $A^2 - 5A + 6\idmap$ 也是線性函數。

因為是線性函數，所以即可將 $A^2 - 5A + 6\idmap$ 轉換成矩陣形式。

得
$$(A^2 - 5A + 6\idmap) \cdot
\begin{bmatrix}
\vdots\\
a_1\\
a_2\\
a_3\\
\vdots
\end{bmatrix}
=A^2 \cdot
\begin{bmatrix}
\vdots\\
a_1\\
a_2\\
a_3\\
\vdots
\end{bmatrix}
-5A \cdot
\begin{bmatrix}
\vdots\\
a_1\\
a_2\\
a_3\\
\vdots
\end{bmatrix}
+6\idmap \cdot
\begin{bmatrix}
\vdots\\
a_1\\
a_2\\
a_3\\
\vdots
\end{bmatrix}=
\begin{bmatrix}
\vdots\\
a_3\\
a_4\\
a_5\\
\vdots
\end{bmatrix}
-\begin{bmatrix}
\vdots\\
5a_2\\
5a_3\\
5a_4\\
\vdots
\end{bmatrix}
+\begin{bmatrix}
\vdots\\
6a_1\\
6a_2\\
6a_3\\
\vdots
\end{bmatrix}=0.
$$
等價於
$$\begin{bmatrix}
\vdots\\
a_3-5a_2+6a_1\\
a_4-5a_3+6a_2\\
a_5-5a_4+6a_3\\
\vdots
\end{bmatrix}
$$
$$
= \begin{cases}
\space\space\space\space\space\space\space\space\space\space\space\space\space\space\vdots\\
a_3-5a_2+6a_1 = 0\\
a_4-5a_3+6a_2 = 0\\
a_5-5a_4+6a_3 = 0\\
\space\space\space\space\space\space\space\space\space\space\space\space\space\space\vdots
\end{cases}.
$$

將 $a_3-5a_2+6a_1 = 0$ 移項後，得 $a_3 = 5a_2 - 6a_1$。

以矩陣方式呈現即
$$M\cdot
\begin{bmatrix}
a_1\\
a_2
\end{bmatrix}
=\begin{bmatrix}
a_2\\
a_3
\end{bmatrix}.
$$
得
$$M=\begin{bmatrix}
0 & 1\\
5 & -6
\end{bmatrix}.
$$

即
$$\begin{bmatrix}
0 & 1\\
5 & -6
\end{bmatrix}^n
\cdot
\begin{bmatrix}
a_1\\
a_2
\end{bmatrix}
=\begin{bmatrix}
a_{n+1}\\
a_{n+2}
\end{bmatrix}.
$$

由此遞迴關係式可知除了設定的初始項 $a_1$ 和 $a_2$ ， 其他項的值都可以由 $c_1 5^n + c_2 \cdot (-6)^n$ 組成，而
$$
c_1 \cdot 5^n + c_2 \cdot (-6)^n = c_1 \cdot (2^n+3^n) + c_2 \cdot (2^n \cdot 3^n).
$$
所以唯二的變數就是 $a_1$ 和 $a_2$ ，而此兩項就不一定包含於 $\vspan \{(\ldots, 2^n, \ldots), (\ldots, 3^n, \ldots)\}$，所以 :
當 $a_1 , a_2 \in \ \vspan \{(\ldots, 2^n, \ldots), (\ldots, 3^n, \ldots)\}$ 時，
$$
\ker(A^2 - 5A + 6\idmap) = \vspan \{(\ldots, 2^n, \ldots), (\ldots, 3^n, \ldots)\}.
$$
反之，
$$
\ker(A^2 - 5A + 6\idmap) \neq \vspan \{(\ldots, 2^n, \ldots), (\ldots, 3^n, \ldots)\}.
$$

即
$$
\ker(A^2 - 5A + 6\idmap) \supseteq \vspan \{(\ldots, 2^n, \ldots), (\ldots, 3^n, \ldots)\}.
$$

:::info
目前分數 = 5 &times; 檢討 = 6.5
:::