Hệ thức truy hồi là gì? Cách giải hệ thức truy hồi toán rời rạc

Hệ thức truy hồi là một công cụ toán học quan trọng dùng để mô tả các dãy số mà mỗi số hạng được xác định thông qua các số hạng đứng trước nó. Hệ thức truy hồi (hay công thức truy hồi) là phương trình biểu diễn mối quan hệ giữa số hạng tổng quát của dãy số với một hoặc nhiều số hạng trước đó. Bài viết dưới đây sẽ giúp bạn hiểu rõ định nghĩa, phân loại, phương pháp giải và các ví dụ minh họa chi tiết về hệ thức truy hồi.

1. Hệ thức truy hồi là gì?

Hệ thức truy hồi (tiếng Anh: Recurrence relation) là phương trình xác định số hạng thứ n của một dãy số thông qua các số hạng có chỉ số nhỏ hơn n.

1.1. Định nghĩa

Định nghĩa: Hệ thức truy hồi cho dãy số \( \{a_n\} \) là một phương trình có dạng:

\[ a_n = f(a_{n-1}, a_{n-2}, …, a_{n-k}, n) \]

Trong đó:

• \( a_n \): Số hạng thứ n cần tìm
• \( a_{n-1}, a_{n-2}, …, a_{n-k} \): Các số hạng trước đó
• k: Bậc của hệ thức truy hồi (số lượng số hạng trước cần dùng)
• f: Hàm xác định mối quan hệ

1.2. Điều kiện đầu (điều kiện biên)

Để xác định duy nhất một dãy số từ hệ thức truy hồi bậc k, ta cần k điều kiện đầu:

\[ a_0 = c_0, \quad a_1 = c_1, \quad …, \quad a_{k-1} = c_{k-1} \]

Bậc hệ thức	Số điều kiện đầu	Ví dụ
Bậc 1	1	\( a_0 = 1 \)
Bậc 2	2	\( a_0 = 0, a_1 = 1 \)
Bậc 3	3	\( a_0 = 1, a_1 = 1, a_2 = 2 \)
Bậc k	k	\( a_0, a_1, …, a_{k-1} \)

1.3. Ví dụ đơn giản

Ví dụ 1: Dãy số Fibonacci

\[ F_n = F_{n-1} + F_{n-2} \]

Điều kiện đầu: \( F_0 = 0, F_1 = 1 \)

Dãy: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Ví dụ 2: Giai thừa

\[ n! = n \cdot (n-1)! \]

Điều kiện đầu: \( 0! = 1 \)

Dãy: 1, 1, 2, 6, 24, 120, 720, …

2. Phân loại hệ thức truy hồi

Hệ thức truy hồi được phân loại theo nhiều tiêu chí khác nhau:

2.1. Phân loại theo tính tuyến tính

Loại	Đặc điểm	Ví dụ
Tuyến tính	Các số hạng \( a_{n-i} \) chỉ có bậc 1, không có tích	\( a_n = 2a_{n-1} + 3a_{n-2} \)
Phi tuyến	Có lũy thừa hoặc tích của các số hạng	\( a_n = a_{n-1}^2 + a_{n-2} \)

2.2. Phân loại theo bậc

Bậc	Dạng tổng quát	Ví dụ
Bậc 1	\( a_n = f(a_{n-1}, n) \)	\( a_n = 2a_{n-1} + 1 \)
Bậc 2	\( a_n = f(a_{n-1}, a_{n-2}, n) \)	\( a_n = a_{n-1} + a_{n-2} \)
Bậc k	\( a_n = f(a_{n-1}, …, a_{n-k}, n) \)	\( a_n = a_{n-1} + a_{n-2} + a_{n-3} \)

2.3. Phân loại theo tính thuần nhất (với hệ thức tuyến tính)

Loại	Đặc điểm	Ví dụ
Thuần nhất	Không có số hạng tự do (chỉ phụ thuộc \( a_{n-i} \))	\( a_n = 3a_{n-1} – 2a_{n-2} \)
Không thuần nhất	Có số hạng tự do f(n)	\( a_n = 3a_{n-1} + n^2 \)

