BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

TRẦN THỊ THU HÀ

ỨNG DỤNG CÔNG THỨC TRUY HỒI
GIẢI TOÁN SƠ CẤP
Chuyên ngành: Phương pháp toán sơ cấp
Mã số : 60.46.01.13

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng – Năm 2015


Công trình được hoàn thành tại
ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến

Phản biện 1: TS. Phan Đức Tuấn
Phản biện 2: GS.TS. Lê Văn Thuyết

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn
tốt nghiệp Thạc sĩ Khoa học họp tại Đại Học Đà Nẵng vào
ngày 12 tháng 12 năm 2015.

Có thể tìm hiểu Luận văn tại:
- Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng
- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng




2
5. Ý nghĩa khoa học và thực tiễn của đề tài
Đề tài nghiên cứu tính ứng dụng của công thức truy hồi.
Giải quyết được các bài toán đặt ra từ thực tế.
6. Cấu trúc luận văn
Ngoài phần mở đầu và kết luận, luận văn được chia làm ba
chương:
Chương 1: Cơ sở lý thuyết
Chương 2: Công thức truy hồi
Chương 3: Ứng dụng công thức truy hồi giải toán sơ cấp


3
CHƯƠNG 1
CƠ SỞ LÝ THUYẾT
1.1. TỔNG QUAN VỀ TỔ HỢP
1.1.1. Sơ lược về lịch sử
1.1.2. Bài toán tổ hợp
a. Cấu hình tổ hợp và các dạng bài toán tổ hợp
Cho các tập hợp
,
,…,
. Giả sử là sơ đồ sắp xếp
các phần tử , , … ,
được mô tả bằng các quy tắc sắp xếp và
, , …,
là các điều kiện ràng buộc lên mỗi sắp xếp theo sơ đồ
. Khi đó mỗi sắp xếp các phần tử của , , … ,

( , )= .
+ Chỉnh hợp không lặp
Định nghĩa 1.2. Một chỉnh hợp không lặp chập của phần
tử khác nhau là một bộ có thứ tự gồm thành phần lấy từ phần tử
đã cho. Các thành phần không được lặp lại.
Số tất cả chỉnh hợp không lặp chập của phần
tử là
!
( , ) = . ( − 1). … . ( − + 1) =
.
( − )!
+ Hoán vị
Định nghĩa 1.3. Một hoán vị của phần tử khác nhau là một
cách sắp xếp thứ tự các phần tử đó.
Hoán vị có thể coi như trường hợp riêng của chỉnh hợp không
lặp chập của , trong đó = . Ta có số hoán vị là
( ) = !.
+ Tổ hợp
Định nghĩa 1.4. Một tổ hợp chập của phần tử khác nhau là
một bộ không kể thứ tự gồm thành phần khác nhau lấy từ phần
tử đã cho. Nói cách khác, ta có thể coi một tổ hợp chập của phần
tử khác nhau là một tập con có phần từ phần tử đã cho.
Gọi số tổ hợp chập của phần tử là ( , ), ta có
!
( , )=
.
! ( − )!
* Các cấu hình tổ hợp mở rộng
+ Hoán vị lặp
Định nghĩa 1.5. Hoán vị lặp là hoán vị trong đó mỗi phần tử

Giả sử có phần tử, trong đó có
phần tử kiểu 1,
phần
tử kiểu 2,…,
phần tử kiểu . Khi đó số các hoán vị phần tử của
là
!
P( ; , , … , ) =
.
! !… !
+ Tổ hợp lặp
Ví dụ 1.1. Giả sử ta có 3 đầu sách: Toán, Tin, Lý và mỗi đầu
sách có ít nhất 6 quyển. Hỏi có bao nhiêu cách chọn ra 6 quyển.
Định nghĩa 1.6. Tổ hợp lặp chập từ phần tử khác nhau là
một nhóm không phân biệt thứ tự gồm phần tử trích từ phần tử
đã cho, trong đó các phần tử có thể được lặp lại.
Định lý 1.2. Giả sử có phần tử khác nhau. Khi đó số tổ
( , ) là
hợp lặp chập từ phần tử của , ký hiệu
( , ) = ( + − 1, − 1) = ( + − 1, ).
* Hàm sinh
Định nghĩa 1.7. Cho dãy số thực ( ) = ( , , … ) và biến
. Khi đó hàm sinh ( ) của dãy ( , , … ) là biểu thức có dạng
với

( )=

Ví dụ 1.2. Hàm

+

