Tại sao phải chuyển các bài toán tổ hợp về hệ thức truy hồi bởi các lý do sau:

1. Tổ hợp rất dễ nhầm lẫn, hay bỏ sót
2. [You must be registered and logged in to see this link.]
Ở đây đưa ra một số bài toán mẫu, có thể áp dụng luôn cách làm vào các bài thi. Rất hay.

1. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có 3 bit 0 liên tiếp.
Đặt S_n là số chuỗi nhị phân độ dài n, có 3 bit 0 liên tiếp:
Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
A1 ( A là chuỗi có độ dài n -1, A chứa 3 bit 0 liên tục) , gọi số cách là S_(n-1)
B10 (B là chuỗi có độ dài n - 2, B chứa 3 bít 0 liên tục), gọi số cách là S_(n-2)
C100 (C là chuỗi có độ dài n - 3, C chứa 3 bít 0 liên tục, gọi số cách là S_(n-3)
D000 (D là chuỗi tùy ý dài n - 3), số cách tính được luôn là 2^(n-3)

Ta có công thức truy hồi:
S_n=S_(n-1)+S_(n-2)+S_(n-3)+2^(n-3)
Khởi tạo:
S₁ = S₂ = 0; S₃ = 1.

2. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n không có 3 bit 0 liên tiếp.
Đặt S_n là số chuỗi nhị phân độ dài n, không có 3 bit 0 liên tiếp:
Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
A1 (A là chuỗi có độ dài n - 1, không có 3 bit 0 liên tiếp), gọi số cách là S_(n-1)
B10 (B là chuỗi có độ dài n - 2, không có 3 bit 0 liên tiếp), gọi số cách là S_(n-2)
C100 (C là chuỗi có độ dài n - 3, không có 3 bit 0 liên tiếp), gọi số cách là S_(n-3)

Nên ta có hệ thức truy hồi:
S_n=S_n-1 + S_n-2 + S_n-3
Khởi tạo: S₁ = 2, S₂ = 4, S₃ = 7

3. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có chứa chuỗi con 01.

Đặt S_n là số chuỗi nhị phân có chứa chuỗi con 01 (*) ta suy ra ngay số chuỗi nhị phân không chứa chuỗi con 01 là 2ⁿ-S_n (**)
Chuỗi nhị phân có chứa chuỗi con 01, thuộc 1 trong 2 dạng:
Ax (A là chuỗi có độ dài n - 1, A chứa chuỗi con 01, x = 0 hoặc 1) gọi số cách là S_(n-1), nhưng do x có 2 trạng thái 0 và 1, nên nhớ phải nhân 2.
B01 (B là chuỗi có độ dài n - 2, B không chứa chuỗi 01) lập luận như (**) thì B là 2^(n-2)-S_n-2

Ta có hệ thức truy hồi:
S_n=2 S_n-1 + (2^(n-2)-S_n-2)
hay S_n = 2 S_n-1 - S_n-2 + 2^(n-2)
Giá trị khởi tạo: S₁ = 0;S₂ = 1

Thực ra S_n có thể tính dễ dàng không truy hồi như sau:
Chuỗi không thỏa mãn (*) chỉ có thể có dạng: 111...111000...000 số chuỗi thế này = n+1
Suy ra:
S_n=2ⁿ-(n+1)

4. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số cách đi lên n bậc thang nếu có thể đi 1, 2 hoặc 3 bước một lần.

Muốn bước lên tới bậc n(n>3) có 3 cách:
Bước tới bậc thứ n-1, rồi bước 1 bậc để lên n
Bước tới bậc thứ n-2 rồi bước 2 bậc để lên tới n
Bước tới bậc thứ n-3 rồi bước 3 bậc để lên tới n
Vậy ta xậy dựng được:
S_n = S_n-1 + S_n-2 + S_n-3
Khởi tạo:
S₁=1;
S₂=2;
S₃=3;

5. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có một số chẵn bit 0.
Gọi Sn là số chuỗi có số chẵn bit 0
Gọi Kn là số chuỗi có số lẻ bít 0
Ta có Sn + Kn = 2ⁿ
Một chuỗi dài n có số chẵn bit 0, được thành lập bằng 2 cách
* Chuỗi số chẵn bít 0 có độ dài n-1, thêm 1
* Chuỗi số lẻ bít 0 có độ dài n-1, thêm 0
Ta có hệ thức sau:
Sn=S_(n-1)+K_(n-1)

Tương tự ta có:
Kn = S_(n-1) + K_(n-1)
Suy ra: Sn = Kn
Hay hệ thức truy hồi là:
Sn = 2S_(n-1)
Với giá trị khởi tạo :
S₁=1

[You must be registered and logged in to see this link.]

6. Tìm hệ thức truy hồi mà R_n thoả mãn, trong đó R_n là số miền của mặt phẳng bị phân chia bởi n đường thẳng nếu không có hai đường nào song song và không có 3 đường nào cùng đi qua một điểm.

Trên mặt phẳng có n (Với n>1) đường thẳng đôi một cắt nhau và không có 3 đường đồng quy. Ta thấy rằng cứ mỗi đường thẳng bị n - 1 đường còn lại chia làm n phần. Bởi vậy nếu ta bỏ đi một đường bất kì thì khi mất n phần này, 2 mặt miền 2 bên lập tức họp lại làm một, điều đó nghĩa là nếu bỏ đi 1 đường thẳng thì số miền bị mất đi là n:

Tức là
R_n = n + R_n-1,
R₁ = 2.
Giải hệ truy hồi này để dễ dạng có được công thức
R_n = n(n + 1)/2 + 1


7. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi ký tự gồm A, B, C có độ dài n chứa hai kí tự liên tiếp giống nhau.

Gọi S_n là số chuỗi thỏa mãn: Có chưa 2 kí tự liên tiếp giống nhau (*)
thì số chuỗi không thỏa mãn (*) là 3ⁿ - S_n
Chuỗi thỏa mãn có 1 trong 2 dạng:

* Mx (M thỏa (*), x có 3 cách)
* Nxx (Nx không thỏa (*))

→ S_n = 3 S_n - 1 + (3^n-1 - S_n - 1) = 2 S_n - 1 + 3^n-1

Khởi tạo: S₁ = 0,
S₂ = 3

Có thể giải không truy hồi như sau:

Đầu tiên tìm số chuỗi không có 2 kí tự liên tiếp bằng nhau:
Chọn kí tự đầu tiên có 3 cách, kí tự tiếp theo có 2 cách (Trừ kí tự trước nó)
Vậy tất cả có: 3. 2^n-1 cách
→ S_n = 3ⁿ - 3. 2^n-1

8. Cho dãy S = {Sn}, S_n là số chuỗi n bit không chứa mẫu 00.
a) Tìm hệ thức truy hồi và các điều kiện khởi tạo cho dãy {Sn}
b) Chứng tỏ S_n = f_n+1, n = 1, 2, … với f là dãy Fibonacci.