2.4. Phân loại theo hệ số

Loại	Đặc điểm	Ví dụ
Hệ số hằng	Các hệ số không phụ thuộc n	\( a_n = 2a_{n-1} + 3a_{n-2} \)
Hệ số biến đổi	Các hệ số phụ thuộc vào n	\( a_n = na_{n-1} + a_{n-2} \)

3. Hệ thức truy hồi tuyến tính cấp k hệ số hằng

Đây là dạng hệ thức truy hồi quan trọng nhất và có phương pháp giải có hệ thống.

3.1. Dạng tổng quát

Dạng thuần nhất:

\[ a_n + c_1 a_{n-1} + c_2 a_{n-2} + … + c_k a_{n-k} = 0 \]

Hay viết lại:

\[ a_n = -c_1 a_{n-1} – c_2 a_{n-2} – … – c_k a_{n-k} \]

Dạng không thuần nhất:

\[ a_n + c_1 a_{n-1} + c_2 a_{n-2} + … + c_k a_{n-k} = f(n) \]

3.2. Phương trình đặc trưng

Để giải hệ thức truy hồi tuyến tính thuần nhất, ta lập phương trình đặc trưng:

\[ r^k + c_1 r^{k-1} + c_2 r^{k-2} + … + c_{k-1} r + c_k = 0 \]

Cách lập: Thay \( a_n \) bằng \( r^n \), rồi chia cho \( r^{n-k} \).

3.3. Ví dụ lập phương trình đặc trưng

Cho hệ thức: \( a_n = 5a_{n-1} – 6a_{n-2} \)

Viết lại: \( a_n – 5a_{n-1} + 6a_{n-2} = 0 \)

Phương trình đặc trưng: \( r^2 – 5r + 6 = 0 \)

Giải: \( (r-2)(r-3) = 0 \Rightarrow r_1 = 2, r_2 = 3 \)

4. Phương pháp giải hệ thức truy hồi tuyến tính thuần nhất

Việc giải hệ thức truy hồi tuyến tính thuần nhất phụ thuộc vào nghiệm của phương trình đặc trưng.

4.1. Trường hợp 1: Nghiệm đơn phân biệt

Nếu phương trình đặc trưng có k nghiệm phân biệt \( r_1, r_2, …, r_k \), nghiệm tổng quát là:

\[ a_n = A_1 r_1^n + A_2 r_2^n + … + A_k r_k^n \]

Trong đó \( A_1, A_2, …, A_k \) là các hằng số được xác định từ điều kiện đầu.

4.2. Trường hợp 2: Nghiệm bội

Nếu \( r_0 \) là nghiệm bội m của phương trình đặc trưng, phần nghiệm tương ứng là:

\[ (A_1 + A_2 n + A_3 n^2 + … + A_m n^{m-1}) r_0^n \]

Bội số	Đóng góp vào nghiệm
Nghiệm đơn (m=1)	\( A \cdot r_0^n \)
Nghiệm bội 2 (m=2)	\( (A_1 + A_2 n) r_0^n \)
Nghiệm bội 3 (m=3)	\( (A_1 + A_2 n + A_3 n^2) r_0^n \)

4.3. Trường hợp 3: Nghiệm phức

Nếu có cặp nghiệm phức liên hợp \( r = \alpha \pm \beta i \), viết dưới dạng lượng giác:

\[ r = \rho(\cos\theta \pm i\sin\theta) \]

Với \( \rho = \sqrt{\alpha^2 + \beta^2} \) và \( \tan\theta = \frac{\beta}{\alpha} \)

Phần nghiệm tương ứng:

\[ \rho^n (A\cos(n\theta) + B\sin(n\theta)) \]

4.4. Bảng tổng hợp các trường hợp

Nghiệm phương trình đặc trưng	Dạng nghiệm tổng quát
\( r_1, r_2 \) phân biệt	\( a_n = A_1 r_1^n + A_2 r_2^n \)
\( r_0 \) bội 2	\( a_n = (A_1 + A_2 n) r_0^n \)
\( \alpha \pm \beta i \)	\( a_n = \rho^n(A\cos(n\theta) + B\sin(n\theta)) \)

