Công thức truy hồi trong toán học: Cách thành lập và cách giải

DISCRETE MATHEMATICS / COMPUTER SCIENCE

Công thức truy hồi trong toán rời rạc: cách lập từ bài toán

a[n] = f(a[n-1], a[n-2], ...)

Trong toán rời rạc, nhiều bài toán không xác định trực tiếp giá trị ở trường hợp thứ n, mà mô tả cách xây dựng nó từ những trường hợp nhỏ hơn. Mối quan hệ đó được biểu diễn bằng công thức truy hồi (recurrence relation), một công cụ nền tảng trong tổ hợp, thiết kế thuật toán và lập trình động.

Tóm tắt nội dung

Muốn lập công thức truy hồi đúng, không nên bắt đầu bằng việc đoán công thức. Hãy xác định rõ đại lượng cần tính, chia lời giải theo bước cuối cùng hoặc trạng thái cuối cùng, biểu diễn mỗi trường hợp bằng những bài toán nhỏ hơn rồi bổ sung điều kiện đầu. Phần lớn sai sót xuất phát từ việc bỏ sót trường hợp, đếm trùng hoặc chọn sai trạng thái.

Minh họa: một trạng thái mới được xây dựng từ các trạng thái nhỏ hơn.

```

1. Công thức truy hồi thực chất là gì?

Giả sử ta có một dãy a<sub>0</sub>, a<sub>1</sub>, a<sub>2</sub>, .... Thay vì viết trực tiếp a<sub>n</sub> theo n, ta có thể xác định a<sub>n</sub> thông qua một hoặc nhiều phần tử đứng trước nó. Chẳng hạn:

a<sub>n</sub> = a<sub>n-1</sub> + 3

Công thức trên cho biết muốn tìm phần tử hiện tại, ta lấy phần tử ngay trước đó rồi cộng thêm 3. Tuy nhiên, chỉ có biểu thức này vẫn chưa đủ để xác định duy nhất dãy số. Ta còn cần ít nhất một điều kiện đầu, chẳng hạn a<sub>0</sub> = 2.

Khi đó ta lần lượt nhận được a<sub>1</sub> = 5, a<sub>2</sub> = 8, a<sub>3</sub> = 11. Như vậy, một định nghĩa truy hồi hoàn chỉnh thường gồm hai thành phần: quan hệ giữa trạng thái hiện tại và trạng thái trước, cùng với các giá trị khởi đầu.

Phân biệt quan trọng: công thức truy hồi trong toán rời rạc không phải là hồi quy trong học máy. Hồi quy (regression) dùng mô hình để ước lượng một đại lượng, còn truy hồi mô tả một đối tượng bằng chính những trường hợp nhỏ hơn của đối tượng đó.

2. Tư duy cốt lõi khi lập công thức truy hồi

Phần khó nhất không phải thao tác đại số mà là chuyển lời văn của bài toán thành các trạng thái nhỏ hơn. Một quy trình đáng tin cậy gồm bốn bước:

1. Xác định đại lượng cần tính. Đặt tên rõ ràng, chẳng hạn a<sub>n</sub> là số cách thực hiện một công việc với kích thước n.
2. Xét bước cuối hoặc lựa chọn đầu tiên. Đây thường là vị trí dễ chia bài toán thành những trường hợp không giao nhau.
3. Quy mỗi trường hợp về bài toán nhỏ hơn. Nếu một lựa chọn làm kích thước giảm từ n xuống n − 1, số phương án còn lại thường liên quan đến a<sub>n-1</sub>.
4. Xác định điều kiện đầu. Tính trực tiếp các trường hợp nhỏ nhất đủ để khởi động quan hệ truy hồi.

Điểm cần đặc biệt chú ý là các trường hợp dùng để cộng với nhau phải không bị đếm trùng. Nếu hai nhánh có thể dẫn tới cùng một cấu hình, phép cộng trực tiếp sẽ cho kết quả sai.

3. Ví dụ cơ bản: số cách bước lên cầu thang

Xét một cầu thang có n bậc. Mỗi lần ta được bước lên 1 bậc hoặc 2 bậc. Gọi a<sub>n</sub> là số cách đi từ mặt đất lên đúng bậc thứ n.

Thay vì cố gắng liệt kê toàn bộ đường đi, ta xét bước cuối cùng. Để đến bậc n, chỉ có hai khả năng:

• Bước cuối dài 1 bậc. Trước đó ta phải đang ở bậc n − 1, có a<sub>n-1</sub> cách.
• Bước cuối dài 2 bậc. Trước đó ta phải đang ở bậc n − 2, có a<sub>n-2</sub> cách.

Hai trường hợp loại trừ nhau vì bước cuối không thể đồng thời dài 1 và 2 bậc. Do đó:

a<sub>n</sub> = a<sub>n-1</sub> + a<sub>n-2</sub>

Với cách quy ước tự nhiên, a<sub>0</sub> = 1 vì có đúng một cách để đi hết cầu thang có 0 bậc: không thực hiện bước nào. Đồng thời a<sub>1</sub> = 1. Từ đó a<sub>2</sub> = 2, a<sub>3</sub> = 3, a<sub>4</sub> = 5.

n	0	1	2	3	4	5
an	1	1	2	3	5	8

Ví dụ này cho thấy một nguyên tắc rất mạnh: hãy phân loại tất cả lời giải theo hành động cuối cùng. Sau khi cố định hành động cuối, phần còn lại thường trở thành một bài toán cùng loại nhưng có kích thước nhỏ hơn.

4. Từ lời văn đến công thức: ví dụ lát bảng

Giả sử cần lát một bảng kích thước 2 × n bằng các viên domino kích thước 2 × 1. Domino được phép đặt đứng hoặc đặt ngang. Gọi a<sub>n</sub> là số cách lát kín bảng.

Ta tập trung vào phần bên phải của bảng. Nếu viên cuối cùng đặt đứng, nó chiếm trọn một cột, còn lại bảng 2 × (n − 1), tạo ra a<sub>n-1</sub> cách.

Nếu không đặt đứng thì ô trên cùng bên phải phải thuộc một viên nằm ngang. Khi đó ô dưới nó cũng buộc phải ghép với một viên ngang khác. Hai viên này chiếm hai cột cuối, còn lại bảng 2 × (n − 2), tương ứng a<sub>n-2</sub> cách.

a<sub>n</sub> = a<sub>n-1</sub> + a<sub>n-2</sub>,   n ≥ 2

Điều kiện đầu là a<sub>0</sub> = 1 và a<sub>1</sub> = 1. Đáng chú ý, bài toán cầu thang và bài toán lát bảng có nội dung hoàn toàn khác nhau nhưng dẫn đến cùng dạng truy hồi. Công thức truy hồi vì thế phản ánh cấu trúc toán học của bài toán chứ không phụ thuộc vào câu chuyện mô tả bên ngoài.

5. Khi công thức có hệ số hoặc nhiều nhánh hơn

Không phải mọi truy hồi đều có dạng a<sub>n</sub> = a<sub>n-1</sub> + a<sub>n-2</sub>. Hệ số xuất hiện khi một trạng thái nhỏ có thể được mở rộng theo nhiều cách khác nhau.

Ví dụ, giả sử ta muốn đếm số chuỗi độ dài n tạo từ các ký hiệu A, B, C mà ký tự cuối được phân thành hai nhóm. Nếu từ mỗi chuỗi hợp lệ độ dài n − 1 có đúng hai cách bổ sung ký hiệu mà vẫn thỏa điều kiện, phần đó sẽ đóng góp 2a<sub>n-1</sub>, không phải chỉ a<sub>n-1</sub>.

Quy tắc kiểm tra: nếu một nhánh truy hồi có hệ số k, phải giải thích được vì sao mỗi trạng thái nhỏ tương ứng chính xác với k lựa chọn ở trạng thái hiện tại.

Một lỗi phổ biến là nhìn vài giá trị đầu rồi đoán quan hệ. Cách này có thể phát hiện quy luật nhưng không chứng minh được công thức. Một công thức truy hồi đáng tin cậy phải xuất phát từ việc phân hoạch tập lời giải thành các trường hợp rõ ràng.

6. Công thức truy hồi trong phân tích thuật toán

Trong khoa học máy tính, truy hồi còn được dùng để mô tả thời gian chạy của thuật toán đệ quy. Chẳng hạn, thuật toán tìm kiếm nhị phân chỉ tiếp tục xử lý khoảng một nửa dữ liệu sau mỗi bước. Nếu T(n) là thời gian chạy với n phần tử, ta có thể mô tả:

T(n) = T(n/2) + c

Trong đó c biểu diễn lượng công việc gần như cố định ở mỗi bước, chẳng hạn so sánh phần tử cần tìm với phần tử giữa. Sau khoảng log<sub>2</sub>n lần chia đôi, kích thước bài toán giảm xuống 1. Vì vậy thời gian chạy có bậc logarit.

Với sắp xếp trộn, mỗi bài toán kích thước n được chia thành hai bài toán kích thước n/2 và cần thêm lượng công việc tỷ lệ với n để trộn kết quả:

T(n) = 2T(n/2) + cn

Ở đây hệ số 2 xuất hiện vì thuật toán tạo ra hai bài toán con. Thành phần cn là công việc thực hiện ngoài hai lời gọi đệ quy. Khi lập truy hồi cho thuật toán, cần tách rõ số bài toán con, kích thước từng bài toán con và chi phí xử lý tại mức hiện tại.

Ví dụ mô phỏng truy hồi bằng Python

Đoạn mã sau tính số cách bước lên cầu thang. Ta dùng hai giá trị trước đó thay vì gọi đệ quy trực tiếp, nhờ vậy tránh tính lặp cùng một trạng thái nhiều lần.

Python

def so_cach(n):
    if n < 0:
        return 0
    if n <= 1:
        return 1

```
truoc_hai, truoc_mot = 1, 1