Giải

a) Chuỗi dài n thỏa mãn không chứa 00 thì có một trong 2 dạng
* A1 (A không chứa mẫu 00)
* B10 (B không chứa mẩu 00)

Vậy có hệ thức truy hồi:
S_n = S_n-1 + S_n-2
S₁ = 2 (0;1),
S₂ = 3 (01;10;11)

b)
Quy nạp:

S₁ = f₂; S₂ = f₃ đúng.

Giả sử đúng đến n - 1
tức là S_k = f_k+1, mọi k = 1.. n - 1

→ S_n = S_n-1 + S_n-2 = f_n + f_n-1 = f_n+1

Vậy S_n = ff_n+1 mọi n = 1, 2, 3,..

9. Tìm hệ thức truy hồi và điều kiện khởi tạo cho số cách đóng cặp ngoặc đơn trong biểu thức
a₁ * a₂ * … * a_n, Với n ≥ 2.

Nếu chỉ có một ngoặc thì một cách đóng cho biểu thức dài n = a₁ * a₂ * … * a_n
Gọi công thức tính số cách đóng cặp ngoặc là S_n với n>2:

Một cách đóng sẽ có 1 trong 2 dạng
* Aan, với cặp ngoặc nằm trong A, A có độ dài n - 1, S_n-1 cách
* Aan), dấu mở ngoặc nằm ở A, có n - 1 cách.

→ S_n = S_n-1 + n - 1
S₂ = 1;
S₃ = 3
S₄ = 3 + 3 = 6

Giải hệ hồi quy dễ tính được
S_n = (n - 1) + (n - 2) +.. + 3 + 2 + 1 = n(n - 1)/2

Thực ra bài này có thể giải đơn giản, một cách đóng ngoặc chính là một tổ hợp chập 2 của n phần tử, đáp số là C_n² = n(n - 1)/2