4.5. Các bước giải chi tiết

1. Bước 1: Viết hệ thức truy hồi về dạng chuẩn
2. Bước 2: Lập phương trình đặc trưng
3. Bước 3: Giải phương trình đặc trưng tìm các nghiệm
4. Bước 4: Viết nghiệm tổng quát theo các trường hợp
5. Bước 5: Dùng điều kiện đầu để tìm các hằng số
6. Bước 6: Viết công thức tường minh cho \( a_n \)

5. Phương pháp giải hệ thức truy hồi tuyến tính không thuần nhất

Với hệ thức truy hồi không thuần nhất, nghiệm có dạng:

\[ a_n = a_n^{(h)} + a_n^{(p)} \]

Trong đó:

• \( a_n^{(h)} \): Nghiệm tổng quát của phần thuần nhất
• \( a_n^{(p)} \): Nghiệm riêng của phương trình không thuần nhất

5.1. Phương pháp tìm nghiệm riêng

Tùy thuộc vào dạng của f(n), ta đoán nghiệm riêng:

Dạng f(n)	Dạng nghiệm riêng thử	Điều kiện
Hằng số c	\( a_n^{(p)} = A \)	1 không là nghiệm đặc trưng
Đa thức bậc m	\( a_n^{(p)} = A_m n^m + … + A_1 n + A_0 \)	1 không là nghiệm đặc trưng
\( b^n \)	\( a_n^{(p)} = A \cdot b^n \)	b không là nghiệm đặc trưng
\( b^n \) (b là nghiệm bội s)	\( a_n^{(p)} = A \cdot n^s \cdot b^n \)	b là nghiệm bội s
\( n^m \cdot b^n \)	\( a_n^{(p)} = (A_m n^m + … + A_0) b^n \)	b không là nghiệm

5.2. Ví dụ minh họa

Giải: \( a_n = 2a_{n-1} + 3^n \), với \( a_0 = 1 \)

Bước 1: Giải phần thuần nhất \( a_n = 2a_{n-1} \)

Phương trình đặc trưng: \( r = 2 \)

Nghiệm thuần nhất: \( a_n^{(h)} = A \cdot 2^n \)

Bước 2: Tìm nghiệm riêng

f(n) = \( 3^n \), thử \( a_n^{(p)} = B \cdot 3^n \)

Thay vào: \( B \cdot 3^n = 2 \cdot B \cdot 3^{n-1} + 3^n \)

\( 3B = 2B + 3 \Rightarrow B = 3 \)

Nghiệm riêng: \( a_n^{(p)} = 3 \cdot 3^n = 3^{n+1} \)

Bước 3: Nghiệm tổng quát

\( a_n = A \cdot 2^n + 3^{n+1} \)

Bước 4: Dùng điều kiện đầu

\( a_0 = A \cdot 1 + 3 = 1 \Rightarrow A = -2 \)

Kết quả: \( a_n = -2 \cdot 2^n + 3^{n+1} = 3^{n+1} – 2^{n+1} \)

6. Các hệ thức truy hồi nổi tiếng

Dưới đây là một số hệ thức truy hồi kinh điển trong toán học:

6.1. Dãy Fibonacci

Hệ thức: \( F_n = F_{n-1} + F_{n-2} \)

Điều kiện đầu: \( F_0 = 0, F_1 = 1 \)

Công thức tường minh (Công thức Binet):

\[ F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^n – \left( \frac{1-\sqrt{5}}{2} \right)^n \right] \]

Dãy số: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

6.2. Giai thừa

Hệ thức: \( n! = n \cdot (n-1)! \)

Điều kiện đầu: \( 0! = 1 \)

Dãy số: 1, 1, 2, 6, 24, 120, 720, 5040, …

6.3. Bài toán Tháp Hà Nội

Hệ thức: \( T_n = 2T_{n-1} + 1 \)

