# 遞迴關係式

Recurrence relation

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}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

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

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### 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

##### Exercise 1(a)

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

<!-- eng start -->
Find $a_2,\ldots, a_5$ by definition.
<!-- eng end -->

---
##### Exercise 1(a) - answer here

By running the code above, we obtain that
$a_{n+2} = -3 a_{n+1} + 3 a_n,$
$a_0 = 1, a_1 = 2.$
Thus, we obtain that
$a_2 = -3\times2 + 3\times1 = -3,$
$a_3 = -3\times (-3) + 3\times2 = 15,$
$a_4 = -3\times15 + 3\times(-3) = -54,$
$a_5 = -3\times(-54) + 3\times15 = 207.$

---

##### Exercise 1(b)

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

<!-- eng start -->
Let $\bv_n = \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}$. Find a matrix $A$ such that $\bv_{n+1} = A\bv_n$.
<!-- eng end -->

---
##### Exercise 1(b) - answer here
By 1(a), we know that
$\bv_0 = \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix},$
$\bv_1 = \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 2 \\ -3 \end{bmatrix}.$
Thus,
$\bv_{n+1} = A\bv_n,$
$\bv_1 = A\bv_0,$
$\begin{bmatrix} 2 \\ -3 \end{bmatrix} = A\begin{bmatrix} 1 \\ 2 \end{bmatrix},$
By calculation,
$A =
\begin{bmatrix}
0 & 1 \\
3 & -3
\end{bmatrix}.$

:::warning

- [x] typo: calaulation
:::

---

##### Exercise 1(c)

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

<!-- eng start -->
Use the given $A^5$ to find $a_5$. Does it agree with the one you found in (a)?
<!-- eng end -->

---
##### Exercise 1(c) - answer here

By running the code above, we obtain that
$A_5=\begin{bmatrix}
-135 & 171 \\
513 & -648
\end{bmatrix}.$
We know that
$\begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}=A \begin{bmatrix} a_{n-1} \\ a_n \end{bmatrix}=\cdots= A^n \begin{bmatrix} a_0 \\ a_1 \end{bmatrix}.$
Thus,
$\begin{bmatrix} a_5 \\ a_6 \end{bmatrix}= A^5 \begin{bmatrix} a_0 \\ a_1 \end{bmatrix},$
$\begin{bmatrix} a_5 \\ a_6 \end{bmatrix}= \begin{bmatrix}
-135 & 171 \\
513 & -648
\end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 207 \\ -783 \end{bmatrix}.$
Therefore,
$a_5 = 207.$

---

:::info
What do the experiments try to tell you? (open answer)

...
:::

:::warning
Not answered.
:::

## Exercises

##### Exercise 2

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

<!-- eng start -->
Solve $a_n$ for each of the following recurrence relations.
<!-- eng end -->

##### 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$。

<!-- eng start -->
It is known that

$$
\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}.
$$

Consider the recurrence relation $a_{n+2} = 5a_{n+1} - 6a_n$ with $a_0 = a_1 = 1$.
<!-- eng end -->
---
##### Exercise 2(a) - answer here

$$
\begin{bmatrix}
0 & 1 \\
-6 & 5
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\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}
1 \\
1
\end{bmatrix},
$$

$$
\begin{bmatrix}
0 & 1 \\
-6 & 5
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
2 & 3
\end{bmatrix}
\begin{bmatrix}
2^n & 0 \\
0 & 3^n
\end{bmatrix}
\begin{bmatrix}
3 & -1 \\
-2 & 1
\end{bmatrix}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-6 & 5
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2^n & 3^n \\
2^{n+1} & 3^{n+1}
\end{bmatrix}
\begin{bmatrix}
2 \\
-1
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-6 & 5
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2^{n+1} - 3^n \\
2^{n+2} - 3^{n+1}
\end{bmatrix}
=
\begin{bmatrix}
a_{n} \\
a_{n+1}
\end{bmatrix}.
$$
Therefore,
$a_{n}$ = $2^{n+1} - 3^n.$

---
##### Exercise 2(b)

已知

$$
\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$。

<!-- eng start -->
It is known that

$$
\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}.
$$

Consider the recurrence relation $a_{n+2} = 0a_{n+1} - 4a_n$ with $a_0 = a_1 = 1$.
<!-- eng end -->

---
##### Exercise 2(b) - answer here

$$
\begin{bmatrix}
0 & 1 \\
-4 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
2 & -2
\end{bmatrix}
\begin{bmatrix}
2^n & 0 \\
0 & (-2)^n
\end{bmatrix}
\begin{bmatrix}
1 & 1 \\
2 & -2
\end{bmatrix}^{-1}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$

