Phương pháp giải hệ thức truy hồi trong trường hợp hệ số bằng 0

[Thanh61 (Thanh2509)]

Anh chị cho em hỏi, trong trường hợp đề cho apha = 0 thì làm thế nào để giải được ạ. Thầy giáo em chỉ nhân với 4^n, nhưng em không biết trình bày và cũng không chắc là đúng hay sai.

[noname00 (HK boy)]

Ở vế phải có chia 4^n thì nhân cả 2 vế với 4^n là ổn rồi còn gì, sợ gì đúng hay sai.

\displaystyle \alpha = 0 \Rightarrow 0 = 4 a_{n-1} - 4 a_{n-2} - \frac{1}{4^n}

Nhân cả 2 vế với 4^n, ta được: 0 = 4^{n+1} a_{n-1} - 4^{n+1} a_{n-2} - 1

\Rightarrow a_{n-1} - a_{n-2} = 4^{-(n+1)} với n \ge 2.

Mà \displaystyle a_0 = \frac{1}{16} = 4^{-2}, a_1 = \frac{5}{64} = \frac{1}{64} + \frac{1}{16} = 4^{-3} + 4^{-2}

\displaystyle \Rightarrow a_n = \sum_{k=2}^{n+2} 4^{-k} = \frac{4^{-1} - 4^{-n-2}}{3}

P/s: Chết thật, hệ thức dạng tuyến tính là gì ấy nhỉ

[hungaya (Hung)]

Đặt b_n = 4^{n+2} . a_n là ra dạng tuyến tính thôi.

[rogp10]

Dạng này gọi là “không thuần nhất” chứ

Hệ số bằng nhau thì cách trên là nhanh nhất.

[Thanh61 (Thanh2509)]

Em cảm ơn anh chị ạ

[tntxtnt]

đoán mò có bài bản phải như thế này : https://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf (5 Linear Recurrences (Annihilators))

Ta có

\begin{aligned} 4a_{n-1} - 4a_{n-2} - \frac{1}{4^n} &= 0 \\ 4a_{n-1} &= \frac{1}{4^n} \\ a_{n-1} &= a_{n-2} + \frac{1}{4^{n+1}} \\ \Rightarrow a_{n+1} &= a_{n} + \frac{1}{4^{n+3}} \end{aligned}

Với dãy S = a_0, a_1, a_2, a_3, ..., a_i, ..., ta có:

\begin{aligned} S &= a_0, a_1, a_2, a_3, ..., a_i, ... \\ E S &= a_1, a_2, a_3, a_4, ..., a_{i+1}, ...\\ \Rightarrow E S - S = (E-1)S &= 4^{-3}, 4^{-4}, 4^{-5}, 4^{-6}, ..., 4^{-3-i}, ... (1)\\ E(E-1)S &= 4^{-4}, 4^{-5}, 4^{-6}, 4^{-7}, ..., 4^{-4-i}, ...\\ 4E(E-1)S &= 4^{-3}, 4^{-4}, 4^{-5}, 4^{-6}, ..., 4^{-3-i}, ... (2)\\ \text{Lấy} (2) - (1) \Rightarrow (4E-1)(E-1)S &= 0\\ 4\left(E-\frac{1}{4}\right)(E-1)S &= 0\\ \left(E-\frac{1}{4}\right)(E-1)S &= 0\\ \end{aligned}

Vậy a_n = \alpha_1\left(\dfrac{1}{4}\right)^n + \alpha_2
Để tìm \alpha_1, \alpha_2, thế a_0 = \dfrac{1}{16} và a_1 = \dfrac{5}{64} ta có \begin{cases} \alpha_1 + \alpha_2 = \frac{1}{16}\\ \frac{1}{4}\alpha_1 + \alpha_2 = \frac{5}{64}\\ \end{cases} \Rightarrow \begin{cases} \frac{3}{4}\alpha_1 = -\frac{1}{64}\\ \alpha_1 + \alpha_2 = \frac{1}{16}\\ \end{cases} \Rightarrow \begin{cases} \alpha_1 = -\frac{1}{48}\\ \alpha_2 = \frac{1}{12}\\ \end{cases}

Vậy \boxed{a_n = \dfrac{1}{12} -\dfrac{1}{48}\left(\dfrac{1}{4}\right)^n}