小马的世界

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

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

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

Characteristic Equation with Complex Roots

Example 1
an2an1+2an2=0a_n-2a_{n-1}+2a_{n-2}=0 for n2n\ge 2 with a0=1,a1=2a_0=1, a_1=2
characteristic equation: r22r+2=0r^2-2r+2=0
the solution is r=1±jr=1\pm j (where j=1j=\sqrt{-1})
r=2ejπ4r=\sqrt{2}e^{j\frac{\pi}{4}} or 2ejπ4\sqrt{2}e^{-j\frac{\pi}{4}}(τjθ=cosθ+jsinθ\tau^{j\theta}=cos\theta+jsin\theta)
The general solution is

an=α1(2ejπ4)+α2(2ejπ4)na_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 λejθ\lambda e^{j\theta} and λejθ\lambda e^{-j\theta}, then the general solution to the HRR can be written as

an=β1λncosnθ+β2λnsinnθa_n=\beta _1\lambda^n cosn\theta+\beta _2\lambda^nsinn\theta

Nonhomogeneous Recurrence Relations

anc1an1c2an2ckank=fna_n -c_1a_{n-1}-c_2a_{n-2}-\dotsc -c_ka_{n-k}=f_n

fnf_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.