10. Gọi a_n là số các chữ số 0 có trong các số tự nhiên từ 0 đến 10ⁿ - 1.
a)Chứng tỏ rằng a_n thoả mãn hệ thức truy hồi a_n = a(n - 1) + 9 * (n - 1) * 10^n-2
b)Biết giá trị đầu a₁ = 1, giải hệ thức truy hồi trên.

Giải

a)
Gọi Kn (n>0) là số các chữ số 0 có trong các số tự nhiên từ 10^n-1 đến 10ⁿ - 1 (Tức có đúng n chữ số, chữ số đầu tiên bên trái khác 0)
Ta sẽ đi chứng minh K_n = 9(N - 1). 10^n-2
Một số có n chữ số sẽ có dạng Ax, trong đó A có n - 1 chữ số và x = 0.. 9
K_n là số các số 0 trong các số dạng Ax
Số các số 0 trong Ax bằng 10 lần số các số 0 trong A cộng thêm các số 0 trong x.
Số các số 0 trong A thì bằng 10 lần số các số K_n-1 (Vì Ax, x có 10 cách chọn)
Số các số 0 ở dạng A0 thì bằng số các số dạng A, số đầu khác 0 nên số cách chọn là 9. 10^n-2

Vậy rốt cuộc ta có công thức:
K_n = 10. K_n-1 + 9. 10^n-2, từ đây dễ dàng quy nạp được
K_n = 9(n - 1). 10^n-2
(vì 10. 9(n - 2). 10^n-3 + 9. 10^n-2 = 9(n - 1). 10^n-3 )

Mặt khác a_n = A_n-1 + K_n
(chia từ 1 đến 10ⁿ - 1 thành 2 đoạn, từ 1 đến 10^n-1 - 1 và 10^n-1 đến 10ⁿ - 1. )

Vậy ta có hệ thức truy hồi:
A_n = A_n-1 + 9(N - 1). 10^n-2

b) Ta có:
a_n = 9(n - 1). 10^n-2 + 9(n - 2). 10^n-3 +... + 9. 1. 10^o + A_o (A_o = 1)
xⁿ - 1 = (x - 1) (x^n-1 + x^n-2 +... + x² + x + 1)
(xⁿ - 1)/(x - 1) = (x^n-1 + x^n-2 +... + x² + x + 1)

Đạo hàm 2 vế

(n. x^n-1. (x - 1) - (xⁿ - 1))/(x - 1)²
= (n - 1… + (n - 2). x^n-3 +... + 2x + 1

Thay x = 10 ta có:
(n. 10^n-1. 9 - (10ⁿ - 1))/9² = (n - 1). 10^n-2 + (n - 2). 10^n-3 +.. + 2. 10 + 1
→ a_n = (n. 10^n-1. 9 - (10ⁿ - 1))/9 + 1
= n. 10^n-1 - (10ⁿ - 1)/9 + 1

11. Gọi a_n là số dãy bit độ dài n không có 2 bit 0 kề nhau.
a)Tìm hệ thức truy hồi cho a_n
b)Biết giá trị đầu a₁ = 2, a₂ = 3, giải hệ thức truy hồi trên.

Một dãy độ dài n không có 2 bit 0 kề nhau thì có 1 trong 2 dạng
* A10 (A có n - 2 bit và không có 2 bit 0 kề nhau)
* B1 (B có n - 1 bít và không có 2 bit 0 kề nhau)

Vậy suy ra
a_n = a(n - 1) + a(n - 2)
a₁ = 2;
a₂ = 3

Dãy này bắt đầu từ a₁ = 2 là dãy Fibonaci
Giải truy hồi bằng cách xét nghiệm của phương trình đặc trưng
x² = x + 1
x₁ = (1 + √5)/2;
x₂ = (1 - √5)/2
a_n = c₁. x₁ⁿ + c₂. x₂ⁿ

Thay n = 1, 2 vào tìm c₁, c₂ (Khách viếng thăm tự thực hiện)

12. Gọi a_n là số dãy bit độ dài n có 2 bit 0 kề nhau.
a) Tìm hệ thức truy hồi cho a_n
b) Biết giá trị đầu a_o = 0 và a₁ = 0, tính số dãy bit độ dài 7 có 2 bit 0 kề nhau.

a)Một số có 2 bít 0 kề nhau thuộc 1 trong 3 dạng
* A00 (A bất kì dài n - 2, số trường hợp là 2^n-2)
* B10 (B chứa 2 bít 0 liền nhau dài n - 2, số trường hợp là a_n-2)
* C1 (C chứa 2 bít 0 liền nhau dài n - 1, số trường hợp là a_n-1)

