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

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

Characteristic Equation with Complex Roots

Example 1
$a_n-2a_{n-1}+2a_{n-2}=0$ for $n\ge 2$ with $a_0=1, a_1=2$
characteristic equation: $r^2-2r+2=0$
the solution is $r=1\pm j$ (where $j=\sqrt{-1}$)
$r=\sqrt{2}e^{j\frac{\pi}{4}}$ or $\sqrt{2}e^{-j\frac{\pi}{4}}$($\tau^{j\theta}=cos\theta+jsin\theta$)
The general solution is

$a_n=\alpha _1(\sqrt{2}e^{j\frac{\pi}{4}})+\alpha _2(\sqrt{2}e^{-j\frac{\pi}{4}})^n$

In general, if the roots of the characteristic equation are $\lambda e^{j\theta}$ and $\lambda e^{-j\theta}$, then the general solution to the HRR can be written as

$a_n=\beta _1\lambda^n cosn\theta+\beta _2\lambda^nsinn\theta$

Nonhomogeneous Recurrence Relations

$a_n -c_1a_{n-1}-c_2a_{n-2}-\dotsc -c_ka_{n-k}=f_n$

$f_n$ is forcing sequence
k-th-order linear nonhomogeneous recurrence relation(NRR) with constant coefficients
or k-th-order linear nonhomogeneous difference equation(NDE) with constant coefficients.