∗ ( − ) + ∗ ( − )+ ⋯, ( ) = ,
( ) = , … }, )
để giải công thức truy hồi
( ) = ∗ ( − 1) + ∗ ( − 2) + ⋯ , (0) = , (1) = , …
1.2. PHƯƠNG TRÌNH SAI PHÂN
Định nghĩa 1.8. Phương trình sai phân tuyến tính cấp là một
hệ thức tuyến tính có dạng
( + )+
( + − 1) + ⋯ +
( ) = ( ),
(1.1)
trong đó , , … , là các hệ số của phương trình,
≠ 0, ( ) là
một hàm số theo .
Nếu ( ) ≡ 0 thì (1.1) có dạng
( + )+
( + − 1) + ⋯ +
( ) = 0.
(1.2)
và được gọi là phương trình sai phân tuyến tính thuần nhất cấp
với hệ số hằng.


7
Nếu ( ) ≠ 0 thì (1.1) được gọi là phương trình sai phân
tuyến tính không thuần nhất cấp với hệ số hằng.
Hàm số ( ) thỏa mãn (1.1) được gọi là nghiệm tổng quát
của phương trình sai phân tuyến tính (1.1).
Hàm số ( ) phụ thuộc tham số, thỏa mãn (1.2) được gọi là
nghiệm tổng quát của (1.2).

Ví dụ 2.2. Trên mặt phẳng kẻ đường thẳng sao cho không có
ba đường nào đồng quy và không có hai đường nào song song. Hỏi
mặt phẳng được chia làm mấy phần?
2.2.2. Giải công thức truy hồi tuyến tính hệ số hằng
a. Định nghĩa công thức truy hồi tuyến tính hệ số hằng
Định nghĩa 2.2
Công thức truy hồi tuyến tính hệ số hằng bậc có dạng
(!) = "# . $(% − 1) + &' . (() − 2) + ⋯ + *+ . ,(- − .) + /(0). (2.1)


9
Trong đó 12 , 34 , … , 56 là các hằng số, 78 ≠ 0 và 9(:) là hàm
số theo ? , @(1) = AB , … , C(D − 1) = EFGH .
Định nghĩa 2.3
Nếu I(J) = 0 thì (2.1) được gọi là công thức truy hồi tuyến
tính thuần nhất hệ số hằng bậc K.
Nếu L(M) ≠ 0 thì (2.1) được gọi là công thức truy hồi tuyến
tính không thuần nhất hệ số hằng bậc N.
b. Phương trình đặc trưng của công thức truy hồi tuyến tính
thuần nhất hệ số hằng
Xét công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc O
(2.2)
Q(R) = ST . U(V − 1) + WX . Y(Z − 2) + ⋯ + [\ . ](^ − _).
Khi đó
(2.3)
a b − cd . e fgh − ij . k lmn − ⋯ − op = 0.
gọi là phương trình đặc trưng của công thức truy hồi tuyến tính thuần

Nếu , , … , tương ứng là các nghiệm bội
,
,…,
của phương trình đặc trưng (2.3) thì nghiệm tổng quát của (2.2) có
dạng ( ) = ( ) + ( ) + ⋯ + ( ),
trong đó
( )=

,

+

,

. +

,

.

+ ⋯+

,

.

.

, ∀


hợp là
= + . , = − ( = −1) thì nghiệm tổng quát của
(2.5) có dạng ( ) = λ . ( . cos( ) + . sin( )),
trong đó
với

λ=

+

, tan

=

,

∈ − ;
,
2 2

, là các hằng số.
· Công thức nghiệm của công thức truy hồi tuyến tính thuần
nhất hệ số hằng bậc ba
Cho công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc
ba
( ) = . ( − 1) + . ( − 2)
(2.7)
+ . ( − 3),
trong đó , , là các hằng số và
≠ 0. Phương trình đặc trưng

* Nghiệm riêng của công thức truy hồi tuyến tính không
thuần nhất hệ số hằng bậc một
Công thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc
một có dạng
( ) = . ( − 1) + ( ),
(2.9)
trong đó ≠ 0, ( ) là hàm theo và ( ) ≠ 0.
Nghiệm đặc trưng của phương trình thuần nhất tương ứng của
(2.9) là = .
Định lý 2.8. Nếu ( ) là đa thức bậc của , ( ) = ( )
thì nghiệm riêng ( ) của (2.9) có dạng:
( )=
( ), nếu ≠ 1,
i.
( ), nếu = 1,
ii. ( ) = .
( ) là dạng đa thức bậc của .
trong đó
Định lý 2.9. Nếu ( ) = . ( , ≠ 0) thì nghiệm riêng
( ) của (2.9) có dạng:
( ) = . , nếu ≠ ,
i.
ii. ( ) = . , nếu = .
( ) là đa
Định lý 2.10. Nếu ( ) = ( ). ( ≠ 0) và
thức bậc của thì nghiệm riêng của (2.9) có dạng:


13
i.

hai có dạng
( ) = . ( − 1) + . ( − 2) + ( ),
(2.12)
trong đó ≠ 0, ( ) là hàm theo và ( ) ≠ 0. Phương trình đặc
trưng của (2.12) có dạng
(2.13)
− . − = 0.
Định lý 2.12
Nếu ( ) là đa thức bậc
của , ( ) = ( ) thì nghiệm
riêng ( ) của (2.12) có dạng:
( )=
( ), nếu (2.13) không có nghiệm = 1,
i.
( ), nếu (2.13) có nghiệm đơn = 1,
ii. ( ) = .
( ), nếu (2.13) có nghiệm kép = 1,
iii. ( ) = .
(n) là dạng đa thức bậc của .
trong đó
( ≠ 0) và
( ) là đa
Định lý 2.12. Nếu ( ) = ( ).
thức bậc của thì nghiệm riêng của (2.12) có dạng:
( ). , nếu (2.13) không có nghiệm = ,
i. ( ) =


14
( ). , nếu (2.13) có nghiệm đơn = ,

Xét công thức truy hồi tuyến tính không thuần nhất hệ số hằng
bậc (2.2),
i. Nếu ( ) là đa thức bậc và 1 là nghiệm đặc trưng bội
của công thức (2.2), thì (2.2) có nghiệm riêng dạng
( )=
. ,
+ . + . +⋯+ .
trong đó các hằng số , , … ,
được xác định bằng cách thế ( )
vào (2.2).
ii. Nếu ( ) = , là nghiệm đặc trưng bội của (2.2) thì
(2.2) có nghiệm riêng dạng
( )= . . ,


15
trong đó hằng được xác định bằng cách thế ( ) vào (2.2).
iii. Giả sử
( ) = ( ) + ( ) + ⋯ + ( ).
Trong trường hợp này ta tìm nghiệm riêng ( ) ứng với hàm
( ), = 1, 2, … , .
Khi đó nghiệm riêng ( ) có dạng
( ) = ( ) + ( ) + ⋯ + ( ).
d. Phương pháp tổng quát giải công thức truy hồi bằng
phương trình đặc trưng
* Công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc
( ) = . ( − 1) + . ( − 2) + ⋯ + . ( − )
Các bước giải như sau:
Bước 1. Giả sử công thức truy hồi tồn tại nghiệm dạng
( ) = . Tìm phương trình đặc trưng của công thức truy hồi dạng

Bước 1. Để tìm dãy số { }, ta xét hàm sinh sinh bởi dãy { } là
( )=

.

.

Bước 2. Dựa vào đặc điểm của dãy { } ta tìm được ( ).
Bước 3. Đồng nhất thức ta sẽ thu được dãy { }.
Ví dụ 2.4. Giải công thức truy hồi
=3
−2
;
= 1, = 5.
Ví dụ 2.5. Giải công thức truy hồi
=−
+2
+3 ;
= 2, = 4.
2.2.4. Giải công thức truy hồi bằng maple
Ví dụ 2.6. Giải công thức truy hồi
−2
−3
= −1+2 ;
= 1, = 0; ≥ 2.
Ví dụ 2.7. Giải công thức truy hồi
−1
−1
+
;

3.1.2. Các bài toán
Bài toán 3.1.1. (Bài toán tháp Hà Nội )
Có ba cọc 1, 2, 3. Ở cọc 1 có đĩa, kích thước khác nhau, xếp
chồng lên nhau sao cho đĩa nằm dưới lớn hơn đĩa nằm trên. Hãy
chuyển tất cả các đĩa từ cọc 1 sang cọc 3 với điều kiện mỗi lần chỉ
được chuyển một đĩa từ cọc này sang cọc khác và luôn đảm bảo đĩa
nằm dưới lớn hơn đĩa nằm trên. Hãy tính số lần di chuyển đĩa.
Bài toán 3.1.2. (Bài toán lãi suất ngân hàng)
Một người có 20000000 đồng Việt Nam, dự định của người này
gửi tiền vào tài khoản tiết kiệm của một ngân hàng với lãi suất là 5% trên
một năm. Hỏi số tiền của người ấy nhận được là bao nhiêu (cả gốc lẫn lãi)
sau 20 năm tiết kiệm? Tổng quát với số năm gửi là ( ≥ 1).
Bài toán 3.1.3.
Có người ngồi thành một hàng ngang vào chiếc ghế. Hỏi
có bao nhiêu cách lập hàng mới cho người đó mà trong mỗi cách