$$
\begin{bmatrix}
0 & 1 \\
-4 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
2 & -2
\end{bmatrix}
\begin{bmatrix}
2^n & 0 \\
0 & (−2)^n
\end{bmatrix}
\begin{bmatrix}
-2 & -1 \\
-2 & 1
\end{bmatrix}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-4 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2^n & (-2)^n \\
2^{n+1} & (-2)^{n+1}
\end{bmatrix}
\begin{bmatrix}
-3 \\
-1
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-4 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2^n((-1)^{n+1}-3) \\
2^{n+1}((-1)^{n+2}-3)
\end{bmatrix}
=
\begin{bmatrix}
a_{n} \\
a_{n+1}
\end{bmatrix}.
$$
Therefore,
$a_{n}$ = $2^n((-1)^{n+1}-3).$

---

##### Exercise 2(c)

已知

$$
\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$。

<!-- eng start -->
It is known that

$$
\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}.
$$

Consider the recurrence relation $a_{n+2} = 4a_{n+1} - 4a_n$ with $a_0 = a_1 = 1$.
<!-- eng end -->

---
##### Exercise 2(c) - answer here

$$
\begin{bmatrix}
0 & 1 \\
-4 & 4
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2& -1 \\
4 & 0
\end{bmatrix}
\begin{bmatrix}
2^n & 1 \\
0 & 2^n
\end{bmatrix}
\begin{bmatrix}
2& -1 \\
4 & 0
\end{bmatrix}^{-1}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$

$$
\begin{bmatrix}
0 & 1 \\
-4 & 4
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2 & -1 \\
4 & 0
\end{bmatrix}
\begin{bmatrix}
2^n & 1 \\
0 & 2^n
\end{bmatrix}
\begin{bmatrix}
0 & 1 \\
-4 & 2
\end{bmatrix}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-4 & 4
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2^{n+1} & 2-2^n \\
2^{n+2} & 1
\end{bmatrix}
\begin{bmatrix}
1 \\
-2
\end{bmatrix},\
$$
$$
\begin{bmatrix}
0 & 1 \\
-4 & 4
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
2^{n+2}-2^2 \\
2^{n+2}-2
\end{bmatrix}
=
\begin{bmatrix}
a_{n} \\
a_{n+1}
\end{bmatrix}.
$$
Therefore,
$a_{n} = 2^{n+2}-2^2 = 2^{n+2}-4.$

:::warning

- [ ] The power of $\begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}$ is not correct.
:::

---
##### Exercise 2(d)

已知

$$
\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$。

<!-- eng start -->
It is known that

$$
\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}.
$$

Consider the recurrence relation $a_{n+2} = 6a_{n+1} - 9a_n$ with $a_0 = a_1 = 1$.
<!-- eng end -->

---

##### Exercise 2(d) - answer here

$$
\begin{bmatrix}
0 & 1 \\
-9 & 6
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
3 & -1 \\
9 & 0
\end{bmatrix}
\begin{bmatrix}
3^n & 1 \\
0 & 3^n
\end{bmatrix}
\begin{bmatrix}
3 & -1 \\
9 & 0
\end{bmatrix}^{-1}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$

$$
\begin{bmatrix}
0 & 1 \\
-9 & 6
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
3 & -1 \\
9 & 0
\end{bmatrix}
\begin{bmatrix}
3^n & 1 \\
0 & 3^n
\end{bmatrix}
\begin{bmatrix}
0 & 1 \\
-9 & 3
\end{bmatrix}
\begin{bmatrix}
1 \\
1
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-9 & 6
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
3^{n+1} & 3-3^n\\
3^{n+2} & 9
\end{bmatrix}
\begin{bmatrix}
1 \\
-6
\end{bmatrix},
$$
$$
\begin{bmatrix}
0 & 1 \\
-9 & 6
\end{bmatrix}^n
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=
\begin{bmatrix}
3^{n+2}-18 \\
3^{n+2}-54
\end{bmatrix}
=
\begin{bmatrix}
a_{n} \\
a_{n+1}
\end{bmatrix}.
$$
Therefore,
$a_{n}$ = $3^{n+2}-18.$

:::warning

- [ ] The power of $\begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$ is not correct.
:::

---

##### 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$ 的一般式。

<!-- eng start -->
It is known that

$$
\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}.
$$

Solve $a_n$ for the recurrence relation $a_{n+3} = 6a_{n+2} - 11a_{n+1} + 6a_n$ with $a_0 = a_1 = a_2 = 1$.
<!-- eng end -->

---

##### Exercise 3 - answer here