Vậy
a_n = a_n-1 + a_n-2 + 2^n-2

b)
a_o = 0,
a₁ = 0
→ a₂ = 0 + 0 + 2⁰ = 1
→ a₃ = 1 + 0 + 2¹ = 3
→ a₄ = 3 + 1 + 2² = 8
→ a₅ = 8 + 3 + 2³ = 19
→ a₆ = 19 + 8 + 2⁴ = 43
→ a₇ = 43 + 19 + 2⁵ = 94

Bài thầy cho sát đề:
Cho dãy số xác định công thức truy hồi:
a_n + 4a_n-1 - 21a_n-2 = 5.3ⁿ với n ≥ 2 và a_o = 1, a₁ = 2.

1. Tính giá trị a₇
2. Tìm công thức tường minh biểu diễn a_n

Bài này ta làm phần 2 trước.
Ta viết lại công thức truy hồi cho giống tổng quát, làm cho dễ
a_n = - 4a_n-1+ 21a_n-2 + 5.3ⁿ (*)

Theo định lý 5.
Bước 1. Chia làm 2 phần ta có:
A_H = - 4a_n-1+ 21a_n-2
A_P = 5.3ⁿ

Bước 2. a_n^(h) là nghiệm của phương trình:
r² + 4r - 21 = 0 (*)
Hay → r₁ = 3, r₂ = -7.
Theo định lý 1 của Hệ thức truy hồi thì:
a_n^(h) = α₁(3)ⁿ + α₂(-7)ⁿ

Bước 3. Tìm nghiệm riêng a_n^(p)
- Xác định dạng của nghiệm riêng, do nghiệm riêng của phương trình (*) trùng với cơ số của AP 1 lần, nên nó phải có dạng : C.n.3ⁿ
- Do nghiệm riêng thoả mãn phương trình hồi quy của định lý 5, nên thay vào và biến đổi tương ứng ta có:
c.n.3ⁿ = (-4)c.(n-1).3^n-1 + 21c.(n-2).3^n-2 + 5.3ⁿ

Hay:
cn3ⁿ + 4c(n-1)3^n-1 - 21c(n-2)3^n-2 - 5.3ⁿ = 0;
Chia cả 2 vế cho 3^n-2 và chuyển c thành biến để tính sẽ được:
30c - 45 =0 → c = 3/2

Thay hệ số tìm được này vào dạng nghiệm riêng để có được a_n^(p). Ta có:
[You must be registered and logged in to see this image.]

Bước 4. Thông báo dạng nghiệm của hệ thức là dạng:
a_n = a_n^(h) + a_n^(p)
Thay kết quả của bước 3 vào.
Trường hợp cụ thể bài toán này ta có:
a_n = a_n^(h) + a_n^(p)
[You must be registered and logged in to see this image.]
Thay vào các giá trị đầu mà đề bài cho a_o = 1, a₁ = 2 để tính các α
a_o = 1 = α₁.3^o + α₂(-7)^o - 5.3^o + 0
a₁ = 2 = α₁.3¹ + α₂(-7)¹ - 5.3¹ + (1.3¹⁺¹)/2
Giải cái này ra được:
[You must be registered and logged in to see this image.]

Vậy kết quả cần tìm là:
[You must be registered and logged in to see this image.]

Việc thay n = 7 do Khách viếng thăm tự thực hiện.

Bạn nào nắm được căn cứ và cơ sở về nghiệm riêng của hệ thức truy hồi hồi quy không thuần nhất, định lý 5, thì nói rõ giúp 1 chút. Hiện tại chẳng biết căn cứ vào đâu để viết ra dạng nghiệm cả. Nhớ là căn cứ vào đâu. Yêu cầu thế nào, thì dạng nghiệm riêng thế nào. Được cái bảng tổng kết là tốt nhất. Google trên mạng chưa tìm thấy cái này. Các bạn Phan Việt, Phan Thị, Hà Thị, Mai Đình, Phan Quốc, Phạm Thái... kiểm tra xem ở Học viện KTQS đang căn cứ vào đâu để tính cái nghiệm riêng này nhé! Tài liệu ý. Thanks trước.

Thanks LĐS đã có buổi làm việc chi tiết về vấn đề nghiệm riêng của hệ thức truy hồi hồi quy không thuần nhất, định lý 5. Đã cập nhật trong [You must be registered and logged in to see this link.].

tren mot so tai leu khac bai giai cuoi cung tren co ket qua anfa 1= 1; anfa2 = 0 nhung o day ket qua lon vay.