小马的世界

【离散数学】笔记-台湾清华赵启超12A12B Recurrence Relations

2021-08-05 · 4 min read
离散数学 数学

这是台湾清华赵启超教授离散数学12A12B课程的笔记。

Recurrence Relations 递推关系

Example 1
Fibonacci numbers
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} for n≥2withF0=0n\ge 2 with F_0=0

Homogenous Recurrence Relations 齐次递推关系

In general

an−c1an−1−c2an−2−…−ckan−k=0a_n-c_1a_{n-1}-c_2a_{n-2}-\dotsc-c_ka_{n-k}=0

with a0=A0,a1=A1,…,ak−1=Ak−1a_0=A_0,a_1=A_1,\dotsc ,a_{k-1}=A_{k-1}(initial condition)
This is k-th order linear homogenous recurrence relation with constant coefficients.(HRR)
常系数k阶线性齐次递推关系。
or k-th order linear homogenous difference equation with constant coeffcients.(HRE)
或常数系数的k阶线性齐次差分方程。

Example 2
Solve an1−5an+6an−1=0a_{n_1}-5a_n+6a_{n-1}=0 for n≥2n\ge 2 with a1=1,a2=5a_1=1,a_2=5.
Try an=rna_n=r^n.
then rn+1−5rn+6rn−1=0r^{n+1}-5r^n+6r^{n-1}=0
then rn−1(r2−5r+6)=0r^{n-1}(r^2-5r+6)=0
then r2−5r+6=0r^2-5r+6=0 (characteristic equation)
then r=2,3r=2,3
hence both an=2na_n=2^n and an=3na_n=3^n are solutions.
Since the equation is linear
an=α12n+α23na_n=\alpha _1 2^n+\alpha _2 3^nis also a solution for any constants α1\alpha _1 and α2\alpha _2
so an=α12n+α23na_n=\alpha _1 2^n+\alpha _2 3^n is the general solution.
For initial conditions,

1=a1=2α1+3α21=a_1=2\alpha _1+3\alpha _2

5=a2=4α1+9α25=a_2=4\alpha _1+9\alpha _2

so α1=−1,α2=1\alpha _1=-1,\alpha _2=1
so an=−2n+3na_n=-2^n+3^n for n≥1n\ge 1

Example 3
Solve Fn−Fn−1−Fn−2=0F_n-F_{n-1}-F_{n-2}=0 for n≥2n\ge 2 with F0=0,F1=1F_0=0,F_1=1.
characteristic equation

r2−r−1=0r^2-r-1=0

r=1±52r=\frac{1\pm \sqrt{5}}{2}

then General solution=α1(1+52)n+α2(1−52)n=\alpha _1(\frac{1+ \sqrt{5}}{2})^n+\alpha _2(\frac{1- \sqrt{5}}{2})^n
For initial conditions

0=F0=α1+α20=F_0=\alpha _1+\alpha _2

1=F1=α1(1+52)+α2(1−52)1=F_1=\alpha _1(\frac{1+ \sqrt{5}}{2})+\alpha _2(\frac{1- \sqrt{5}}{2})

so α1=15,α2=−15\alpha _1=\frac{1}{\sqrt{5}}, \alpha _2=-\frac{1}{\sqrt{5}}
so Fn=15[(1+52)n−(1−52)n]F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] for n≥0n\ge 0