Dãy số - Phần 4


Hôm nay chúng ta sẽ học về cách giải phương trình sai phân tuyến tính để tìm công thức tổng quát cho dãy số. Phương pháp này có thể sử dụng ở mọi trường hợp, kể cả trường hợp mà phương trình đặc trưngnghiệm bội.



Phương pháp giải phương trình sai phân tuyến tính tổng quát

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 sẽ nêu một vài ví dụ.

  • Nếu phương trình đặc trưng là $(x - x_1)^2=0$ thì $$f_n = (\alpha_{11} + \alpha_{12} ~n) ~ x_1^n .$$
  • Nếu phương trình đặc trưng là $(x - x_1)^2 (x-x_2)=0$ thì $$f_n = (\alpha_{11} + \alpha_{12} ~n) ~ x_1^n + \alpha_{21} ~ x_2^n .$$
  • Nếu phương trình đặc trưng là $(x - x_1)^3 (x-x_2) (x-x_3)^2=0$ thì $$f_n = (\alpha_{11} + \alpha_{12} ~n + \alpha_{13} ~n^2) ~ x_1^n + \alpha_{21} ~ x_2^n + (\alpha_{31} + \alpha_{32} ~n) ~x_3^n .$$
  • Nếu phương trình đặc trưng là $(x - x_1)^2 (x-x_2)^2 (x-x_3)^2=0$ thì $$f_n = (\alpha_{11} + \alpha_{12} ~n ) ~ x_1^n + (\alpha_{21} + \alpha_{22} ~n) ~ x_2^n + (\alpha_{31} + \alpha_{32} ~n) ~x_3^n .$$
  • Nếu phương trình đặc trưng là $(x - x_1) (x-x_2) (x-x_3)=0$ thì $$f_n = \alpha_{11} ~ x_1^n + \alpha_{21} ~ x_2^n + \alpha_{31} ~x_3^n .$$
  • Nếu $j_1 = j_2 = \dots = j_t = 1$, tức là phương trình đặc trưng chỉ có toàn nghiệm đơn $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=a_k(x - x_1) (x - x_2) \dots (x - x_t)=0$$ thì $$f_n = \alpha_{11} ~ x_1^n + \alpha_{21} ~ x_2^n + \dots + \alpha_{t1} ~ x_t^n,$$ như vậy, chúng ta có công thức quen thuộc mà chúng ta đã học ở các bài trước.


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 = 3, ~f_1 = 2, ~f_n = 4 f_{n-1} - 4 f_{n-2}.$$

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



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

Lời giải: Phương trình đặc trưng phải có dạng $$(x-3)(x-4)^2 = x^3 -11 x^2 + 40 x - 48 = 0.$$ Từ đó suy ra phương trình sai phân là $$f_n - 11 f_{n-1} + 40 f_{n-2} - 48 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= 7, ~f_1 = 27, ~f_2 = 109, ~f_n = 11 f_{n-1} - 40 f_{n-2} + 48 f_{n-3}.$$



Tính đúng đắn của phương pháp giải phương trình sai phân

Để chứng minh tính đúng đắn của phương pháp giải phương trình sai phân trên, chúng ta cần chứng minh rằng
  • nếu phương trình đặc trưng chia hết cho $(x-x_i)$ thì dãy số $$f_n = \alpha_{i1} ~x_i^n$$ thoã mãn phương trình sai phân;
  • nếu phương trình đặc trưng chia hết cho $(x-x_i)^2$ thì dãy số $$f_n = (\alpha_{i1} + \alpha_{i2}~n ) ~x_i^n$$ thoã mãn phương trình sai phân;
  • nếu phương trình đặc trưng chia hết cho $(x-x_i)^3$ thì dãy số $$f_n = (\alpha_{i1} + \alpha_{i2}~n + \alpha_{i3}~n^2) ~x_i^n$$ thoã mãn phương trình sai phân; v.v...
  • một cách tổng quát, nếu phương trình đặc trưng $$f(x) = a_k x^k + a_{k-1} x^{k-1} + \dots + a_0 = (x - z)^j (b_s x^s + b_{s-1} x^{s-1} + \dots + b_0)$$ thì dãy số $$f_n = p(n)~z^n$$ thoã mãn phương trình sai phân, trong đó $p(n)$ là một đa thức bất kỳ có bậc bé thua $j$.



Chúng ta phát biểu tính chất này thành một định lý

Định lý cơ bản của phương trình sai phân tuyến tính. Giả sử phương trình đặc trưng có thể viết thành $$f(x) = a_k x^k + a_{k-1} x^{k-1} + \dots + a_0 = (x - z)^j (b_s x^s + b_{s-1} x^{s-1} + \dots + b_0)$$ và $$f_n = p(n)~z^n,$$ trong đó $p(n)$ là một đa thức có bậc bé thua $j$. Vậy thì dãy số $f_n$ thoã mãn phương trình sai phân
$$a_k f_{n} + a_{k-1} f_{n-1} + \dots + a_1 f_{n-k+1} + a_0 f_{n-k} = 0.$$

Kỳ sau, chúng ta sẽ giới thiệu về phép sai phân và dùng phép sai phân để chứng minh định lý cơ bản trên. Nói ngắn gọn thì sai phân của $p(x)$ chính là $$\Delta (p(x)) = p(x+1) - p(x).$$ Phép sai phân trong toán đại số từa tựa như là phép lấy đạo hàm trong giải tích vậy. Phép sai phân có nhiều ứng dụng, chẳng hạn như trên blog này chúng ta đã dùng nó để chứng minh định lý Wilson.

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 = 5, ~f_1 = 9, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$

2. Tìm công thức tổng quát cho dãy số sau  $$f_0 = 2, ~f_1 = 6, ~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 = 1, ~f_1 = 5, ~f_2 = 22, ~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 = 5, ~f_1 = 1, ~f_2 = 11, ~f_3 = 11, ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$

5. Tìm công thức tổng quát cho dãy số sau $$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}.$$

6. Tìm công thức tổng quát cho dãy số sau $$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}.$$

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

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

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




Đáp số.

1. $f_n = (5 - 2n) ~3^n$

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

3. $f_n = 2^n + n ~3^n$

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

5. $f_n = n^2 + n + (-1)^n$

6. $f_n = (2n + 1) (-1)^n + (n-1) 2^n$