Bài giảng Toán rời rạc - Chương: Công thức truy hồi - Trần Vĩnh Đức

 Công thức truy hồi
 Trần Vĩnh Đức
 HUST
Ngày 24 tháng 7 năm 2018
 1 / 45
Nội dung
 Ví dụ
 Công thức truy hồi
 Công thức truy hồi và hàm sinh
 Số Catalan
 Công thức truy hồi tuyến tính
Ví dụ
Một quần thể vi trùng có số lượng cá thể tăng gấp đôi sau mỗi giờ.
Nếu thoạt đầu có 5 cá thể hỏi sau 5 giờ số lượng của chúng là bao
nhiêu?
 {
 an = 2an−1
 a0 = 5
 3 / 45
Bài tập
Hãy tìm công thức tường minh cho dãy
 {
 an = 2an
 a0 = 5
 4 / 45
Ví dụ
Xét một cầu thang với n bậc thang. Có bao nhiêu cách để đi lên
cầu thang nếu chúng ta có thể leo lên 1 bậc hoặc 2 bậc trong mỗi
bước?
 S1 = 1
 S2 = 2
 Sn+2 = Sn+1 + Sn với n ≥ 1
 5 / 45
Ví dụ
Có bao nhiêu xâu nhị phân độ dài n không chứa hai bit 0 liên tiếp?
 
 an+1 = an + an−1
 a = 2
  1
 a2 = 3
 6 / 45
Bài tập
Hãy dùng kỹ thuật hàm sinh để tìm công thức tường minh cho dãy
 
 an+1 = an + an−1
 a = 2
  1
 a2 = 3
 7 / 45
Ví dụ
Có bao nhiêu xâu tam phân độ dài n không chứa dãy con ”012”?
 
 an+3 = 3an+2 − an
 a = 3
  1
 a2 = 9
 8 / 45
Nội dung
 Ví dụ
 Công thức truy hồi
 Công thức truy hồi và hàm sinh
 Số Catalan
 Công thức truy hồi tuyến tính
Công thức truy hồi
 Định nghĩa
 Công thức truy hồi đối với dãy số ⟨an⟩ là công thức biểu diễn an
 qua một hay nhiều số hạng đi trước của dãy.
 10 / 45
Ví dụ
Xét dãy số ⟨an⟩ thỏa mãn công thức
 {
 an = an−1 − an−2
 a0 = 3a1 = 5
Từ công thức truy hồi ta có
 a2 = a1 − a0 = 5 − 3 = 2
 a3 = a2 − a1 = 2 − 5 = −3
 11 / 45
Định nghĩa
Một dãy số được gọi là nghiệm của công thức truy hồi nếu các số
hạng của nó thỏa mãn công thức truy hồi này.
 12 / 45
Ví dụ
 ▶ Xét công thức truy hồi
 an = 2an−1 − an−2 với n ≥ 2.
 ▶
 Dãy số ⟨an⟩ với an = 3n có phải là nghiệm của hệ thức truy
 hồi trên hay không?
 ▶ n
 Còn dãy an = 2 ?
 ▶
 Còn dãy an = 5?
 13 / 45
Ví dụ
Giả sử một người gửi 10, 000 đô la vào tài khoản của mình tại một
ngân hàng với lãi kép 11% mỗi năm. Hỏi sau 30 năm anh ta có
bao nhiêu tiền trong tài khoản ngân hàng.
 {
 Pn = Pn−1 + 0.11Pn−1 = 1.11Pn−1
 P0 = 10, 000 đô la.
 14 / 45
Ví dụ
 ▶ Một hệ máy tính coi một xâu các chữ số hệ thập phân là một
 từ mã hợp lệ nếu nó chứa một số chẵn chữ số 0.
 ▶ Chẳng hạn, 1230407869 là hợp lệ, còn 120987045608 là
 không hợp lệ.
 ▶
 Giả sử an là số các từ mã độ dài n.
 ▶
 Hãy tìm công thức truy hồi cho an.
 n−1
 an = 9an−1 + (10 − an−1)
 n−1
 = 8an−1 + 10 .
 15 / 45
P1: JSN
WB00623-07 WB00623-Tucker October 28, 2011 12:25
 7.1 Recurrence Relation Models 285
 Is there some systematic way to enumerate the ways to climb four stairs that
breaks the problem into parts involving the ways to climb three or fewer stairs?
Clearly, once the first step is taken there are three or fewer stairs remaining to climb.
Thus we see that after a first step of one stair, there are a3 ways to continue the climb
up the remaining three stairs. If the first step covers two stairs, then there are a2 ways
to continue up the remaining two stairs. So a a a . We confirm that the values
 4 = 3 + 2
for a4, a3, a2 satisfy this relation: 5 3 2. This argument applies to the first step
when climbing any number of stairs,= as+ is shown in Figures 7.1b and 7.1c. Thus
an an 1 an 2.
 = − + −
 In Section 7.3 we obtain an explicit solution to this recurrence relation. The rela-
tion an an 1 an 2 is called the Fibonacci relation. The numbers an generated by
 = − + −
the Fibonacci relation with the initial conditions a0 a1 1 are called the Fibonacci
numbers. They begin 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,= 89. Fibonacci= numbers arise natu-
rally in many areas of combinatorial mathematics. There is even a journal, Fibonacci
Quarterly, devoted solely to research involving the Fibonacci relation and Fibonacci
numbers. Fibonacci numbers have been applied to other fields of mathematics, such as
numerical analysis. They occur in the natural world—for example, the arrangements
of petals in some flowers. For more information about the occurrences of Fibonacci
numbers in nature, see [1].
Example 3: Dividing the Plane
Suppose we draw n straight lines on a piece of paper so that every pair of lines intersect
(but no three lines intersect at a common point). Into how many regions do these n
lines divide the plane?
 Again we approach the problem initially by examining the situation for small
values of n. With one line, the paper is divided into two regions. With two lines,
we get four regions—that is, a2 4. See Figure 7.2a. From Figure 7.2b, we see that
a 7. The skeptical reader may= ask: how do we know that three intersecting lines
3 =
will alwaysVí create dụ seven regions? Let us go back one step, then.
 Clearly two intersecting lines will always yield four regions, as shown in Figure
7.2a. Now▶ let usChúng examine ta vẽ then effectđường of thẳng drawing trên the giấy third sao line cho (labeled mọi cặp “3” đường in Figure
7.2b). It must crossthẳng each đều of cắt the nhau other và two không lines có(at badifferent đường points). thẳng Before, nào đồng between,
and after thesequy. two intersection points, the third line cuts through three of the regions
formed by the▶ firstCác two đường lines thẳng (this actionnày chia of the mặt third phẳng line thành does not bao depend nhiêu on miền? how it is
drawn, just that it intersects the other two lines). So in severing three regions, the third
line must form three new regions, actually creating six new regions out of three old
regions. Thus a a 3 4 3 7, independently of how the third line is drawn.
 3 = 2 + = + =
 2 2 3 2 3
 4
 1 1 1
Figure 7.2 (a) (b) (c)
 16 / 45
Ví dụ (Chọn không lặp)
Đặt an,k là số cách chọn tập con k phần tử từ tập n phần tử. Hãy
tìm công thức truy hồi cho ak,n.
 an,k = an−1,k + an−1,k−1 (Đẳng thức Pascal)
 17 / 45
Ví dụ (Bỏ bóng)
Hãy tìm công thức truy hồi cho số cách bỏ n quả bóng giống nhau
và k chiếc hộp phân biệt sao cho mỗi hộp chỉ có 2 hoặc 3 hoặc 4
quả bóng.
 an,k = an−2,k−1 + an−3,k−1 + an−4,k−1.
 18 / 45
Ví dụ (Hệ thức truy hồi)
Tìm công thức truy hồi cho: Số xâu tam phân độ dài n với một số
chẵn 0 và một số lẻ 1.
 an = bn−1 + cn−1 + an−1
 n−1
 bn = 3 − cn−1
 n−1
 cn = 3 − bn−1
 19 / 45
Nội dung
 Ví dụ
 Công thức truy hồi
 Công thức truy hồi và hàm sinh
 Số Catalan
 Công thức truy hồi tuyến tính
Ví dụ
Tìm hàm sinh cho dãy số là nghiệm của công thức truy hồi
 an = an−1 + n
 a0 = 1
 21 / 45
Ví dụ (Chọn không lặp)
Đặt gn(x) là họ các hàm sinh
 k n
 gn(x) = an,0 + an,1x + ··· + an,kx + ... an,nx
thỏa mãn công thức truy hồi
 an,k = an−1,k + an−1,k−1
 an,0 = an,n = 1
 an,k = 0 với mọi k > n
Hãy tìm dạng đóng cho hàm sinh gn(x) và dùng nó để tìm công
thức tường minh cho an,k.
 22 / 45
Giải
 ∑n ∑n
 k k k
 gn(x) − 1 = an,kx = (an−1,kx + an−1,k−1x )
 k=1 k=1
 ∑n ∑n−1
 k k
 = an−1,kx + x an−1,hx )
 k=1 h=0
 = gn−1(x) − 1 + xgn−1(x)
 Vậy ta được
 gn(x) = gn−1(x) + xgn−1(x) = (1 + x)gn−1(x)
 Giải công thức truy hồi trên, ta được
 n n
 gn(x) = (1 + x) g0(x) = (1 + x) .
 23 / 45
Nội dung
 Ví dụ
 Công thức truy hồi
 Công thức truy hồi và hàm sinh
 Số Catalan
 Công thức truy hồi tuyến tính
Số Catalan
Có bao nhiêu cách đặt dấu ngoặc cho tổng n số để chỉ định trình
tự thực hiện phép cộng?
Ví dụ
Với n = 4 ta có 5 khả năng:
 (((a + b) + c) + d)
 ((a + (b + c)) + d)
 ((a + b) + (c + d))
 (a + ((b + c) + d))
 (a + (b + (c + d)))
 25 / 45
Công thức truy hồi cho các số Catalan
 Cn = C1Cn−1 + C2Cn−2 + ··· + Cn−1C1
 ∑n−1
 = CiCn−i.
 i=1
Công thức này suy ra từ các cách đặt dấu ngoặc:
 (1 ... n) = (1)(2 ... n),
 (1 2)(3 ... n),
 ···
 (1 ... n − 1)(n).
Ta đặt C0 = 0 và ta biết C1 = 1.
 26 / 45
Công thức truy hồi cho các số Catalan
 Cn = C0Cn + C1Cn−1 + C2Cn−2 + ··· + Cn−1C1 + CnC0
 ∑n
 = CiCn−i.
 i=0
 27 / 45
Hàm sinh của số Catalan
 Xét hàm sinh của Cn:
 C(x) = 0 + x + x2 + 2x3 + 5x4 + ···
 ∑ ∑ ∑n
 n n
 = 0 + Cnx = (CiCn−i) x
 n≥1 n≥1 i=0
 Theo luật tích
 C(x)2 = C 2 + (C C + C C )x + (C C + C C + C C )x2 + ···
 0 0 (1 1 0 ) 0 2 1 1 2 0
 ∑ ∑n
 n
 = 0 + 0 + CiCn−i x
 n≥2 i=0
 = C(x) − x
 28 / 45
Hàm sinh cho các số Catalan
 Giải phương trình
 C(x)2 − C(x) + x = 0.
 Ta được
 √
 1  1 − 4x
 C(x) =
 2
 1  (1 − 4x)1/2
 = .
 2
 Vì C0 = 0, ta lấy nghiệm
 1 − (1 − 4x)1/2
 C(x) = .
 2
 29 / 45
Định lý nhị thức tổng quát
 Với số thực q bất kỳ, khai triển của chuỗi
 ( ) ( ) ( ) ( )
 q q q q
 (1 + y)q = + y + y2 + ··· + yn + ···
 0 1 2 n
 ( )
 q n
 có hệ số n của y được định nghĩa bởi
 ( )
 q q(q − 1)(q − 2) × · · · × [q − (n − 1)]
 := .
 n n!
 ( )
 q
 (Công thức cho hệ số tổng quát n xuất hiện từ chuỗi Taylor cho
 (1 + y)q.)
 30 / 45
Bổ đề
Với mỗi n ≥ 1,
 ( ) ( )
 n−1 2n−2
 1/2 (−1) −
 = × n 1
 n n 22n−1
 31 / 45
Định lý
Hàm sinh của dãy số Catalan là
 1 − (1 − 4x)1/2
 C(x) =
 2
 ∞ ( )
 ∑ 1 2n − 2
 = xn.
 n n − 1
 n=1
 32 / 45
Số Catalan
 ( )
 1 2n − 2
 C = .
 n n n − 1
 33 / 45
Bài tập
Xét bàn cờ n × n:
Xét đường đi ngắn nhất từ góc A tới góc B đi qua các cạnh (mỗi
đường qua 2n cạnh).
1. Có bao nhiêu đường như vậy?
2. Chứng minh rằng số đường không xuống dưới đường chéo
 chính là số Catalan C .
 n ( )
 1 2n−2
3. Hãy tìm cách chứng minh số Catalan Cn = n n−1 mà
 không dùng hàm sinh.
 34 / 45
Nội dung
 Ví dụ
 Công thức truy hồi
 Công thức truy hồi và hàm sinh
 Số Catalan
 Công thức truy hồi tuyến tính
Định nghĩa
Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng
là hệ thức truy hồi có dạng
 an = c1an−1 + c2an−2 + ··· + ckan−k
trong đó c1, c2,..., ck là các số thực và ck ≠ 0.
 36 / 45
Ví dụ
 ▶ Công thức truy hồi
 Pn = (1.11)Pn−1
 là tuyến tính thuần nhất bậc một.
 ▶ Công thức
 fn = fn−1 + fn−2
 là tuyến tính thuần nhất bậc hai.
 37 / 45
Định lý
Cho c1, c2 là hai số thực. Giả sử phương trình
 2
 r − c1r − c2 = 0
có hai nghiệm phân biệt r1, r2. Khi đó dãy ⟨an⟩ là nghiệm của hệ
thức truy hồi
 an = c1an−1 + c2an−2
nếu và chỉ nếu
 n n
 an = α1r1 + α2r2
trong đó α1, α2 là các hằng số.
 38 / 45
Ví dụ
Tìm nghiệm của hệ thức truy hồi
 an = an−1 + 2an−2
với a0 = 2, a1 = 7.
 39 / 45
Bài tập
Hãy chứng minh định lý trước dùng hàm sinh.
 40 / 45
Định lý
Cho c1 và c2 là hai số thực và c2 ≠ 0. Giả sử phương trình
 2
 r − c1r − c2 = 0
có nghiệm kép r0. Khi đó dãy ⟨an⟩ là nghiệm của hệ thức truy hồi
 an = c1an−1 + c2an−2
nếu và chỉ nếu
 n n
 an = α1r0 + α2nr0
trong đó α1, α2 là các hằng số.
 41 / 45
Ví dụ
Tìm nghiệm của hệ thức truy hồi
 an = 6an−1 − 9an−2
với a0 = 1, a1 = 6.
 42 / 45
Bài tập
Hãy chứng minh định lý trước dùng hàm sinh.
 43 / 45
Định lý
Cho c1, c2,..., ck là các số thực. Giả sử phương trình
 k k−1
 r − c1r − · · · − ck = 0
có k nghiệm phân biệt r1, r2,..., rk. Khi đó dãy ⟨an⟩ là nghiệm
của hệ thức truy hồi
 an = c1an−1 + c2an−2 + ··· + ckan−k
nếu và chỉ nếu
 n n n
 an = α1r1 + α2r2 + ··· + αkrk
trong đó αi là các hằng số.
 44 / 45
Ví dụ
Tìm nghiệm của hệ thức truy hồi
 an = 6an−1 − 11an−2 + 6an−3
với a0 = 2, a1 = 5 và a2 = 15.
 45 / 45