Tài liệu bồi dưỡng học sinh giỏi Máy tính bỏ túi - Dạng toán về dãy truy hồi (phibonacci)

DẠNG TOÁN VỀ DÃY TRUY HỒI
(Phibonacci)
Bài 1: Cho dãy số: u1 = 2 ; u2 = 20, un+1 = 2un + un-1 ( n= 2; 3 )
a) Tính u3 ; u4 ; u5 ; u6 ; u7
b) Viết quy trình bấm phím liên tục để tính các giá trị của un với 
u1 = 2 ; u2 = 20, un+1 = 2un + un-1 ( n= 2; 3 )
	c) Sử dụng quy trình trên, tính giá trị của u22 ; u23 ; u24 ; u25
Bài 2: cho dãy số u0 = 2 ; u1= 10 ; un+1 = 10un – un-1 (n = 1, 2, 3 )
Lập một quy trình tính un+1 
Tính u2, u3, u4 , u5, u6
Tìm công thức tổng quát của un
Bài 3: Cho dãy số u0 = 2 ; u1 = 3 ; un+1 = un2 + un-12 
Lập quy trình tính un
Tính u2 , u3, u4 , u5.
Bài 4: Cho dãy số sắp thứ tự u1 , u2 , u3 , , un, un + 1. Biết u1 = 1; u2 = 2 ; u3 = 3 
và un = un – 1 + 2un – 2 + 3un – 3
Tính u4 , u5 ; u6 ; u7.
Viết quy trình bấm phím liên tục để tính giá trị của un với n 4
c) Sử dụng quy trình trên để tính giá trị của u22 , u25 ; u28 ; u30
Bài 5: Cho dãy số: Un = 
Tính 4 số hạng đầu tiên của dãy số.
Chứng minh: Un + 2 = 6Un + 1 – 4Un
Lập quy trình ấn phím liên tục tính Un + 2 trên máy Casio
Bài 6: Cho dãy số : Un = Với n = 1; 2; 3; .
Tính 6 số hạng đầu tiên của dãy.
Lập công thức truy hồi để tính Un + 2 theo Un và Un + 1
Lập quy trình ấn phím liên tục tính Un + 2 trên máy casio
Bài 7: Cho dãy số u1 = 8 ; u2 = 13 , un+1 = un + un-1 (n = 2; 3; 4 )
Lập quy trình bấm phím liên tục để tính giá trị un+1 với mọi n 2
Sử dụng quy trình trên tính giá trị u13 ; u17
Bài 8: Cho dãy số un = n = 0; 1; 2; 3 
Tính 8 số hạng đầu tiên của dãy số này.
Lập công thức truy hồi để tính un+2 theo un+1 và un
Lập một quy trình tính un trên máy casio
Tìm tất cả các số tự nhiên n để un chia hết cho 3
Bài 9: Cho dãy số un = n = 0; 1; 2; 3 
Tính 5 số hạng đầu tiên
Lập một công thức truy hồi để tính un+1 theo un và un-1
Lập một quy trình tính un+1 trên máy casio
Chứng minh rằng un = 5m2 khi n chẳn và un = m2 khi n lẻ
Bài 10: cho un với u1 = 0 ; u2 = 14 ; u3 = -18 và un+1 = 7un-1 – 6un-2 với n = 3; 4 
Lập công thức tính un và tính u4; u5 ; u6  u20
Lập và chứng minh công thức tổng quát của un
Chứng minh với mọi số nguyên tố p thì up chia hết cho p
Bài 11: Cho dãy số: un = (1)
Lập công thức truy hồi.
Lập quy trình tính trên máy casio để tính un và tính u1; u2 ; u3  u10
Bài 12: Cho dãy số un = 
Lập công thức truy hồi.
Lập công thức tính trên máy casio để tính un và tính u0 đến u4
Bài 13: Cho u1 = 1 ; u2 = 2 và dãy số được xác định
Nếu n chẳn: u2n+2 = 3u2n+1 + 5u2n - 1 
Nếu n lẻ : u2n+1 = 5u2n + 3u2n-1
a) Lập quy trình tính trên máy casio để tính u12, u13 , S12 ; S13
 (S12 bằng tổng các số hạng của dãy ứng n = 12) 