for _ in range(2, n + 1):
    hien_tai = truoc_mot + truoc_hai
    truoc_hai, truoc_mot = truoc_mot, hien_tai

return truoc_mot
```

print(so_cach(5))  # 8

Kết quả bằng 8 vì công thức là a<sub>n</sub> = a<sub>n-1</sub> + a<sub>n-2</sub> với a<sub>0</sub> = a<sub>1</sub> = 1. Thuật toán chỉ giữ hai trạng thái cần thiết nên dùng bộ nhớ hằng số.

7. Cách kiểm tra một công thức truy hồi đã lập đúng hay chưa

Sau khi lập công thức, nên kiểm tra bằng các trường hợp nhỏ trước khi giải hoặc lập trình. Đây là bước đơn giản nhưng phát hiện được phần lớn lỗi mô hình hóa.

• Kiểm tra ý nghĩa trạng thái: a<sub>n</sub> phải có một định nghĩa duy nhất và không thay đổi trong quá trình suy luận.
• Kiểm tra tính đầy đủ: mọi lời giải hợp lệ phải rơi vào ít nhất một trường hợp đã xét.
• Kiểm tra không đếm trùng: một lời giải không được xuất hiện ở hai nhánh khác nhau nếu ta cộng số lượng các nhánh.
• Kiểm tra điều kiện đầu: phải có đủ số giá trị để tính được trạng thái tiếp theo.
• Kiểm tra bằng tay: tính n = 0, 1, 2 hoặc 3 trực tiếp rồi đối chiếu với công thức.

Nếu công thức dùng a<sub>n-1</sub> và a<sub>n-2</sub>, thông thường ta cần hai điều kiện đầu độc lập. Nếu dùng tới a<sub>n-3</sub>, có thể cần ba giá trị khởi đầu. Số điều kiện đầu không nên được chọn tùy ý mà phải đủ để quan hệ truy hồi xác định được các giá trị tiếp theo.

Mẫu tư duy nên nhớ

Đặt a<sub>n</sub> là đại lượng cần tìm → chọn một đặc điểm để chia toàn bộ lời giải thành các trường hợp → đưa từng trường hợp về a<sub>n-1</sub>, a<sub>n-2</sub>, ... → cộng hoặc kết hợp các trường hợp → xác định điều kiện đầu → kiểm tra với vài giá trị nhỏ.

Kết luận

Lập công thức truy hồi là quá trình tìm ra cấu trúc lặp bên trong bài toán. Cách tiếp cận hiệu quả nhất là định nghĩa trạng thái chính xác, phân chia lời giải theo bước đầu hoặc bước cuối, rồi quy từng nhánh về những trạng thái nhỏ hơn.

Khi đã hình thành được tư duy này, công thức truy hồi không chỉ giúp giải các bài toán đếm trong toán rời rạc mà còn trở thành nền tảng để hiểu đệ quy, lập trình động và phân tích độ phức tạp của nhiều thuật toán quan trọng.