Dãy số - Phần 5

Hôm nay chúng ta sẽ làm một số bài tập để rèn luyện kỹ năng giải phương trình sai phân tuyến tính.



Giả sử chúng ta cần tìm công thức cho dãy số $\{f_n\}$ thõa mãn phương trình sai phân $$a_k f_{n} + a_{k-1} f_{n-1} + a_{k-2} f_{n-2} + \dots + a_0 f_{n-k}=0$$ với điều kiện ban đầu là những giá trị của $f_0, f_1, \dots, f_{k-1}$, chúng ta sẽ giải bằng hai bước sau đây.

Bước 1. Giải phương trình sai phân.
Tạo phương trình đặc trưng $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=0$$ và tìm nghiệm của nó
$$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=a_k(x - x_1)^{j_1} (x - x_2)^{j_2} \dots (x - x_t)^{j_t}.$$

Giả sử phương trình đặc trưng có $t$ nghiệm $x_1, \dots, x_t$, trong đó $x_1$ là nghiệm bội bậc $j_1$, $x_2$ là nghiệm bội bậc $j_2$, v.v... Vậy thì với mọi hằng số $\alpha_{ij}$, dãy số $$f_n = (\alpha_{11} + \alpha_{12} n + \dots + \alpha_{1 j_1} n^{j_1 - 1}) ~ x_1^n + (\alpha_{21} + \alpha_{22} n + \dots + \alpha_{2 j_2} n^{j_2 - 1}) ~ x_2^n$$ $$+ \dots + (\alpha_{t1} + \alpha_{t2} n + \dots + \alpha_{t j_t} n^{j_t - 1}) ~ x_t^n$$ thõa mãn phương trình sai phân $$a_k f_{n} + a_{k-1} f_{n-1} + a_{k-2} f_{n-2} + \dots + a_0 f_{n-k}=0.$$  

Bước 2. Giải quyết các điều kiện ban đầu.
Thay các giá trị của $f_0, f_1, \dots, f_{k-1}$ vào biểu thức của $f_n$ để lập một hệ phương trình cho các hệ số $\alpha_{ij}$ rồi giải hệ phương trình này.

Bây giờ chúng ta làm vài bài tập.

Bài toán 1: Tìm công thức tổng quát cho dãy số sau   $$f_0 = 5, ~f_1 = 9, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$

Lời giải: Từ phương trình sai phân $$f_n - 6 f_{n-1} + 9 f_{n-2}=0$$ chúng ta có phương trình đặc trưng $$x^2 - 6 x + 9 = 0.$$ Giải phương trình này chúng ta có $$x^2 - 6 x + 9 = (x-3)^2= 0,$$ tức là một nghiệm bội $x = 3$ bậc 2. Vậy chúng ta tìm dãy số có dạng  $$f_n = (\alpha_{11} + \alpha_{12} ~n )~ 3^n.$$ Với $n=0,1$, chúng ta có $$f_0 = \alpha_{11} = 5,$$ $$f_1 = (\alpha_{11} + \alpha_{12}) ~3 = 9.$$ Giải hệ phương trình này chúng ta có $\alpha_{11} = 5$ và $\alpha_{12} = -2$. Từ đó chúng ta có $$f_n = (5 - 2n) ~3^n.$$



Bài toán 2: Tìm công thức tổng quát cho dãy số sau   $$f_0 = 1, ~f_1 = 5, ~f_2 = 22, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$

Lời giải: Từ phương trình sai phân $$f_n - 8 f_{n-1} + 21 f_{n-2}- 18 f_{n-3}=0$$ chúng ta có phương trình đặc trưng $$x^3 - 8 x^2 + 21 x - 18 = 0.$$ Giải phương trình này chúng ta có $$x^3 - 8 x^2 + 21 x - 18 = (x-2)(x-3)^2= 0.$$ Vậy chúng ta tìm dãy số có dạng  $$f_n = \alpha_{11} ~ 2^n + (\alpha_{21} + \alpha_{22} ~n )~ 3^n.$$ Với $n=0,1,2$, chúng ta có $$f_0 = \alpha_{11} + \alpha_{21} = 1,$$ $$f_1 = 2 \alpha_{11} + 3 \alpha_{21} + 3 \alpha_{22} = 5,$$ $$f_2 = 4 \alpha_{11} + 9 \alpha_{21} + 18 \alpha_{22} = 22.$$ Giải hệ phương trình này chúng ta có $\alpha_{11} = 1$, $\alpha_{21}=0$ và $\alpha_{22} = 1$. Từ đó chúng ta có $$f_n = 2^n + n ~3^n.$$



Bài toán 3: Tìm công thức tổng quát cho dãy số sau   $$f_0 = 5, ~f_1 = 1, ~f_2 = 11, ~f_3 = 11, ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$