b) Tính u12 ; u13 và tính tổng S12 ; S13 
Chú ý1: Dãy số un = aun-1 + bun-2 (1) gọi là công thức truy hồi để tính un.
	 Dãy số : un = c1u1n + c2u2n (2) gọi là công thức tổng quát để tính của un
Công thức (1) và (2) cùng biểu diễn để tính giá trị của un và có quan hệ với nhau.
Ở công thức (2) u1 và u2 là nghiệm của phương trình: u2 = au + b hay u2 – au – b = 0
Do vậy nếu biết được công thức truy hồi ta tìm được công thức tổng quát và ngược lại.
HƯỚNG DẪN
	Ví dụ1: (Bài 2)
cho dãy số u0 = 2 ; u1= 10 ; un+1 = 10un – un-1 (n = 1, 2, 3 )
Tìm công thức tổng quát của un 
Giải: Công thức tổng quát có dạng: un = c1x1n + c2x2n 
Trong dó x1 và x2 là nghiệm của phương trình: x2 – 10x + 1 = 0 (*)
Giải pt (*) có x1 = ; x2 = 5 - 2
	un = c1()n + c2(5 - 2)n do u0 = 2 ; u1 = 10 nên ta có:
 c1 = c2 = 1
Vậy công thức tổng quát: un = ()n + (5 - 2)n 
	Ví dụ 2: (Bài 8)
Cho dãy số : Un = Với n = 0; 1; 2; 3; .
Lập công thức truy hồi để tính Un + 2 theo Un và Un + 1
	Giải: 
Cách 1: Ta biểu diễn Un dưới dạng tổng quát un = c1u1n + c2u2n như sau: 
Un = c1 =; c2 = -; u1 = 2+;u2 = 2-
Trong đó u1; u2 là nghiệm của pt: (u – 2-)(u – 2+) = 0 
Hay: u2 – 4u + 1 = 0 u2 = 4u – 1 
Vậy công thức truy hồi: un+2 = 4un + 1 - un với u1 = 1 ; u2 = 4
Cách 2: Đặt a = 2 + ; b = 2 - 
Ta có: un = an / 2- bn / 2 ; 
un + 2 = an(2 + )2 /2 – bn(2 - )2 / 2
 = an(4 + 4 + 3) / 2 - bn(4 - 4 + 3) /2
 = an (8 + 4 - 1)/2 - bn (8 - 4 - 1) / 2
 = 4an(2 + ) / 2 - 4bn(2 - ) / 2 - (an /2- bn/2 )
 = 4 un+1 - un
Vậy ta có công thức truy hồi: un+2 = 4un + 1 - un 
Chú ý 2: Để lập quy trình tính trên máy casio fx 570 MS có nhiều quy trình ta nên sử dụng theo quy trình sau là ngắn gọn nhất:
	Ví dụ 1: 
Cho dãy số: u1 = 2 ; u2 = 20, un+1 = 2un + un-1 ( n= 2; 3 )
 Viết quy trình bấm phím liên tục để tính các giá trị của un với 
u1 = 2 ; u2 = 20, un+1 = 2un + un-1 ( n= 2; 3 )
Giải: 2 /shift / sto A (gán u1 vào A)
 20 /shift / sto B (gán u2 vào B)
 Alpha /A / Alpha / = /2 /Alpha /B / + / Alpha / A / Alpha / :
 Alpha /B / Alpha / = /2 /Alpha /A / + / Alpha / B / Alpha / = (được u3) 
Lặp lại dấu “ =” ta được các số hạng tiếp theo .
	Ví dụ 2: Cho dãy số un = un – 1 + 2un – 2 + 3un – 3 Biết u1 = 1; u2 = 2 ; u3 = 3 
Viết quy trình bấm phím liên tục để tính giá trị của un với n 4
 1 /shift / sto A (gán u1 vào A)
 2 /shift / sto B (gán u2 vào B)
	3 /shift / sto C (gán u3 vào C)
 Alpha /A / Alpha / = /Alpha /C / + / 2 / Alpha / B / + / 3 /Alpha /A / Alpha /:
 Alpha /B / Alpha / = /Alpha /A / + / 2 / Alpha / C / + / 3 /Alpha /B / Alpha /:
 Alpha /C / Alpha / = /Alpha /B / + / 2 / Alpha / A / + / 3 /Alpha /C / Alpha / = (u4)
 Lặp lại dấu “ =” ta được các số hạng tiếp theo .