18
lập, mỗi người hoặc giữ nguyên vị trí của mình, hoặc đổi chỗ cho
người liền bên trái, hoặc đổi chỗ cho người liền bên phải.
Bài toán 3.1.4.
Trên mặt phẳng kẻ đường thẳng sao cho không có 3 đường
nào đồng quy và không có 2 đường nào song song. Tính số đa giác
được tạo thành.
Bài toán 3.1.5.
Trong một cuộc thi đấu thể thao có huy chương, được phát
trong ngày thi đấu. Ngày thứ nhất, người ta phát 1 huy chương và
huy chương còn lại. Ngày thứ hai, người ta phát 2 huy chương và
huy chương còn lại. Những ngày còn lại được tiếp tục và tương tự
như vậy. Ngày sau cùng còn lại huy chương để phát. Hỏi có tất cả

+( − )
;
= , =
+ .
Giải công thức truy hồi ta tìm được . Thay vào hệ ta tìm
được .
Bài toán 3.2.2. Tìm , thỏa mãn:
= 2;
=0
4 =2
−3
(3.5)
2 =2
+
c. Dãy số cho bởi công thức truy hồi là một biểu thức tuyến
tính với hệ số biến thiên
Việc giải công thức truy hồi với hệ số biến thiên rất phức tạp.
Trong phần này, ta chỉ xét một số bài toán được giải bằng phương
pháp đặt dãy số phụ.
Bài toán 3.2.3. Cho dãy số ( ) xác định bởi:
2
=
3
∀ ≥ 1.
=

mãn:

2 −2
Xác định công thức tổng quát của


)(

=

)

+ 1), ∀ ≥ 2.

)

(

( )
(
)

+ 1), ∀ ≥ 2.
;

trong đó ( − 1), ∀ ≥ 2, ∈ N ∗ cho trước.
d. Dãy số cho bởi công thức truy hồi dạng phân tuyến tính với hệ
số hằng


20
Dạng 3.2.1. Tìm số hạng tổng quát của dãy số (
= ,

=

=

, ∀ ≥ 2.

,∀ ≥ 2

Dạng 3.2.2. Tìm số hạng tổng quát của dãy số ( )cho bởi:
+
= , =
, ∀ ≥ 1,
+
trong đó , , , , là các số thực cho trước.
Bài toán 3.2.9. Tìm số hạng tổng quát của dãy số ( ) thỏa

mãn:
(

Dạng 3.2.3. Cho
) thỏa mãn:

, ∀ ≥ 1.

≥ 0. Tìm công thức tổng quát của dãy số

+

(3.13)
,∀ ≥ 2 .
2
e. Dãy số cho bởi công thức truy hồi dưới dạng khác


> 0,

, ∀ ≥ 2,

> 1.

) thỏa


21
Bài toán 3.2.12. Tìm số hạng tổng quát của dãy số (
với

= ,

= ,

=

+

, ∀ ≥ 3,

) thỏa mãn:

∈ R; , ∈ R∗ .
Bài toán 3.2.13. Tìm số hạng tổng quát của dãy số ( ) thỏa mãn:
= , =
+2

2
=
3
∀ ≥ 2.
=

2(2 − 1)
+1
Tính tổng của 2001 số hạng đầu tiên của dãy ( ).
3.3. ỨNG DỤNG TRONG SỐ HỌC
Bài toán 3.3.1.
Cho dãy số ( ) xác định bởi:
= 1,
= 2,
=2
−
+ 2 với mọi ≥ 3.
Chứng minh rằng: ∀ , .
cũng là một số hạng của dãy số.


22
Bài toán 3.3.2. Cho dãy số ( ) thỏa mãn
= 1,
= 0,
=2
−
+ 2, ∀ ≥ 2
Chứng minh
là một số chính phương.

= 0,
ii. Với mọi ≥ 3,
( − 5 + 7)( − 2)
=
+ ( − 5 + 7)
−3
−2
−
.
+3
Chứng minh
là số chính phương với mọi ≥ 0.
3.4. ỨNG DỤNG GIẢI PHƯƠNG TRÌNH SAI PHÂN
Việc giải phương trình sai phân thực chất là giải công thức
truy hồi.
Bài toán 3.4.1. Giải phương trình sai phân
= 17
= 2 − + 2 + 1 + 6. 2 .


23

Bài toán 3.4.2. Giải phương trình sai phân
= 1;
=1
2
−5
+ 2 =
− 2 + 3.
3.5. ỨNG DỤNG TÍNH TÍCH PHÂN


, =
.
24
48
Bài toán 3.6.2. Tính tích phân
=

cos

. cos(

)

,

=

( ∈ N ∗ ).