This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
Recurrence relation
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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
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
As long as we have a formulat for $A^n$, then we know $\bv_n = A^n\bv_0$.
### 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
令 $\bv_n = \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}$，
找到一個矩陣 $A$ 使得 $\bv_{n+1} = A\bv_n$。
Let $\bv_n = \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix}$. Find a matrix $A$ such that $\bv_{n+1} = A\bv_n$.
利用題目給的 $A^5$，求出 $a_5$。
比較答案是否和前面算的一樣。
Use the given $A^5$ to find $a_5$. Does it agree with the one you found in (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$。
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$.
已知
$$ \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$。
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$.
已知
$$ \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$。
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$.
已知
$$ \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$。
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$.
已知
$$ \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$ 的一般式。
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$.
以下提供解遞迴關係式的另一種觀點。
The following exercises provide an alternative theory to solve the recurrence relation.
考慮集合
$$ \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}$ 搭配以上定義的向量加法與純量乘法後，是一個向量空間。
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.
定義一個左移函數（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$ 是一個線性函數。
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.
說明 $A - 3\idmap$ 也是一個線性函數且
$$ \ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}. $$Show that $A - 3\idmap$ is also a linear function and
$$ \ker(A - 3\idmap) = \vspan\{(\ldots, 3^n, \ldots)\}. $$若 $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)$。
說明
（實際上兩個集合相等，但另一個方向證明要花比較多的力氣。）
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.)