Ví dụ 3:
Cho u1 = 1 ; u2 = 2 và dãy số được xác định
Nếu n chẳn: u2n+2 = 3u2n+1 + 5u2n - 1
Nếu n lẻ : u2n+1 = 5u2n + 3u2n-1
a)Lập quy trình tính trên máy casio để tính u12 ; u13 ; S12 ; S13 (S12 bằng tổng các số hạng của dãy ứng n = 12) 
b) Tính u12 ; u13 và tính tổng S12 ; S13 
Giải : Thiết lập quy trình tính trên máy như sau.
Gán u1 = 1 vào A (lẻ) ( 1 /shift / sto/ A )
 u2 = 2 vào B (chẳn) (2 /shift / sto/ B)
 S2 = 3 vào C (3 /shift / sto /C)
Nhập: 
A = 5B + 3A : (u3) (Alpha/A/Alpha/=/5/Alpha/B/+/3/Alpha/A/Alpha /:/)
C = C + A : (S3) (Alpha/C/Alpha/=/Alpha/C/+/Alpha/A /:/) 
B = 3A + 5B - 1: (u4) (Alpha/B/Alpha/=/3/Alpha/A/+/5/Alpha/B/-/1/Alpha /:/)
C = C + B (S4) (Alpha/C/Alpha/=/Alpha/C/+/Alpha/B/=/=/=/=/ 
Ấn liên tiếp các dấu bằng: Lần 1 “=” (được u3)
 Lần 2 “=” (được S3)
 Lần 3 “=” (được u4)
 Lần 4 “=” (được S4) 
Lặp lại dấu “=” cứ thế ta tìm được dãy số theo chu kì: (u3, S3, u4, S4) ; (u5, S5, u6, S6) (u7, S7, u8, S8) .
Như vậy ta dễ dàng giải quyết được bài toán: 
u12 =11980248 ; S12 =15786430 ; u13 =69198729 ; S13 =84985159 
ĐÁP ÁN:
DẠNG TOÁN VỀ DÃY TRUY HỒI
Bài 1: a) u3 = 42 ; u4 = 104 ; u5 = 250 ; u6 = 604 ; u7 = 1458
1b) gán: 2 A ; 20 B ; ghi A = 2B + A : B = 2A + B ấn liên tục dấu “=” 
1c) u22 = 850268156 ; u23 = 1941675090 ; u24 = 4687618336; u25 = 11316911762
Bài 2: a) gán: 2 A ; 10 B ; ghi A = 10B - A : B = 10A - B ấn liên tục dấu “=”
b) u2 = 89 ; u3 = 970 ; u4 = 9602 ; u5 = 95050 ; u6 = 940898
c) CTTQ: có dạng Un = C1x1n + C2x2n trong đó x1 ; x2 là nghiệm pt: x2 = 10x – 1 (*)
 (*) có nghiệm: x1 = 5 + 2 ; x2 = 5 - 2 thay vào un ta tìm được c1 = c2 = 1
Vậy công thức tổng quát: un = (5 + 2)n + (5 - 2)n 
Bài 3: a) gán: 2 A ; 3 B ; ghi A = B2 + A2 : B = A2 + B2 ấn liên tục dấu “=”
b) u2 = 13 ; u3 = 178 ; u4 = 31853 ; u5 = 1014645293
Bài 4: a) gán: 1 A ; 2 B ; 3C ghi A = C + 2B + 3A : B = A + 2C + 3B :
C = B + 2A + 3C ấn liên tục dấu “=” được các số hạng tiếp theo của dãy
b) u22 = 53147701 ; u25 = 711474236 ; u28 = 9524317645 ; u30 = 53697038226
Bài 5: a) u0 = 0 ; u1 = ; u2 = 4 ; u3 = 21
b) Đặt a = 3 + ; b = 3 - ta có: un = ; un + 1 = 
un+2 = = 
 = = 6un + 1- 4un vậy: un+2 = 6un + 1- 4un 