Điều kiện đầu: \( T_1 = 1 \)

Công thức tường minh: \( T_n = 2^n – 1 \)

Ý nghĩa: Số bước tối thiểu để di chuyển n đĩa.

6.4. Số Catalan

Hệ thức: \( C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} \)

Điều kiện đầu: \( C_0 = 1 \)

Công thức tường minh: \( C_n = \frac{1}{n+1} \binom{2n}{n} \)

Dãy số: 1, 1, 2, 5, 14, 42, 132, …

6.5. Dãy Lucas

Hệ thức: \( L_n = L_{n-1} + L_{n-2} \)

Điều kiện đầu: \( L_0 = 2, L_1 = 1 \)

Dãy số: 2, 1, 3, 4, 7, 11, 18, 29, 47, …

6.6. Bảng tổng hợp

Tên dãy	Hệ thức truy hồi	Điều kiện đầu	Công thức tường minh
Fibonacci	\( F_n = F_{n-1} + F_{n-2} \)	\( F_0=0, F_1=1 \)	Công thức Binet
Giai thừa	\( n! = n(n-1)! \)	\( 0! = 1 \)	\( n! \)
Tháp Hà Nội	\( T_n = 2T_{n-1} + 1 \)	\( T_1 = 1 \)	\( 2^n – 1 \)
Cấp số cộng	\( a_n = a_{n-1} + d \)	\( a_1 \)	\( a_1 + (n-1)d \)
Cấp số nhân	\( a_n = q \cdot a_{n-1} \)	\( a_1 \)	\( a_1 \cdot q^{n-1} \)

7. Ứng dụng của hệ thức truy hồi

Hệ thức truy hồi có rất nhiều ứng dụng trong thực tế và các ngành khoa học:

7.1. Trong Toán học

• Tổ hợp: Đếm số cách sắp xếp, phân hoạch
• Lý thuyết số: Nghiên cứu các dãy số đặc biệt
• Giải tích: Tính xấp xỉ, phương pháp lặp

7.2. Trong Khoa học máy tính

• Phân tích thuật toán: Đánh giá độ phức tạp (chia để trị)
• Quy hoạch động: Giải các bài toán tối ưu
• Đệ quy: Cài đặt các hàm đệ quy

7.3. Trong các lĩnh vực khác

Lĩnh vực	Ứng dụng
Sinh học	Mô hình tăng trưởng quần thể
Kinh tế	Mô hình lãi kép, tăng trưởng
Vật lý	Hệ động lực rời rạc
Mật mã học	Sinh số ngẫu nhiên

7.4. Ví dụ: Thuật toán chia để trị

Thuật toán Merge Sort có độ phức tạp thời gian T(n) thỏa mãn:

\[ T(n) = 2T\left(\frac{n}{2}\right) + O(n) \]

Giải ra: \( T(n) = O(n \log n) \)

8. Ví dụ và bài tập minh họa có lời giải chi tiết

Để nắm vững cách giải hệ thức truy hồi, hãy cùng làm các bài tập sau:

Bài tập 1: Hệ thức truy hồi bậc 1

Đề bài: Giải hệ thức truy hồi: \( a_n = 3a_{n-1} + 2 \) với \( a_0 = 1 \)

Lời giải:

Bước 1: Giải phần thuần nhất \( a_n = 3a_{n-1} \)

Phương trình đặc trưng: r = 3

Nghiệm thuần nhất: \( a_n^{(h)} = A \cdot 3^n \)

Bước 2: Tìm nghiệm riêng

f(n) = 2 (hằng số), thử \( a_n^{(p)} = B \)

Thay vào: \( B = 3B + 2 \Rightarrow -2B = 2 \Rightarrow B = -1 \)

Nghiệm riêng: \( a_n^{(p)} = -1 \)

Bước 3: Nghiệm tổng quát

\( a_n = A \cdot 3^n – 1 \)

Bước 4: Dùng điều kiện đầu

\( a_0 = A \cdot 1 – 1 = 1 \Rightarrow A = 2 \)

Kết quả: \( a_n = 2 \cdot 3^n – 1 \)

