LÝ THUYẾT ĐỒ THỊ
4
CƠ SỞ LOGIC
1
QUAN HỆ
2
MỘT SỐ BÀI TOÁN CƠ BẢN
3
TOÁN RỜI RẠC
ĐẠI SỐ BOOLE
5
2 tiết
2 tiết
8 tiết
12 tiết
6 tiết
Chương
Chương
1
1
Chương
Chương
1
1:
CƠ SỞ LOGIC
Nguyên lý qui nạp toán học
1.2
Công thức truy hồi
1.3
1.1
Mệnh đề


!3
2
!2
1
) 



 n
nn
n
a
b) n
3
+ 11n chia hết cho 6, n  1
HD
a) Với n = 1:
2
1
)!11(
1
1,
2
1


 VPVT
1,
)!1(







 k
kk
k
k
k
Ta chứng minh (1) đúng với n = k+1, tức là cm:
)!2(
1
)!1(
1
1
)!2(
1
)!1(

!3
2
!2
1






Vậy:
1,
)!1(
1
1
)!1(

!3
2
!2
1




 n
nn
n
b) Đặt: P(n) = n
3
+ 11n
Với n = 1: P(1) = 1
3
+ 11.1= 12 chia hết cho 6
Giả sử:
Ta chứng minh (1) đúng với n = k+1, tức là cm:
))1(11)1(()1(
3
 kkkP
P(k) = (k

ĩ
a
a
Công thức truy hồi của dãy s
0
, s
1
, s
2
, … là công
thức xác định s
n
qua một hay nhiều số hạng đi
trước của dãy.
Điều kiện ban đầu là các giá trị gán cho một số
hữu hạn các phần tử đầu.
1.3 CÔNG THỨC TRUY HỒI
b. Dãy số Fibonacci được định nghĩa như sau:
f
n
= f
n-1
+ f
n-2
, với

n

2 & f
0

2. Giải công thức truy hồi
Giải CTTH bằng pp lặp là thay thế liên tiếp công
thức truy hồi vào chính nó, mỗi lần thay bậc n
giảm đi ít nhất một đơn vị, cho đến khi đạt giá trị
ban đầu.
Giải công thức truy hồi là tìm một công thức rõ
ràng cho s
n
mà không phải tính thông qua các
phần tử trước nó.
a. Giải công thức truy hồi bằng phương pháp lặp:
Bài toán : Tháp Hà Nội
Có 3 cọc a, b, c. Trên cọc a có n đĩa xếp chồng
lên nhau sao cho đĩa nhỏ trên đĩa lớn.
Cần chuyển chồng đĩa từ cọc a sang cọc c tuân
thủ quy tắc: Mỗi lần chỉ chuyển được một đĩa, luôn
đảm bảo đĩa nhỏ trên đĩa lớn, có thể sử dụng cọc b
làm trung gian.
Phương pháp di chuyển đĩa như sau:
 Chuyển n – 1 đĩa từ cọc a sang cọc b sử dụng
cọc c làm trung gian.
 Chuyển đĩa lớn nhất từ cọc a sang cọc c.
 Chuyển n – 1 đĩa từ cọc b sang cọc c sử dụng
cọc a làm trung gian.
Đếm số lần di chuyển của n đĩa trên?
Công thức truy hồi tính số lần di chuyển đĩa:
S
n
= 2.s
n-1

= c
1
s
1
+ c
2
s
2
+ + c
n
s
n
,
trong đó c
1
, c
2
, , c
k
là các số thực và c
k
 0.
Điều kiện đầu là:
s
0
= C
0
, s
1
= C

2
r
k-2
  c
k
= 0
có k nghiệm phân biệt r
1
, r
2
, , r
k
. Khi đó dãy {s
n
} là
nghiệm của hệ thức truy hồi (1) nếu:
s
n
= 
1
r
1
n
+ 
2
r
2
n
+ + 
k

2
– r – 1 = 0
có 2 nghiệm phân biệt:
2
51
r;
2
51
r
21




n
2
n
1n
2
51
2
51
f





