Let
$$ D=\begin{bmatrix}
3 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 1
\end{bmatrix},
A=\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
6 & -11 & 6
\end{bmatrix},
Q=\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix},
A_n = \begin{bmatrix}
a_n \\
a_{n+1} \\
a_{n+2}
\end{bmatrix}.
$$
$$A^n=QD^nQ^{-1}$$
$$=\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}\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}^{-1} $$
$$=\frac{1}{2}\begin{bmatrix}
1 & 1 & 1 \\
3 & 2 & 1 \\
9 & 4 & 1
\end{bmatrix}\begin{bmatrix}
3^n & 0 & 0 \\
0 & 2^n & 0 \\
0 & 0 & 1^n
\end{bmatrix}\begin{bmatrix}
2 & -3 & 1 \\
-6 & 8 & -2 \\
-6 & -5 & 1
\end{bmatrix}
$$

$$
=\frac{1}{2}\begin{bmatrix}
2‧3^n-6‧2^n+6 & -3^{n+1}+2^{n+3} & 3^n-2{n+1}+1 \\
& \cdots & \\
& \cdots &
\end{bmatrix}.
$$
Therefore,
$$
a_n=\frac{1}{2}(2‧3^n-6‧2^n+6-3^{n+1}+2^{n+3}-5+3^n-2^{n+1}+1)=3^n-3‧2^n+1.
$$

---

##### Exercise 4

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

<!-- eng start -->
Find a formula for the $n$-th term $a_n$ in the Fibonacci sequence.
<!-- eng end -->
---

##### Exercise 4 - answer here
Let $$
Q=\begin{bmatrix}
1 & 1 \\
\lambda_1 & \lambda_2 \\
\end{bmatrix},
A=\begin{bmatrix}
0 & 1 \\
1 & 1 \\
\end{bmatrix},
\bv_{n} = \begin{bmatrix}
a_{n} \\
a_{n+1} \\
\end{bmatrix}.
$$
When $\lambda_1=\frac{1-\sqrt{5}}{2},\lambda_2=\frac{1+\sqrt{5}}{2}$, $A$ is diagonalization.
So$$
Q^{-1} A Q = D= \begin{bmatrix}
\lambda_1 & 0 \\
0 & \lambda_2
\end{bmatrix}.
$$
Then,
$\bv_n = A \bv_{n-1} = A^2 \bv_{n-2} = \cdots = A^n \bv_0 = Q D^{n} Q^{-1} \bv_0$
\begin{array}{l}= \begin{bmatrix}
1 & 1 \\
\lambda_1 & \lambda_2 \\
\end{bmatrix}
\begin{bmatrix}
\lambda_1^{n} & 0 \\
0 & \lambda_2^{n} \\
\end{bmatrix}
\begin{bmatrix}
\lambda_2 & -1 \\
-\lambda_1 & 1 \\
\end{bmatrix}
\dfrac{1}{\lambda_2 - \lambda_1} \bv_0
\end{array}

Therefore,

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

:::warning

- [x] $D$ is not correct.
:::

---

##### Exercise 5

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

<!-- eng start -->
The following exercises provide an alternative theory to solve the recurrence relation.
<!-- eng end -->

##### 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}$ 搭配以上定義的向量加法與純量乘法後，是一個向量空間。

<!-- eng start -->
Consider the set

$$
\mathbb{R}^\mathbb{Z} = \{( \ldots, a_{-1}, a_0, a_1, \ldots): a_n \in \mathbb{R} \text{ for all }n\in\mathbb{Z}\}.
$$

Define the vector addition and the scalar multiplication on it as

$$
( \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).
$$

Show that $\mathbb{R}^\mathbb{Z}$ equipped with the two operations above is a vector space.
<!-- eng end -->

##### 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$ 是一個線性函數。

<!-- eng start -->
Define the advanced operator $A: \mathbb{R}^\mathbb{Z} \rightarrow \mathbb{R}^\mathbb{Z}$ by

$$
A(\ldots, a_n, \ldots) = (\ldots, a_{n+1},\ldots).
$$

This operator shifts the given sequence to the left by one slot. Show that $A$ is a linear function.
<!-- eng end -->

##### Exercise 5(a)

說明 $A - 3\idmap$ 也是一個線性函數且

$$
\ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}.
$$

<!-- eng start -->
Show that $A - 3\idmap$ is also a linear function and

$$
\ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}.
$$
<!-- eng end -->

##### Exercise 5(b)

若 $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)\}.
$$

（實際上兩個集合相等，但另一個方向證明要花比較多的力氣。）

<!-- eng start -->
Let $f$ and $g$ be functions in $\mathbb{R}^\mathbb{Z} \rightarrow \mathbb{R}^\mathbb{Z}$. We let $fg$ be the composition $f(g(\cdot))$. Thus, $A^2$ means applying the operator $A$ to the sequence twice.

It is known that $A^2 - 5A + 6\idmap = (A - 2\idmap)(A - 3\idmap)$. Show that

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

(In fact, these two sets are exactly the same, but it is harder to show the other direction.)
<!-- eng end -->

:::info
collaboration: 1
4 problems: 4

- 2a, 2b, 3, 4

moderator: 1
qc: 1
:::