Kiểm tra:

• \( a_0 = 2 – 1 = 1 \) ✓
• \( a_1 = 6 – 1 = 5 = 3(1) + 2 \) ✓
• \( a_2 = 18 – 1 = 17 = 3(5) + 2 \) ✓

Bài tập 2: Hệ thức truy hồi bậc 2 (nghiệm phân biệt)

Đề bài: Giải hệ thức truy hồi: \( a_n = 5a_{n-1} – 6a_{n-2} \) với \( a_0 = 1, a_1 = 4 \)

Lời giải:

Bước 1: Lập phương trình đặc trưng

\( r^2 – 5r + 6 = 0 \)

\( (r-2)(r-3) = 0 \)

Nghiệm: \( r_1 = 2, r_2 = 3 \) (phân biệt)

Bước 2: Viết nghiệm tổng quát

\( a_n = A \cdot 2^n + B \cdot 3^n \)

Bước 3: Dùng điều kiện đầu

\( a_0 = A + B = 1 \) … (1)

\( a_1 = 2A + 3B = 4 \) … (2)

Từ (1): \( A = 1 – B \)

Thay vào (2): \( 2(1-B) + 3B = 4 \)

\( 2 + B = 4 \Rightarrow B = 2 \)

\( A = 1 – 2 = -1 \)

Kết quả: \( a_n = -2^n + 2 \cdot 3^n = 2 \cdot 3^n – 2^n \)

Kiểm tra:

• \( a_0 = 2 – 1 = 1 \) ✓
• \( a_1 = 6 – 2 = 4 \) ✓
• \( a_2 = 18 – 4 = 14 = 5(4) – 6(1) = 14 \) ✓

Bài tập 3: Hệ thức truy hồi bậc 2 (nghiệm bội)

Đề bài: Giải: \( a_n = 4a_{n-1} – 4a_{n-2} \) với \( a_0 = 1, a_1 = 4 \)

Lời giải:

Bước 1: Phương trình đặc trưng

\( r^2 – 4r + 4 = 0 \)

\( (r-2)^2 = 0 \)

Nghiệm: \( r = 2 \) (bội 2)

Bước 2: Nghiệm tổng quát (nghiệm bội 2)

\( a_n = (A + Bn) \cdot 2^n \)

Bước 3: Dùng điều kiện đầu

\( a_0 = (A + 0) \cdot 1 = A = 1 \)

\( a_1 = (A + B) \cdot 2 = (1 + B) \cdot 2 = 4 \)

\( 1 + B = 2 \Rightarrow B = 1 \)

Kết quả: \( a_n = (1 + n) \cdot 2^n = (n+1) \cdot 2^n \)

Kiểm tra:

• \( a_0 = 1 \cdot 1 = 1 \) ✓
• \( a_1 = 2 \cdot 2 = 4 \) ✓
• \( a_2 = 3 \cdot 4 = 12 = 4(4) – 4(1) = 12 \) ✓

Bài tập 4: Dãy Fibonacci

Đề bài: Tìm công thức tường minh của dãy Fibonacci: \( F_n = F_{n-1} + F_{n-2} \) với \( F_0 = 0, F_1 = 1 \)

Lời giải:

Bước 1: Phương trình đặc trưng

\( r^2 – r – 1 = 0 \)

\( r = \frac{1 \pm \sqrt{5}}{2} \)

Đặt: \( \phi = \frac{1+\sqrt{5}}{2} \) (tỉ lệ vàng) và \( \hat{\phi} = \frac{1-\sqrt{5}}{2} \)

Bước 2: Nghiệm tổng quát

\( F_n = A \cdot \phi^n + B \cdot \hat{\phi}^n \)

Bước 3: Dùng điều kiện đầu

\( F_0 = A + B = 0 \Rightarrow B = -A \)

\( F_1 = A\phi + B\hat{\phi} = A(\phi – \hat{\phi}) = A \cdot \sqrt{5} = 1 \)

\( A = \frac{1}{\sqrt{5}}, \quad B = -\frac{1}{\sqrt{5}} \)