Lời giải: Từ phương trình sai phân $$f_n - 2 f_{n-1} + 2 f_{n-3}- f_{n-4}=0$$ chúng ta có phương trình đặc trưng $$x^4 - 2 x^3 + 2x - 1 = 0.$$ Giải phương trình này chúng ta có $$x^4 - 2 x^3 + 2x - 1 = (x+1) (x-1)^3 = 0.$$ Vậy chúng ta tìm dãy số có dạng  $$f_n = \alpha_{11} ~ (-1)^n + (\alpha_{21} + \alpha_{22} ~n + \alpha_{23} ~n^2) ~1^n.$$ Với $n=0,1,2,3$, chúng ta có $$f_0 = \alpha_{11} + \alpha_{21} = 5,$$ $$f_1 = - \alpha_{11} + \alpha_{21} + \alpha_{22} + \alpha_{23} = 1,$$ $$f_2 = \alpha_{11} + \alpha_{21} + 2 \alpha_{22} + 4 \alpha_{23} = 11,$$ $$f_3 = - \alpha_{11} + \alpha_{21} + 3 \alpha_{22} + 9 \alpha_{23}= 11.$$ Giải hệ phương trình này chúng ta có $\alpha_{11} = 3$, $\alpha_{21}=2$, $\alpha_{22} = 1$ và $\alpha_{23} = 1$. Từ đó chúng ta có $$f_n = 3 (-1)^{n} + 2 + n + n^2 .$$

Bài toán 4: Tìm công thức truy hồi cho dãy số $f_n = n ~3^n$.

Lời giải: Phương trình đặc trưng phải có dạng $$(x-3)^2 = x^2 - 6 x + 9 = 0.$$ Từ đó suy ra phương trình sai phân là $$f_n - 6 f_{n-1} + 9 f_{n-2} = 0.$$ Kết hợp với điều kiện ban đầu chúng ta có công thức truy hồi $$f_0= 0, ~f_1 = 3, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$





Bài toán 5: Tìm công thức truy hồi cho dãy số $f_n = (2n + 1) 3^n - 2^n$.

Lời giải: Phương trình đặc trưng phải có dạng $$(x-2)(x-3)^2 = x^3 - 8 x^2 + 21 x - 18 = 0.$$ Từ đó suy ra phương trình sai phân là $$f_n - 8 f_{n-1} + 21 f_{n-2}- 18 f_{n-3}=0.$$ Kết hợp với điều kiện ban đầu chúng ta có công thức truy hồi $$f_0= 0, ~f_1 = 7, ~f_2 = 41, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$

Bài toán 6: Tìm công thức truy hồi cho dãy số $f_n = n^2 + n + (-1)^n$.

Lời giải: Chúng ta có $$f_n = (n^2 + n) ~ 1^n + (-1)^n,$$ do đó phương trình đặc trưng phải có dạng $$(x+1) (x-1)^3 = x^4 - 2 x^3 + 2x - 1 = 0.$$ Từ đó suy ra phương trình sai phân là $$f_n - 2 f_{n-1} + 2 f_{n-3}- f_{n-4} = 0.$$ Kết hợp với điều kiện ban đầu chúng ta có công thức truy hồi $$f_0= 1, ~f_1 = 1, ~f_2 = 7, ~f_3 =11 , ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$

Bài toán 7: Tìm công thức truy hồi cho dãy số $f_n = (2n + 1) (-1)^n + (n-1) ~2^n$.

Lời giải: Phương trình đặc trưng phải có dạng $$(x+1)^2 (x-2)^2 = x^4 - 2 x^3 - 3 x^2 + 4x + 4 = 0.$$ Từ đó suy ra phương trình sai phân là $$f_n - 2 f_{n-1} - 3 f_{n-2} + 4 f_{n-3} + 4 f_{n-4} = 0.$$ Kết hợp với điều kiện ban đầu chúng ta có công thức truy hồi $$f_0= 0, ~f_1 = -3, ~f_2 = 9, ~f_3 =9 , ~f_n = 2 f_{n-1}  + 3 f_{n-2} - 4 f_{n-3} - 4 f_{n-4}.$$

Chúng ta tạm dừng ở đây, hẹn gặp lại các bạn ở các kỳ sau nhé.



Bài tập về nhà.


1. Tìm công thức tổng quát cho dãy số sau   $$f_0 = 3, ~f_1 = 6, ~f_n = 4 f_{n-1} - 4 f_{n-2}.$$

2. Tìm công thức tổng quát cho dãy số sau   $$f_0 = 0, ~f_1 = 9, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$

3. Tìm công thức tổng quát cho dãy số sau   $$f_0 = 0, ~f_1 = 1, ~f_2 = 5, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$

4. Tìm công thức tổng quát cho dãy số sau   $$f_0 = 1, ~f_1 = 0, ~f_2 = 3, ~f_3 = 2, ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$

5. Tìm công thức truy hồi cho dãy số $f_n = n~ 2^n$.

6. Tìm công thức truy hồi cho dãy số $f_n = 2n^3 - n^2 + 3n -1$.


Đáp số.

1. $f_n = 3 \times 2^n$

2. $f_n = n \times 3^{n+1}$

3. $f_n = 3^n - 2^n$

4. $f_n = (-1)^{n} + n$