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

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

Guessing Particular Solution

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

Example 1
$a_n-2a_{n-1}=n$ for $n\ge 1$ with $a_0=1$
The general solution to the associated HRR is $\alpha _12^n$
Let the trial sequence for a particular solution to the NRR be $P_n=B_1n+B_0$
that is $(B_1n+B_0)-2(B_1(n-1)+B_0)=n$
so $-B_1n+(2B_1-B_0)=n$
that is $B_1=-1, B_0=-2, P_n=-n-2$
The general solution to the NRR is $a_n=\alpha _12^n-n-2$
For $n=0,1=a_0=\alpha _1-2$ that is $\alpha _1=3$
Therefore, $a_n=3\times 2^n-n-2$ for $n\ge 0$.

Example 2
$a_{n+2}-4a_{n+1}+4a_n=2^n,n\ge 0$ with $a_0=a_1=0$
HRR: $a_{n+2}-4a_{n+1}+4a_n=0$ characteristic equation is $r^2-4r+4=0$. $r=2,2$
So the general solution to the associated HRR is $\alpha _1 2^n+\alpha _2n2^n$
Try the trail sequence $P_n=B_02^n$ for a particular solution to the NRR.

$B_02^{n+2}-4B_02^{n+1}+4B_02^n=2^n$

that is

$B_02^n(4-8+4)=2^n$

that is $0=2^n$. It is a contradiction.
Then try $P_n=B_0n2^n$

$B_0(n+2)2^{n+2}-4B_0(n+1)2^{n+1}+4B_0n2^n=2^n$

that is

$B_02^n(4n+8-8n-8+4n)n=2^n$

that is $0=2^n$. It is also a contradiction.
Now try $P_n=B_0n^22^n$

$B_0(n+2)^22^{n+2}-4B_0(n+1)^22^{n+1}+4B_0n^22^n=2^n$

that is

$B_02^n(4(n+2)^2-8(n+1)^2+4n^2)=2^n$

that is $8=2^n$.$B_0=\frac{1}{8}$
so $P_n=\frac{1}{8}n^22^n$ is a particular solution to the NRR.
Hence the general solution to the NRR is $a_n=\alpha _12^n+\alpha _2n2^n+\frac{1}{8}n^22^n$
For initial conditions,

$0=a_0=\alpha _1$

$0=a_1=2\alpha _1 +2\alpha _2 +\frac{1}{4}$

$\alpha _1=0, \alpha _2 =-\frac{1}{8}$

$a_n=\frac{1}{8}n2^n+\frac{1}{8}n^22^n$

so solution is $a_n=n(n-1)2^{n-3}$ for $n\ge 0$.

In general, if the trial sequence mentioned above fails, multiply it by n. Try again. Repeat this procedure as often as necessary to find a particular solution.