c) gán: 0 A ; 3/2 B ; ghi A = 6B - 4A : B = 6A - 4B bấm “=” (được u2) = 
B6a) u1 = 2 ; u2 = 10,5 ; u3 = 35,75 ; u4 = 113,125 ; u5 = 354, 8125; u6 = 1118,34375
b) Chứng minh tương tự bài 5b ta có: un + 2 = 5un + 1 – 23/4un – 21/4
c) gán: 2 A ; 10,5 B ; ghi A = 5B – 23/4A – 21/4 : B = 5A – 23/4B – 21/4 bấm “=” (được u3) = =  (được các số hạng của dãy tiếp theo)
B7a) : gán: 8 A ; 13 B ; ghi A = B + A : B = A + B bấm “=” (được u2) = 
b) u13 = 2584 ; u17 = 17711
Bài 8: u1 = 1 ; u2 = 4 ; u3 = 15; u4 = 56; u5 = 209; u6 = 780; u7 = 2911; u8 = 10864
b) C/m tương tự bài 5b ta có: un+2 = 4un + 1 - un với u1 = 1 ; u2 = 4
c) gán: 1 A ; 4 B ; ghi A = 4B - A : B = 4A - B bấm “=” (được u3) = 
d) Để un chia hết cho 3 khi n = 3k
Bài 9: a) u0 = 0 ; u1 = 1 ; u2 = 5 ; u3 = 16 ; u4 = 45
b) Tương tự bài 5b ta lập được công thức truy hồi: un + 2 = 3un+1 – un + 2
c) gán: 0A ; 1 B ; ghi A = 3B – A + 2 : B = 3A – B + 2 bấm “=” (u2) = 
Bài 10: a) gán: 0A ; 14 B ; -18C ghi A = 7B –6A : B = 7C – 6B :
C = 7A – 6C bấm “=” (u4) = (u5) 
u4 = 98; u5 = -210; u6 = 794 ; u7 = -2058 ; u8 = 6818 ; u9 = -19170 ; u10 = 60074
u11 = -175098 ; u12 = 535538 ; u13 = -1586130 ; u14 = 4799354; u15 = -14316138
u16 = 43112258 ; u17 = - 129009090 ; u18 = 387682634 ; u19 = -1161737178; 
u20 = 3487832978 
10b) Công thức tổng quát có dạng: un = C1x1n + C2x2n + C3x3n (*)trong đó x1 ; x2 ; x3 là nghiệm của phương trình x3 = 7x – 6 x1 = 2; x2 = -3; x3 = 1 thay vào (*)
un = C12n + C2(-3)n + C3 Xét n = 1; n = 2 ; n = 3 ta tìm được C1 = C2 = C3 = 1
Vậy công thức tổng quát là: un = 2n + (-3)n + 1 
Chứng minh bằng phương pháp quy nạp: 
Bài 11: a) Tương tự bài 5b ta lập được: un + 2 = 10un+1 – 18un với u1 = 1; u2 = 10
b) gán: 1 A ; 10 B ; ghi A = 10B -18A : B = 10A - 18B bấm “=” ( u3) = 
u3 = 82; u4 = 640; u5 = 4924; u6 = 37720 ; u7 = 288568 ; u8 = 2206720; 
u9= 16872976; u10 = 129008800
Bài 12: a) Tương tự bài 5b ta lập được CT: un+2 = 3un+1 - un với u0 = 2 ; u1 = 3
b) gán: 2 A ; 3 B ; ghi A = 3B -A : B = 3A - B bấm “=” ( u2) = 
u2 = 7; u3 = 18 ; u4 = 47; u5 = 123
Bài 13: Gán u1 = 1 vào A (lẻ); u2 = 2 vào B (chẳn) ; S2 = 3 vào C 
Nhập: A = 5B + 3A : C = C + A : B = 3A + 5B - 1: C = C + B 
Bấm liên tiếp các dấu bằng: Lần 1 “=” (được u3)
 Lần 2 “=” (được S3)
 Lần 3 “=” (được u4)
 Lần 4 “=” (được S4) 
Lặp lại dấu “=” cứ thế ta tìm được dãy số theo chu kì: (u3, S3, u4, S4) ; (u5, S5, u6, S6) (u7, S7, u8, S8) .
Như vậy ta dễ dàng giải quyết được bài toán: 
u12 =11980248 ; S12 =15786430 ; u13 =69198729 ; S13 =84985159