Kết quả (Công thức Binet):

\[ F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^n – \left( \frac{1-\sqrt{5}}{2} \right)^n \right] \]

Bài tập 5: Bài toán Tháp Hà Nội

Đề bài: Tìm công thức tính số bước tối thiểu để di chuyển n đĩa trong bài toán Tháp Hà Nội.

Hệ thức: \( T_n = 2T_{n-1} + 1 \) với \( T_1 = 1 \)

Lời giải:

Cách 1: Giải trực tiếp

Nghiệm thuần nhất: \( T_n^{(h)} = A \cdot 2^n \)

Nghiệm riêng: Thử \( T_n^{(p)} = B \)

\( B = 2B + 1 \Rightarrow B = -1 \)

Nghiệm tổng quát: \( T_n = A \cdot 2^n – 1 \)

Điều kiện đầu: \( T_1 = 2A – 1 = 1 \Rightarrow A = 1 \)

Kết quả: \( T_n = 2^n – 1 \)

Cách 2: Chứng minh quy nạp

\( T_1 = 2^1 – 1 = 1 \) ✓

Giả sử đúng với n-1: \( T_{n-1} = 2^{n-1} – 1 \)

\( T_n = 2T_{n-1} + 1 = 2(2^{n-1} – 1) + 1 = 2^n – 2 + 1 = 2^n – 1 \) ✓

Bài tập 6: Hệ thức không thuần nhất với f(n) là đa thức

Đề bài: Giải: \( a_n = 2a_{n-1} + n \) với \( a_0 = 0 \)

Lời giải:

Bước 1: Nghiệm thuần nhất

\( a_n^{(h)} = A \cdot 2^n \)

Bước 2: Tìm nghiệm riêng

f(n) = n (đa thức bậc 1), thử \( a_n^{(p)} = Bn + C \)

Thay vào: \( Bn + C = 2(B(n-1) + C) + n \)

\( Bn + C = 2Bn – 2B + 2C + n \)

\( Bn + C = (2B + 1)n + (2C – 2B) \)

So sánh hệ số:

• Hệ số n: \( B = 2B + 1 \Rightarrow B = -1 \)
• Hệ số tự do: \( C = 2C – 2B = 2C + 2 \Rightarrow C = -2 \)

Nghiệm riêng: \( a_n^{(p)} = -n – 2 \)

Bước 3: Nghiệm tổng quát

\( a_n = A \cdot 2^n – n – 2 \)

Bước 4: Điều kiện đầu

\( a_0 = A – 0 – 2 = 0 \Rightarrow A = 2 \)

Kết quả: \( a_n = 2^{n+1} – n – 2 \)

Kiểm tra:

• \( a_0 = 2 – 0 – 2 = 0 \) ✓
• \( a_1 = 4 – 1 – 2 = 1 = 2(0) + 1 \) ✓
• \( a_2 = 8 – 2 – 2 = 4 = 2(1) + 2 \) ✓

9. Kết luận

Qua bài viết trên, VJOL đã giúp bạn hiểu rõ về hệ thức truy hồi cùng các kiến thức quan trọng liên quan. Tóm tắt những điểm cần nhớ:

• Hệ thức truy hồi là phương trình xác định số hạng thứ n qua các số hạng trước đó, cần kèm theo điều kiện đầu
• Phân loại: Tuyến tính/phi tuyến, thuần nhất/không thuần nhất, hệ số hằng/biến đổi
• Phương pháp giải: Lập phương trình đặc trưng, tìm nghiệm tổng quát theo các trường hợp nghiệm
• Nghiệm bội: Nhân thêm lũy thừa của n vào nghiệm tổng quát
• Hệ thức không thuần nhất: Nghiệm = Nghiệm thuần nhất + Nghiệm riêng
• Ứng dụng: Fibonacci, Tháp Hà Nội, phân tích thuật toán, quy hoạch động

Hy vọng bài viết đã giúp bạn nắm vững kiến thức về hệ thức truy hồi và có thể áp dụng vào giải toán hiệu quả!