intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Chuyên đề dãy số - Giải các hệ thức truy hồi

Chia sẻ: Nguyễn Minh Hải | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST
Báo xấu
8
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu "Chuyên đề dãy số - Giải các hệ thức truy hồi" trình bày các nội dung chính sau: Sơ lược về dãy số và quan hệ truy hồi trong toán học; Phương pháp giải hệ thức truy hồi; Giải các quan hệ truy hồi. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chuyên đề dãy số - Giải các hệ thức truy hồi

  1. VanHoa Chuyên dãy s - Gi i các h th c truy h i Copyright 2008 vanhoa Knowledge is power Chuyên I. S l c v dãy s và quan h truy h i trong toán h c Trong toán h c, dãy s là m t danh sách (h u h n ho c vô h n) li t kê các s theo m t th t nào ó. Quan h truy h i là m t ng th c bi u di n dãy s m t cách quy, m i ph n t c a dãy c xác nh b i m t hàm s c a các ph n t tr c. M t s quan h truy h i c xác nh m t cách n gi n có th có nh ng c tính h t s c ph c t p, th nh tho ng c nghiên c u b i các nhà v t lý h c và th nh tho ng l i c nghiên c u b i các nhà toán h c v m t l p c a toán h c c bi t n v i cái tên gi i tích phi tuy n. Ph n này khá ph c t p và không ng d ng nhi u ch ng trình THPT nên s không c c p chuyên này. M t cách t ng quát, h th c f ( n + k ) = g ( f (n + k − 1), f (n + k − 2),..., f (n + 1) ) (B.1) là m t h th c truy h i b c k. Công th c trên còn có th c viêt d i d ng: f n + k = g ( f n + k −1 , f n + k − 2 ,..., f n +1 ) Gi i m t h th c truy h i có ngh!a là tìm m t hàm s không quy theo bi n n n gi n nh t. II. Gi i h th c truy h i " chuyên này chúng ta s ch xét 4 ph ng pháp c b n: • Ph ng pháp th • Ph ng pháp quy n p • Ph ng pháp s d ng nghi m c tr ng • Ph ng pháp s d ng hàm sinh 1. Ph ng pháp th Trong ph ng pháp th gi i các h th c truy h i cho f (n) , s truy h i c a f (n) c s d ng l p i l p l i nhi u l n lo i b# m i giá tr c a f () v ph i. $ hi u rõ h n ph ng pháp này, ta hãy xét m t s ví d . Ví d II.1.1 Xét dãy s ( tn ) xác nh nh sau: c1 | n = 0 tn = * (II.1.1) c2 + tn −1 | n ∈ N u n > 2 thì tn −1 = c2 + tn − 2 , n u n > 3 thì tn − 2 = c2 + tn −3 ,… Nh ng ng th c này là h qu tr c ti p c a (II.1.1) và c dùng xác nh bi u th c không truy h i cho tn : tn = c2 + tn −1 = c2 + c2 + tn − 2 = c2 + c2 + c2 + tn −3 = ... = nc2 + t0 = nc2 + c1 , n ∈ Nên chúng ta có th th%y r&ng tn = nc2 + c1 , n ∈ vanhoa@lqdqt.com Trang 1 10/1/2008
  2. VanHoa Chuyên dãy s - Gi i các h th c truy h i Ví d II.1.2 Xét h th c truy h i: c | n =1 t (n) = n * (II.1.2) at + nc | n ∈ ,n ≥ 2 b v i n là l'y th(a c a b. Gi s r&ng n = bk , k ∈ . Gi i (II.1.2) b&ng ph ng pháp th cho ta: n t ( n ) = at + nc b n n = a at 2 + c + nc b b n a = a 2t 2 + nc + nc b b n n a = a 2 at 3 + c 2 + nc + 1 b b b 2 3 n a a = a t 3 + nc + nc +1 b b b 2 n n a a = a 3 at 4 + c 4 + nc + +1 b b b b 3 2 4n a a a = a t 4 + nc + + +1 b b b b = ... k −1 i kn a = a t k + nc b i =0 b k −1 i a = a k t (1) + nc i =0 b k −1 i k a = a c + nc i =0 b k k −1 i a a = nc + nc b i =0 b k i a = nc i= 0 b k +1 a k i k i −1 a a b Khi a = b , = k + 1 , khi a ≠ b , = . b b a i =0 i =0 −1 b vanhoa@lqdqt.com Trang 2 10/1/2008
  3. VanHoa Chuyên dãy s - Gi i các h th c truy h i nc ( k + 1) | a = b k +1 a V y, ta c: t ( n ) = −1 b , k = log b n nc |a ≠b a −1 b n Xét h th c + g (n) | n ∈ * t ( n ) = at (I.1.3) b v i a và b là nh ng h&ng s ã bi t. Gi s r&ng t (1) ã c bi t. Rõ ràng, (I.1.3) tr thành (I.1.2) khi t (1) = c và g ( n ) = nc . L i s d ng ph ng pháp th , ta có: n t ( n ) = at + g ( n) b n n = a at 2 +g + g ( n) b b n n = a 2t 2 + ag + g ( n) b b = ... k −1 n = a k t (1) + ai g i =0 bi V i k = logb n . $ ng th c này có th c làm n gi n h n nh sau: k −1 n t ( n ) = a k t (1) + ai g i=0 bi k −1 = a k t (1) + i=0 ( a g ( n )) i k −i k = a k t (1) + j =1 ( a g (b )) −j j Do a k = a logb n = n logb a , nên bi u th c cho t ( n ) tr thành: k t ( n ) = n logb a t (1) + j =1 ( a g (b )) −j j log b a k g (b j ) =n t (1) + j logb a j =1 (b ) k = n logb a t (1) + j =1 ( h (b )) j vanhoa@lqdqt.com Trang 3 10/1/2008
  4. VanHoa Chuyên dãy s - Gi i các h th c truy h i g (b j ) V i h (b j )= . V y cu i cùng bi u th c cho t ( n ) c a chúng la là t ( n ) = nlogb a ( t (1) + f ( n ) ) v i j logb a (b ) k f (n) = j =1 ( h (b )) . Xét m t s j tr )ng h p riêng c a (II.1.3): n g ( n) • a = 1, b = 2, g (n) = c cho ta t ( n ) = t + c , lúc này log b a = 0 và h ( n ) = logb a = c . T( công 2 n log b a th c trên, ta c t (n) = n ( t (1) + c log 2 n ) = t (1) + c log 2 n n • a = 7, b = 2, g ( n ) = 18n 2 cho ta t ( n ) = 7t + 18n 2 , lúc này log b a = log 2 7 và 2 18n 2 k 2 − log 2 7 h ( n) = log 2 7 = 18n 2 −log 2 7 , công th c cho t (n) là t ( n ) = nlog 2 7 t (1) + 18 ( 2 j ) n j =1 ( 2− log2 7 )( k +1) ( 2 −log 2 7 ) k j 2 −2 = n log 2 7 t (1) + 18 j =1 ( 2( 2 − log 2 7 ) ) = n log 2 7 t (1) + 18 2 ( 2−log 2 7 ) −1 . n 4n 6 • a = 9, b = 3, g ( n ) = 4n6 cho ta t ( n ) = 9t + 4n 6 , lúc này log b a = 2 và h ( n ) = 2 = 4n 4 , nên 3 n k 4 81log3 n +1 − 81 t ( n ) = n 2 t (1) + 4 (3 j ) = n 2 t (1) + j =1 20 2. Ph ng pháp quy n p Quy n p là m t ph ng pháp ki m tra h n là m t ph ng pháp gi i. Xét các ví d : Ví d II.2.1 Xét h th c truy h i 2|n = 0 tn = 3 + tn −1 | n ∈ * C s cho vi c quy n p là, khi n = 0, tn = 2 và 3n + 2 = 2. Gi s r&ng tm = 3m + 2, m ∈ , chúng ta s ch ng minh tm +1 = 3 ( m + 1) + 2 , i u này hi n nhiên úng theo h th c truy h i. Nh ã c c p trên, ph ng pháp quy n p không th dùng tìm ra l)i gi i cho m i h th c truy h i, nó ch có th dùng ki m tra tính úng *n m t h th c. 3. Ph ng pháp nghi m c tr ng H th c truy h i c a f ( n ) là m t ph ng trình truy h i tuy n tính n u và ch n u nó có d ng: k f (n) = gi ( n ) f ( n − i ) + g ( n ) i =1 v i gi ( n ) | i = 1, k và g ( n ) là các hàm s bi n n mà không ph i là hàm s bi n f. H th c truy h i xác nh nh trên là ph ng trình truy h i tuy n tính b c k, v i k là h&ng s và g k ( n ) ≠ 0 . N u g k ( n ) = 0, ∀n thì b c c a ph ng trình truy h i tuy n tính ó nh# h n k. M t ph ng trình truy h i tuy n tính v i h s h ng là ph ng trình có d ng: f ( n ) = a1 f ( n − 1) + a2 f ( n − 2 ) + ... + ak f ( n − k ) + g ( n ) , n ≥ k (II.3.1) V i ai | i = 1, n là h&ng s , g ( n ) là hàm s bi n n mà không ph i là hàm s bi n f. (II.3.1) là m t c a ph ng trình truy h i tuy n tính thu n nh t n u và ch n u g ( n ) ≡ 0 . Ph n l n các h tr c truy h i chuyên này ã c p n u là ph ng trình truy h i tuy n tính v i h s h ng. vanhoa@lqdqt.com Trang 4 10/1/2008
  5. VanHoa Chuyên dãy s - Gi i các h th c truy h i H th c (II.1.2): c | n =1 t (n) = n at + nc | n ∈ * , n ≥ 2 b v i n là l'y th(a c a b không ph i là m t ph ng trình truy h i tuy n tính b c k v i h&ng s k nào b i n vì s xu%t hi n c a t v ph i. Tuy nhiên, vì n là l'y th(a c a b nên (II.1.2) có th vi t l i: b c | n =1 t ( bk ) = at ( b k −1 ) + cb k | k ∈ * Dùng h(k ) bi u di n t ( b k ) , h th c trên tr thành: c | n =1 h (k ) = * ah ( k − 1) + c 2 k | k ∈ D th%y h th c trên là m t ph ng trình truy h i tuy n tính không thu n nh t b c 1 v i h s h ng. Do h(k ) = t ( b k ) = t ( n ) , vi c gi i h th c tuy n tính t ng ng v i vi c gi i h th c trên. H th c * t ( n ) = t ( n − 1) + t ( n − 2 ) | n ∈ ,n ≥ 2 Xác nh các s Fibonacci khi s d ng i u ki n t ( 0 ) = 0, t (1) = 1 . $ây là m t ph ng trình truy h i tuy n tính thu n nh t b c 2 v i h s h ng. Nh ng h th c trên có th c gi i b&ng cách tr c tiên xác nh m t nghi m chung cho t ( n ) . Nghi m chung này ch a m t s h s ch a xác nh và v i các giá tr c a t ( 0 ) , t (1) ,..., t ( k − 1) , chúng ta có th xác nh c các h s ch a xác nh ó. L%y ví d h th c t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) | n ∈ * , n ≥ 2 , nghi m chung c a nó là t ( n ) = c1 2n + c2 3n (chúng ta s tìm hi u cách tìm nghi m chung này sau), các d s ch a xác nh là c1 và c2 . N u t ( 0 ) = 0 và t (1) = 1 , chúng ta có th th vào t ( n ) = c1 2n + c2 3n xác nh c1 và c2 . Vi c này cho ta f ( 0 ) = c1 + c2 = 0 và f (1) = 2c1 + 3c2 = 1 Do ó c1 = 1, c2 = −1 . Vì v y, t ( n ) = 2n − 3n , n ≥ 0 là nghi m c a h th c t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) . Nghi m chung c a (II.3.1) có th bi u di n d i d ng t ng c a f h ( n ) và f p ( n ) , v i f h ( n ) là nghi m chung cho ph n thu n nh%t c a (II.3.1): f h ( n ) = a1 f h ( n − 1) + a2 f h ( n − 2 ) + ... + ak f h ( n − k ) , n ≥ k và f p ( n ) là nghi m riêng c a f p ( n ) = a1 f p ( n − 1) + a2 f p ( n − 2 ) + ... + ak f p ( n − k ) + g ( n ) , n ≥ k Nh n th%y r&ng f h ( n ) + f p ( n ) là m t nghi m c a (II.3.1). Do ph ng pháp ta s dùng xác nh f p ( n ) s cho chúng ta m t bi u th c f p ( n ) có th không ph i là nghi m c a ph ng trình f ( n ) . Nên vi c tìm f h ( n ) c ng vào f p ( n ) là i u c n thi t. vanhoa@lqdqt.com Trang 5 10/1/2008
  6. VanHoa Chuyên dãy s - Gi i các h th c truy h i Tìm f h ( n ) $ xác nh f h ( n ) chúng ta c n ph i gi i h th c tuy n tính d ng: f h ( n ) = a1 f h ( n − 1) + a2 f h ( n − 2 ) + ... + ak f h ( n − k ) Hay f h ( n ) − a1 f h ( n − 1) − a2 f h ( n − 2 ) − ... − ak f h ( n − k ) = 0 (II.3.1.1) Nh n th%y r&ng (II.3.1.1) có m t nghi m d ng f h ( n ) = Ax . Th vào (II.3.1.1), ta n c: A ( x n − a1 x n −1 − a2 x n − 2 − ... − ak x n − k ) = 0 Ta có th gi s A ≠ 0 , khi ó ta c k x n−k x k − ai x k −i = 0 i =1 Ph ng trình trên có n nghi m (trong ó có n – k nghi m là 0). K nghi m còn l i c a nó là nghi m c a ph ng trình x k − a1 x k −1 − a2 x k − 2 − ... − ak = 0 (II.3.1.2) Ph ng trình (II.3.1.2) g i là ph ng trình c tr ng c a (II.3.1.1) . Trong ph ong trình trên có úng k nghi m. Ta ch xét tr )ng h p nó có úng k nghi m trong . Nghi m c a ph ng trình c tr ng x2 − 5x + 6 = 0 là 2 và 3. Ph ng trình c tr ng x3 − 8 x 2 + 21x − 18 = 0 (II.3.1.3) có các nghi m là r1 = 2, r2 = 3, r3 = 3 , v i 3 là nghi m b i 2. Các nghi m phân bi t c a nó là 2 và 3. inh lý 1. Gi s các nghi m phân bi t c a ph ng trình c tr ng x k − a1 x k −1 − a2 x k − 2 − ... − ak = 0 c a h th c tuy n tính thu n nh t f h ( n ) = a1 f h ( n − 1) + a2 f h ( n − 2 ) + ... + ak f h ( n − k ) là t1 , t2 ,..., t s v i s ≤ k . T n t i m t nghi m chung c a f h ( n ) có d ng: f h ( n ) = u1 ( n ) + u2 ( n ) + ... + us ( n ) v i ( ui ( n ) = ci0 + ci1 n + ci2 n 2 + ... + ciw-1 n w−1 tin ) ây, ti là nghi m b i w. Ph ng trình c tr ng c a ph ng trình truy h i * t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) | n ∈ ,n ≥ 2 2 Là x − 5x + 6 = 0 Nghi m c a ph ng trình c tr ng này là 2 và 3. nh lý 1 cho ta t ( n ) = u1 ( n ) + u2 ( n ) v i u1 ( n ) = c1 2 , u2 ( n ) = c2 3 , Do ó, t ( n ) = c1 2 + c2 3 . n n n n (II.3.1.3) là ph ng trình c tr ng c a h th c truy h i thu n nh t sau: f ( n ) = 8 f ( n − 1) − 21 f ( n − 2 ) + 18 f ( n − 3) Ph ng trình ó có 2 nghi m phân bi t là r1 = 2 và r2 = 3 , v i r2 là nghi m b i 2. Nên, u1 ( n ) = c1 2n , và u2 ( n ) = ( c2 + c3 n ) 3n . Nghi m chung c a h th c truy h i trên là f ( n ) = c1 2n + ( c2 + c2 n ) 3n vanhoa@lqdqt.com Trang 6 10/1/2008
  7. VanHoa Chuyên dãy s - Gi i các h th c truy h i Dãy truy h i cho các s Fibonacci là thu n nh t và có ph ng trình c tr ng x 2 − x − 1 = 0 . Các nghi m c a n 1− 5 1+ 5 1− 5 nó là r1 = và r2 = . Do các nghi m này phân bi t, nên u1 ( n ) = c1 và 2 2 2 n 1+ 5 u2 ( n ) = c2 . Vì v y 2 n n 1− 5 1+ 5 F ( n ) = c1 + c2 2 2 Là nghi m chung c a dãy Fibonacci. S d ng i u ki n F ( 0 ) = 0 và F (1) = 1 , ta c c1 + c2 = 0 và 1− 5 1+ 5 1 1 c1 + c2 = 1 . Gi i cho c1 , c2 ta c c1 = − , c2 = . Nên các s Fibonacci thõa mãn 2 2 5 5 ng th c n n 1 1− 5 1 1+ 5 F (n) = − + 5 2 5 2 $ nh lý 1 cho chúng ta m t ph ng pháp n gi n xác nh nghi m chung c a b%t k+ h th c truy h i tuy n tính tu n nh t b c k v i h s h ng. Chúng ta ch c n xác nh các nghi m c a ph ng trình c tr ng c a nó, Tìm f p ( n ) Hi n ch a có ph ng pháp chung xác nh nghi m riêng f p ( n ) . Bi u th c c a f p ( n ) ph thu c r%t nhi u vào g ( n ) . Chúng ta ch xét 2 tr )ng h p: • g ( n ) là m t a th c bi n n • g ( n ) là hàm s m' theo bi n n Tìm f p ( n ) khi g ( n ) là a th c theo bi n n Khi g ( n ) = 0 , nghi m riêng f p ( n ) = 0 . d Khi g ( n ) = ei ni , ed ≠ 0 , nghi m riêng f p ( n ) có d ng i =1 f p ( n ) = p0 + p1n + p2 n 2 + ... + pd + m n d + m (III.3.2.1.1) V i m = 0 n u 1 không là nghi m c a ph ng trình c tr ng, và n u 1 là nghi m c a ph ng trình c tr ng thì m = k v i 1 là nghi m b i k c a ph ng trình c tr ng. $ xác nh p0 , p2 ,..., pd + m , ta th f p ( n ) vào h th c truy h i r i áp d ng tính ch%t c a ng nh%t th c. Xét ví d u ( n ) = 3u ( n − 1) + 6u ( n − 2 ) + 3n + 2 (III.3.2.1.2) Có g ( n ) = 3n + 2 , ph ng trình c tr ng c a nó là x 2 − 3 x − 6 = 0 . Ph ng trình này không có nghi m x = 1 nên m = 0 , nghi m riêng c a (III.3.2.1.2) có d ng f p ( n ) = p0 + p1n . Th vào (III.3.2.1.2), ta c: p0 + p1n = 3 ( p0 + p1 ( n − 1) ) + 6 ( p0 + p1 ( n − 2 ) ) + 3n + 2 = 3 p0 + 3np1 − 3 p1 + 6 p0 + 6np1 − 12 p1 + 3n + 2 = ( 9 p0 − 15 p1 + 2 ) + ( 9 p1 + 3) n, ∀n ∈ , n ≥ 2 vanhoa@lqdqt.com Trang 7 10/1/2008
  8. VanHoa Chuyên dãy s - Gi i các h th c truy h i So sánh 2 v c a ng th c trên, ta c 61 p0 = − p0 = 9 p0 − 15 p1 + 2 64 ⇔ p1 = 9 p1 + 3 3 p1 = − 8 61 3 Do ó m t nghi m riêng c a (III.3.2.1.2) là f p ( n ) = − − n 64 8 Xét dãy s f ( n ) = 2 f ( n − 1) − f ( n − 2 ) − 6 (III.3.2.1.3) Ph ng trình c tr ng t ng ng c a nó là x 2 − 2 x + 1 = 0 , nghi m c a nó là r1 = r2 = 1 . Nên, f p ( n ) có d ng: f p ( n ) = p0 + p1n + p2 n 2 Th vào (III.3.2.1.3), ta c: 2 2 ( ) ( p0 + p1n + p2 n 2 = 2 p0 + p1 ( n − 1) + p2 ( n − 1) − p0 + p1 ( n − 2 ) + p2 ( n − 2 ) − 6 ) = ( p0 − 2 p2 − 6 ) + p1n + p2 n 2 , ∀n ∈ , n ≥ 2 So sánh 2 v , ta c p0 = p0 − 2 p2 − 6 p2 = −3 , nên f p ( n ) = p0 + p1n − 3n 2 , m t khác f h ( n ) = ( c0 + c1n )1n , v y f ( n ) = p0 + p1n − 3n 2 + c0 + c1n = c2 + c3 n − 3n 2 v i c2 , c3 là các h&ng s , có th xác nh t( các giá tr c a f ( 0 ) và f (1) . Tìm f p ( n ) khi g ( n ) là hàm s m theo bi n n Khi g ( n ) = ca n v i c và a là h&ng s , thì nghi m riêng f p ( n ) có d ng f p ( n ) = ( p0 + p1n + p2 n 2 + ... + pw n w ) a n V i w = 0 n u a là nghi m c a ph ng trình c tr ng, và b&ng k v i a là nghi m b i k c a ph ng trình c tr ng. Xét h th c truy h i f ( n ) = 3 f ( n − 1) + 2 f ( n − 4 ) − 6 ⋅ 2n (III.3.2.1.4) H th c truy h i thu n nh%t t ng ng là: f h ( n ) = 3 f h ( n − 1) + 2 f h ( n − 4 ) Ph ng trình c tr ng c a nó là: x 4 − 3x3 − 2 = 0 D dàng ki m tra x = 2 không ph i là nghi m c a nó, vì v y nghi m riêng c a (III.3.2.1.4) có d ng: f p ( n ) = p0 2n Th vào (III.3.2.1.4) ta c: p0 2n = 3 p0 2n −1 + 2 p0 2n − 4 − 6 ⋅ 2n , ∀n ∈ , n ≥ 4 ⇔ p0 24 = 3 p0 23 + 2 p0 − 6 ⋅ 24 , ∀n ∈ , n ≥ 4 ⇔ 16 p0 = 24 p0 + 2 p0 − 96, ∀n ∈ , n ≥ 4 48 ⇔ p0 = 5 48 ⋅ 2n Nên m t nghi m riêng c a (III.3.2.1.4) là f p ( n ) = . 5 vanhoa@lqdqt.com Trang 8 10/1/2008
  9. VanHoa Chuyên dãy s - Gi i các h th c truy h i Xét h th c truy h i f ( n ) = 5 f ( n − 1) − 6 f ( n − 2 ) + 4 ⋅ 3n (III.3.2.1.5) 2 Ph ng trình c tr ng c a h th c truy h i thu n nh%t t ng ng là x − 5 x + 6 = 0 , có nghi m r1 = 2, r2 = 3 . Do 3 là nghi m b i 1 (nghi m n) c a ph ng trình c tr ng nên nghi m riêng c a nó có d ng: f p ( n ) = ( p0 + p1n ) 3n Th vào (III.3.2.1.5) ta c: ( p0 + p1n ) 3 = 5 ( p0 + p1 ( n − 1) ) 3n −1 − 6 ( p0 + p1 ( n − 2 ) ) 3n −2 + 4 ⋅ 3n , ∀n ∈ , n ≥ 2 n Chia 2 v cho 3n − 2 , ta c: ( p0 + p1n ) 32 = 5 ( p0 + p1 ( n − 1) ) 3 − 6 ( p0 + p1 ( n − 2 ) ) + 4 ⋅ 32 = ( 9 p0 − 3 p1 + 36 ) + 9 p1n, ∀n ∈ , n ≥ 2 So sánh 2 v , ta th%y 9 p0 = 9 p0 − 3 p1 + 36 ⇔ p1 = 12 . M t nghi m riêng c a (III.3.2.1.5) là: f p ( n ) = ( p0 + 12n ) 3n M t khác, nghi m chung c a ph n thu n nh%t c a nó là: f h ( n ) = c1 2n + c2 3n V y nên nghi m chung c a nó là: f ( n ) = fh ( n ) + f p ( n ) = c1 2n + ( c2 + p0 ) 3n + 12 ⋅ n ⋅ 3n = c1 2n + c3 3n + 12 ⋅ n ⋅ 3n Cho 2 giá tr u, f ( 0 ) và f (1) , ta s tính c giá tr c a c1 và c3 . Tìm k t quá cu i cùng Chúng ta ã bi t f ( n ) = f h ( n ) + f p ( n ) là nghi m chung c a h th c truy h i: f ( n ) = a1 f ( n − 1) + a2 f ( n − 2 ) + ... + ak f ( n − k ) + g ( n ) , n ≥ k (II.3.3.1) S d ng các giá tr ban u f ( 0 ) , f (1) , f ( 2 ) ,..., f ( k − 1) , chúng ta có th tìm c k h&ng s ch a xác nh trong f h ( n ) + f p ( n ) nh n c k t qu duy nh%t v i m i b giá tr ban u cho h th c trên. Tóm t t Ph ng pháp nghi m c tr ng dùng gi i h th c (II.3.3.1) bao g m các b c sau: 1. Vi t ph ng trình c tr ng: k k x − ai x k −i = 0 i =1 2. Xác nh các nghi m phân bi t t1 , t1 ,..., t s c a ph ng trình c tr ng, v i ti là nghi m b i mi , i = 1, n . 3. Xác nh nghi m chung fh ( n ) c a h th c thu n nh%t t ng ng. ( ) f h ( n ) = u1 ( n ) + u2 ( n ) + ... + us ( n ) v i ui ( n ) = ci0 + ci1 n + ci2 n 2 + ... + ciw-1 n w−1 tin , w = mi . 4. Xác nh nghi m riêng f p ( n ) . • N u g ( n ) = 0 , thì f p ( n ) = 0 . vanhoa@lqdqt.com Trang 9 10/1/2008
  10. VanHoa Chuyên dãy s - Gi i các h th c truy h i d • Khi g ( n ) = ei ni , ed ≠ 0 , nghi m riêng f p ( n ) có d ng i =1 f p ( n ) = p0 + p1n + p2 n 2 + ... + pd + m n d + m (III.3.2.1.1) V i m = 0 n u 1 không là nghi m c a ph ng trình c tr ng, và n u 1 là nghi m c a ph ng trình c tr ng thì m = k v i 1 là nghi m b i k c a ph ng trình c tr ng. • Khi g ( n ) = ca n v i c và a là h&ng s , thì nghi m riêng f p ( n ) có d ng f p ( n ) = ( p0 + p1n + p2 n 2 + ... + pw n w ) a n V i w = 0 n u a là nghi m c a ph ng trình c tr ng, và b&ng k v i a là nghi m b i k c a ph ng trình c tr ng. 5. N u g ( n ) ≠ 0 , s d ng f p ( n ) trên lo i b# t%t c các f ( n − i ) trong (II.3.3.1) b&ng cách thay th f p ( n − i ) cho f ( n − i ) . Sau ó s d ng tính ch%t c a ng nh%t nh c xác nh càng nhi u càng t t các h s ch a bi t. 6. Ghi ra k t qu , f ( n ) = f h ( n ) + f p ( n ) . Gi i h s d ng các giá tr ban u f ( 0 ) , f (1) , f ( 2 ) ,..., f ( k − 1) tìm t%t c các h s ch a bi t còn l i. nh lý 2. Sáu b c trên luôn tìm c nghi m duy nh t cho h th c (II.3.3.1) v i các giá tr kh i u cho tr c. Ví d II.3.5.1. Ph ng trình c tr ng c a h th c truy h i tuy n tính thu n nh t b c 2: un = 6un −1 − 4un − 2 | n ∈ , n ≥ 2 Là x2 − 6 x + 4 = 0 Có 2 nghi m phân bi t x1 = 3 − 5, x2 = 3 + 5 n n Nên ( un = c1 3 − 5 ) ( + c2 3 + 5 ) | n∈ Gi s r&ng ta có u0 = 0 và u1 = 4 5 , v y thì ta có h : 0 0 ( ) + c (3 + 5 ) ⇔ 0 = c + c u0 = c1 3 − 5 2 1 ⇔ 2 c1 = −2 1 4 5 = c (3 − 5 ) + c (3 + 5 ) 1 c2 = 2 u = c (3 − 5 ) + c (3 + 5 ) 1 1 2 1 2 n n V y bi u th c c a u là u = −2 ( 3 − 5 ) + 2 ( 3 + 5 ) | n ∈ n n Ví d II.3.5.2. Xét h th c 5 |n=0 2 9 un = | n =1 2 5un −1 − 6un − 2 + 3n 2 | n ∈ , n ≥ 2 Ph ng trình c tr ung cho ph n thu n nh%t là: x2 − 5x + 6 = 0 Nghi m c a nó là x1 = 2, x2 = 3 Vì v y nghi m chung cho ph n thu n nh%t là hn = c1 2 n + c2 3n | n ∈ vanhoa@lqdqt.com Trang 10 10/1/2008
  11. VanHoa Chuyên dãy s - Gi i các h th c truy h i Do g ( n ) = 3n 2 và 1 không ph i là nghi m c a ph ng trình c tr ng nên nghi m riêng c a un có d ng: pn = a0 + a1n + a2 n 2 Th vào h th c ban u: 2 2 ( ) ( a0 + a1n + a2 n 2 = 5 a0 + a1 ( n − 1) + a2 ( n − 1) − 6 a0 + a1 ( n − 2 ) + a2 ( n − 2 ) + 3n 2) = ( −a0 + 7 a1 − 19a2 ) + ( − a1 + 14a2 ) x + ( 3 − a2 ) x 2 , ∀n ∈ , n ≥ 2 Nên ta có h a0 = − a0 + 7a1 − 19a2 45 21 3 a1 = − a1 + 14a2 ⇔ a0 = , a1 = , a2 = 2 2 2 a2 = 3 − a2 V y nghi m chung c a un là 45 21 3 un = hn + pn = c1 2n + c2 3n + + n + n 2 , ∀n ∈ 2 2 2 5 9 Do u0 và u1 ã c bi t v i giá tr l n l t là và , ta c: 2 2 5 45 = c1 + c2 + 2 2 c = −30 ⇔ 1 9 69 c2 = 10 = 2c1 + 3c2 + 2 2 45 21 3 V y nên un = −30 ⋅ 2n + 10 ⋅ 3n + + n + n 2 , ∀n ∈ 2 2 2 Chúng ta có th ki m tra k t qu này b&ng quy n p Ví d II.3.5.3. Chúng ta hãy gi i h th c: f ( n ) = 10 f ( n − 1) − 37 f ( n − 2 ) + 60 f ( n − 3) − 36 f ( n − 4 ) + 4 | n ∈ , n ≥ 4 V i f ( 0 ) = f (1) = f ( 2 ) = f ( 3) = 1 Ph ng trình c tr ng: x 4 − 10 x3 + 37 x 2 + 60 x − 36 = 0 Hay 2 2 ( x − 3) ( x − 2 ) =0 Có các nghi m x1 = x2 = 2 và x3 = x4 = 3 Do các nghi m u b i 2 nên nghi m chung c a ph n thu n nh%t là: f h ( n ) = ( c1 + c2 n ) 2n + ( c3 + c4 n ) 4n Do g ( n ) = 4 và 1 không ph i là nghi m c a ph ng trình c tr ng nên f p ( n ) có d ng: f p ( n ) = p0 Th vào h th c ban u, ta có: p0 = 10 p0 − 37 p0 + 60 p0 − 36 p0 + 4 Nên p0 = 1 Nghi m chung c a h th c ban u s là: f h ( n ) = ( c1 + c2 n ) 2n + ( c3 + c4 n ) 4n + 1 vanhoa@lqdqt.com Trang 11 10/1/2008
  12. VanHoa Chuyên dãy s - Gi i các h th c truy h i Th n = 0, n = 1, n = 2, n = 3 và s d ng f ( 0 ) = f (1) = f ( 2 ) = f ( 3) = 1 , ta c c1 + c3 = 0 2c1 + 2c2 + 3c3 + 3c4 = 0 ⇔ c1 = c2 = c3 = c4 = 0 4c1 + 8c2 + 9c3 + 18c4 = 0 8c1 + 24c2 + 27c3 + 81c4 = 0 V y nên f ( n ) = 1, ∀n ∈ . Chúng ta có th d dàng ki m tra i u này b&ng quy n p. Bây gi) n u thay i i u ki n bài thành f ( 0 ) = f (1) = f ( 2 ) = 1, f ( 3) = 4 thì sau khi l p h t ng 3 t nh trên ta s tìm c c1 = 6, c2 = , c3 = −6, c4 = 1 , lúc này 2 3 f h ( n ) = 6 + n 2n + ( n − 6 ) 4n + 1, ∀n ∈ . M t l n n a, chúng ta có th ki m tra k t qu này b&ng 2 quy n p. 4. Ph ng pháp s d ng hàm sinh M t hàm sinh G ( z ) là m t chu i l'y th(a vô h n: +∞ G ( z) = ci z i (II.4.1) i =0 Ta nói r&ng m t hàm sinh G ( z ) t ng ng v i hàm s f: → n u và ch n u ci = f ( i ) , ∀i ∈ . Ví d II.4.1. G ( z ) = 2zi t ng ng v i hàm f ( n ) = 2, ∀n ∈ ; i≥0 G ( z) = iz i t ng ng v i hàm f ( n ) = n, ∀n ∈ ; i ≥0 0 | ∀n ∈ , 0 ≤ n ≤ 7 G ( z) = 2zi t ng ng v i hàm f ( n ) = . i ≥8 2 | ∀n ∈ ,8 ≤ n M t hàm sinh có th c bi u di n d i 2 d ng. F ng th nh%t c g i là chu i l y th a, ây là d ng c cho (II.4.1). D ng khác c g i là d ng t )ng minh. Ví d II.4.2. Chu i l'y th(a cho hàm f ( n ) = 1, ∀n ∈ là G ( z ) = z i , nên zG ( z ) = z i . Tr( theo i ≥0 i ≥1 1 v , ta có G ( z ) − zG ( z ) = zi − z i = 1 , d,n n G ( z) = . Vì v y d ng t )ng minh c a chu i l'y i ≥0 i ≥1 1− z 1 th(a z i là . i≥0 1− z 1 L u ý r&ng = z i ch úng v i nh ng giá tr c a z làm chu i z i h i t . Chúng ta không bàn 1 − z i ≥0 i≥0 n v%n này ây. n V i n là s nguyên và i là s t nhiên, h s nh th c c xác nh nh sau: i n n ( n − 1)( n − 2 ) ... ( n − i + 1) = i i ( i − 1)( i − 2 ) ... (1) 3 3⋅ 2 4 4⋅3 −3 ( −3) ⋅ ( −4 ) = 6 Ví d II.4.3. = = 3; = = 6; = 2 2 ⋅1 2 2 ⋅1 2 2 ⋅1 vanhoa@lqdqt.com Trang 12 10/1/2008
  13. VanHoa Chuyên dãy s - Gi i các h th c truy h i nh lý khai tri n nh th c (hay ng*n g n h n là nh lý nh th c) là m t nh lý toán h c v vi c khai tri n hàm m' c a t ng. C th , k t qu c a nh lý này là vi c khai tri n m t nh th c b c n thành m t a th c có n+1 s h ng: n n n n −i i (a + z) = a z ,n∈ i =0 i T ng quát h n, nh lý c phát bi u d i d ng: n m n i (1 + z ) = z ,n∈ (II.4.2) i =0 i V i m = n n u n ≥ 0 và m = +∞ trong tr )ng h p ng c l i. $ ng th c (II.4.2) cho ta m t s d ng t )ng minh quan tr ng. Ví d II.4.4. V i n = −2 , ta c 1 −2 i 2 = z (1 + z ) i≥0 i −2 ( −2 )( −2 − 1)( −2 − 2 ) ... ( −2 − i ) = −1 i i + 1 Mà = ( )( ) i i ( i − 1)( i − 2 ) ... (1) 1 Nên (1 + z ) 2 = i ≥0 (( −1) ( i + 1) z ) i i 1 Th z b i – z, ta u c 2 = ( ( i + 1) z ) i (1 − z ) i≥0 1 V y d ng t )ng minh c a ( ( i + 1) z ) là i 2 . i≥0 (1 − z ) 1 * $ ng th c (II.4.2) có th dùng tìm d ng t )ng minh c a n | n∈ . (1 − z ) Chúng ta s s m bi t r&ng, hàm sinh có th dùng gi i các quan h h i quy. Nh ng u tiên, chúng ta hãy tìm hi u v các phép toán trên các hàm sinh. Các phép toán trên hàm sinh C ng và tr : N u G1 ( z ) = ci z i và G2 ( z ) = di z i là các hàm sinh t ng ng v i các hàm f1 và f 2 , i≥0 i≥0 thì hàm sinh ng v i f1 ± f 2 là ( ci ± di ) z i , là h qu tr c ti p t( nh ngh!a c a hàm sinh. i≥0 Nhân v i h ng s : N u G1 ( z ) = ci z i là hàm sinh t ng ng v i hàm f , thì i≥0 G2 ( z ) = aG1 ( z ) = aci z i là hàm sinh ng v i a ⋅ f , a là h&ng s . i≥0 0 | n∈ ,0 ≤ n < k Do z k G1 ( z ) = ci z i + k là hàm sinh ng v i hàm s g (n) = , nên nhân m t i ≥0 f (n − k ) | n ∈ , n ≥ k hàm sinh v i z k t ng ng v i vi c d ch chuy n dãy s sang ph i k nv. vanhoa@lqdqt.com Trang 13 10/1/2008
  14. VanHoa Chuyên dãy s - Gi i các h th c truy h i 1 Ví d II.4.5. " ví d II.4.4, chúng ta ã ch ra r&ng ( ( i + 1) z ) = i 2 , nhân c 2 v v i z, ta nh n i≥0 (1 − z ) i +1 z z z c ( ( i + 1) z ) = 2 hay ( iz ) = i 2 . Nên 2 là d ng t )ng minh cho hàm sinh i≥0 (1 − z ) i≥0 (1 − z ) (1 − z ) ng v i hàm s f ( n ) = n, ∀n ∈ , n ≥ 0 . Tích c a 2 hàm sinh: Tích G1 ( z ) ⋅ G2 ( z ) c a 2 hàm sinh G1 ( z ) = ci z i và G2 ( z ) = di z i là m t i≥0 i≥0 hàm sinh th 3 G3 ( z ) = ei z . Có th d dàng ki m tra i c r&ng ei c cho b i: i≥0 i ei = c j di − j , i ∈ (II.4.1.1) j =0 L u ý r&ng tích c a 2 hàm sinh có tính giao hoán: G1 ( z ) ⋅ G2 ( z ) = G2 ( z ) ⋅ G1 ( z ) $ ng th c (II.4.1.1) cho ta th%y tích c a 2 hàm sinh có th có l i trong vi c tính các t ng. N u 1 G2 ( z ) = z i = , di = 1, ∀i ∈ , thì (II.4.1.1) tr thành: i ≥0 1− z i ei = cj,i ∈ (II.4.1.2) j =0 n Ví d II.4.6. Chúng ta hãy th tìm bi u th c t )ng minh cho t ng s ( n ) = i . T( ví d II.4.5, chúng ta i =1 z ã bi t r&ng 2 là d ng t )ng minh cho hàm sinh ng v i hàm s f ( n ) = n . H n n a, ví d (1 − z ) 1 II.4.2, ta bi t r&ng là d ng t )ng minh cho hàm sinh ng v i hàm s f ( n ) = 1 . Nên, 1− z 1 z z ⋅ 2 = 3 là d ng t )ng minh cho iz i z i . Gi s r&ng d ng chu i l'y th(a c a 1 − z (1 − z ) (1 − z ) i≥0 i ≥0 n z 3 là ei z i . Theo (II.4.1.2), en = i = s ( n ) . Bây gi) chúng ta s tính ei . S d ng nh lý nh (1 − z ) i≥0 i=0 th c ta nh n c: −3 −3 i (1 − z ) = ( −1) z i i ≥0 i −3 Vì v y h s c a z n −1 trong khai tri n c a (1 − z ) là: −3 n −1 ( −3)( −4 ) ... ( −3 − n + 2 ) −1 n −1 ( −1) = ( ) n −1 ( n − 1)( n − 2 ) ... (1) = ( n + 1)( n )( n − 1) ... ( 3) ( n − 1)( n − 2 ) ... (1) n ( n + 1) = 2 vanhoa@lqdqt.com Trang 14 10/1/2008
  15. VanHoa Chuyên dãy s - Gi i các h th c truy h i z n ( n + 1) Nên, h s en c a z n trong khai tri n l'y th(a c a 3 là = s (n) . (1 − z ) 2 o hàm: L%y o hàm (II.4.1) theo z cho ta: +∞ d (G ( z )) = ici z i −1 (II.4.1.3) dz i =0 Hay +∞ d z dz (G ( z )) = ( ic )i z i (II.4.1.4) i =0 Ví d II.4.7. " ví d II.4.4, khai tri n nh th c ã c dùng tìm d ng t )ng minh cho ( ( i + 1) z ) . Chúng ta c'ng có th i tìm c k t qu này b&ng phép o hàm. T( ví d II.4.2, ta bi t i≥0 1 +∞ d 1 +∞ 1 r&ng zi = . , s d ng (II.4.1.3) cho ta iz i −1 = hay ( i + 1) z i = 2 . i≥0 1− z i =0 dz 1 − z i =0 (1 − z ) Tích phân: L%y tích phân (II.4.1) theo z, ta c: z +∞ ci −1 z i G ( u )du = (II.4.1.5) 0 i =1 i 1 * Ví d II.4.8. D ng t )ng minh cho hàm sinh c a hàm f ( n ) = , n ∈ có th c xác nh b&ng n cách l%y tích phân c a f ( n ) = 1 , t( ví d II.4.2, ta có: 1 = ui 1− u i≥0 Vì v y, z z 1 du = u i du 0 1− u i≥0 0 1 i +1 = z i≥0 z +1 1 i = z i >0 z Nh ng z 1 du = − ln (1 − z ) 0 1− u 0|n = 0 Nên hàm sinh c a hàm s f ( n ) = 1 là − ln (1 − z ) . | n∈ * n ng d ng gi i các h th c truy h i Ph ng pháp s d ng hàm sinh gi i các h th c truy h i s c minh h a rõ nh%t b&ng cách l%y m t ví d . Xét h th c truy h i: 0 |n=0 F ( n) = 2 F ( n − 1) + 7 | n ∈ * vanhoa@lqdqt.com Trang 15 10/1/2008
  16. VanHoa Chuyên dãy s - Gi i các h th c truy h i Nh ng b c gi i các h th c truy h i b&ng hàm sinh là: 1. G i G ( z ) = ai z i là hàm sinh c a hàm F ( n ) , v y thì ai = F ( i ) , ∀i ∈ . i ≥0 2. Thay th t%t c F ( n ) , F ( n − 1) , F ( n − 2 ) ,... b i các ai t ng ng, ví d này sau khi th c hi n * b c 2 ta s c: an = 2an −1 + 7, ∀n ∈ 3. Nhân 2 v c a ng th c nh n c v i z n và l%y t ng 2 v c a t%t c các n mà ng th c còn úng. " ví d này, ta c an z n = 2 an −1an z n + 7zn n ≥1 n ≥1 n ≥1 D ng t )ng minh Chu i l'y th(a −1 1 (1 − az ) ai z i i≥0 −2 2 (1 − az ) ( i + 1) a i z i i≥0 m n i i az n i =0 i 3 (1 − az ) n |n≥0 m= +∞ | n < 0 i +1 4 ln (1 + az ) ( −1) ai z i i ≥1 i 1 i i 5 − ln (1 − az ) az i ≥1 i 1 i i 6 eaz az i≥0 i ! B ng 1. M t s d ng t ng minh và chu i l y th a t ng ng 4. Thay th t%t c các t ng ch a ai b&ng bi u th c t ng ng ch ch a G ( z ) , z và m t s h u h n các ai . Cho m t h th c truy h i b c k s ch còn l i a0 , a1 ,..., ak −1 . " ví d này là: G ( z ) − a0 = 2 zG ( z ) + 7zn n ≥1 5. Thay th các giá tr ã bi t a0 , a1 ,..., ak −1 ( ai = F ( i ) ) : G ( z ) = 2 zG ( z ) + 7zn n ≥1 6. Gi i ph ng trình tìm G ( z ) t( ng th c nh n c. " ây thì: 1 7zn G ( z) = 1 − 2 z n ≥1 7. Xác nh h s c a z trong khai tri n l'y th(a c a ng th c nh n n c b c 6. H s này là an = F ( n ) . V ví d c a chúng ta: G ( z) = 2i z i ⋅ 7zn i≥0 n ≥1 vanhoa@lqdqt.com Trang 16 10/1/2008
  17. VanHoa Chuyên dãy s - Gi i các h th c truy h i H s c a z n trong tích c a hai chu i trên là : n an = 7 ⋅ 2n −i = 7 ( 2n − 1) i =1 Nên, F ( n ) = 7 ( 2 n − 1) , n ∈ . M t vài ví d ti p ây s minh h a rõ h n k! thu t này. Ví d II.4.2.1. Chúng ta hãy xét dãy các s Fibonacci: Fn = Fn −1 + Fn − 2 , ∀n ∈ * , n ≥ 2 V i F0 = 0, F1 = 1 $ t G ( z) = ai z i là hàm sinh c a hàm Fn . T( nh ngh!a c a hàm sinh, ta có ai = Fi , ∀i ∈ . V y thì i ≥0 Fn = an , Fn −1 = an −1 , Fn − 2 = an − 2 , t( h th c truy h i cho Fn , ta c: * an = an −1 + an − 2 , ∀n ∈ ,n ≥ 2 Nhân 2 v v i z n và l%y t ng t( n = 2 n +∞ , ta c: * an z n = an −1 z n + an − 2 z n , ∀n ∈ ,n ≥ 2 n≥2 n≥2 n≥2 * Nh n xét r&ng t ng trên không th l%y t( n = 0 n +∞ do Fn = Fn −1 + Fn − 2 ch úng v i ∀n ∈ ,n ≥ 2. $ ng th c trên có th c vi t l i nh sau: G ( z ) − a1 z − a0 = z an −1 z n −1 + z 2 an − 2 z n − 2 = z an z n + z 2 an z n = zG ( z ) − a0 z + z 2G ( z ) , ∀n ∈ * ,n ≥ 2 n≥2 n≥2 n ≥1 n ≥0 Th a0 = F0 = 0 và a1 = F1 = 1 và gi i ng th c trên cho G ( z ) , ta c: z G ( z) = 1− z − z2 z = 1+ 5 1− 5 1− z 1− z 2 2 1 1 1 = − 5 1+ 5 1− 5 1− z 1− z 2 2 −1 Do khai tri n l'y th(a c a (1 − az ) là a i z i nên: i≥0 i i 1 1+ 5 i 1− 5 G ( z) = z − zi 5 i≥0 2 i≥0 2 i i 1 1+ 5 1− 5 = − zi 5 i≥0 2 2 n n 1 1+ 5 1− 5 V y nên Fn = an = − , ∀n ≥ 0 . 5 2 2 vanhoa@lqdqt.com Trang 17 10/1/2008
  18. VanHoa Chuyên dãy s - Gi i các h th c truy h i 0 |n=0 Ví d II.4.2.2. Xét dãy: tn = atn −1 + bn | n ≥ 1 $ t G ( z) = ci z i là hàm sinh c a hàm tn , thì ci = ti , i ≥ 0 . T( công th c truy h i c a dãy, ta có: i≥0 cn = acn −1 + bn, ∀n ≥ 1 Nhân 2 v v i z r i l%y t ng t( n = 1 n n +∞ cho ta: cn z n = a cn −1 z n + bnz n n ≥1 n ≥1 n ≥1 Hay G ( z ) − c0 = az cn −1 z n −1 + bnz n n ≥1 n ≥1 = azG ( z ) + bnz n n ≥1 1 Th c0 = 0 và bi n i, ta c: G ( z ) = bnz n = an zn bnz n 1 − az n ≥1 n ≥0 n ≥1 Áp d ng công th c tích c a 2 hàm sinh, ta có: n n i cn = b ia n −i = ba n . i =1 i =0 ai n i Nên tn = cn = ba n ,n ≥ 0 . i =0 ai n i Ví d II.4.2.3. " ví d tr c, chúng ta ã ch ng minh c r&ng cn = ba n . M t bi u th c t )ng i =0 ai n i minh h n cho cn có th nh n c t( bi u th c t )ng minh c a d n = i . V i a = 1 bi u th c này có i =0 a th c tìm m t cách r%t n gi n, vì v y ta ch xét tr )ng h p a ≠ 1 . Tr c tiên, ta hãy tìm hàm sinh −1 i −1 z zi cho hàm s f ( i ) = i . Ta ã bi t r&ng (1 − z ) = z . Nên, 1 − i = . L%y o hàm theo bi n a i ≥0 a i≥0 ai z, ta c d 1 d zi d zi iz i −1 = = = dz 1 − z dz i≥0 ai i≥0 dz a i i ≥0 ai a a iz i −1 Hay 2 = ( z − a) i≥0 ai az iz i Nhân 2 v v i z, ta c 2 = ( z − a) i≥0 ai 1 Nhân 2 v v i , ta c 1− z az 1 iz i n i 2 = = z n = ( dn z n ) ( z − a ) (1 − z ) 1− z i≥0 a i n ≥0 i =0 ai n ≥0 vanhoa@lqdqt.com Trang 18 10/1/2008
  19. VanHoa Chuyên dãy s - Gi i các h th c truy h i Bây gi) chúng ta c n ph i tìm h s c a z n trong khai tri n c a az 2 ( z − a ) (1 − z ) Khai tri n bi u th c trên, ta c az −2 −1 2 = az ( a − z ) (1 − z ) ( z − a ) (1 − z ) −2 z z −1 = 1− (1 − z ) a a z i +1 i = i z zi a i ≥0 a i≥0 Nên, n −1 1 i +1 dn = a i =1 ai n −1 1 i n −1 1 = + a i =1 a i i =1 a i n 1 −1 1 n a = dn − n + a a 1 −1 a a n +1 − an − a + n Suy ra dn = 2 . a n ( a − 1) Ví d II.4.2.4. Xét h th c truy h i un = 5un −1 − 6un − 2 + 2n, ∀n ∈ , n ≥ 2 v i u0 = u1 = 0 . Gi s G ( z ) = ci z i là hàm sinh ng v i hàm f. V y thì un = cn , un −1 = cn −1 và un − 2 = cn − 2 . Vì th : i≥0 cn = 5cn −1 − 6cn − 2 + 2n, n ≥ 2 Hay cn z n = 5cn −1 z n − 6cn − 2 z n + 2nz n , n ≥ 2 L%y t ng khi cho n = 2 n +∞ : cn z n = 5 z cn −1 z n −1 − 6 z 2 cn − 2 z n − 2 + 2nz n , n ≥ 2 n≥2 n≥2 n≥2 n≥2 Hay G ( z ) − c1 z − c0 = 5 z ( G ( z ) − c0 ) − 6 z 2G ( z ) + 2nz n , n ≥ 2 n≥2 Th c0 = c1 = 0 , ta c: G ( z ) = 5 zG ( z ) − 6 z 2G ( z ) + 2nz n , n ≥ 2 n≥2 Hay G ( z ) (1 − 5 z + 6 z 2 ) = 2nz n n≥2 vanhoa@lqdqt.com Trang 19 10/1/2008
  20. VanHoa Chuyên dãy s - Gi i các h th c truy h i Nên 2nz n n≥2 G ( z) = (1 − 3z )(1 − 2 z ) 3 2 = − 2 jz j 1 − 3z 1 − 2 z j≥2 = 3 3i z j − 2 2i z j 2 jz j i ≥0 i ≥0 j ≥2 Có th th%y r&ng h s cn c a z lúc này là: n n n cn = 6 j ⋅ 3n − j − 4 j ⋅ 2n − j j =2 j =2 n n j j = 6 ⋅ 3n − 4 ⋅ 2n j =2 3 j =2 2 j j n j 3n +1 − 2n − 3 1 T( ví d II.4.2.3, ta bi t r&ng: = − j =2 3 4 ⋅ 3n 3 j n j 2n +1 − n − 2 1 Và = − j =2 2 2n 2 j 3n +1 − 2n − 3 1 2n +1 − n − 2 1 cn = 6 ⋅ 3n − − 4 ⋅ 2n − 4 ⋅ 3n 3 2n 2 3 n +1 Nên = 2 ( 3 − 2n − 3) − 6 ⋅ 3n−1 − 4 ( 2n+1 − n − 2 ) + 4 ⋅ 2n−1 5 ⋅ 3n 7 = − 3 ⋅ 2n +1 + n + 2 2 5⋅3 n 7 V y un = − 3 ⋅ 2n +1 + n + . 2 2 Cu i cùng m)i các b n hãy t gi i m t s bài toán sau n*m ch*c h n các ph ng pháp nêu trên: Tìm s h ng t ng quát c a dãy s ( un ) trong các tr )ng h p sau sau: 1. u1 = a , un +1 = a + bun . 1 2. u0 = a, u1 = b, un + 2 = ( un +1 + un ) 2 3. u0 = 1, u1 = 2, u2 = 3, un +3 = 18un + 2 − 107un +1 + 210 + n 3 − 5n 2 − 3 4 2 4 2 4. u1 = a , un +1un − un +1un + un − aun +1un − bun +1un + bun +1un − bun +1 = 0 . 5. u0 = a, u1 = b, u2 = c, 2un +3 + un + 2 − 16un +1 − 15un + 4n 2 − 2 = 0 6. u0 = a, u1 = b, u2 = c, 2un +3 + 5un + 2 − 4un +1 − 10un − 3n + n 2 − 4n − 4 = 0 7. u0 = a, u1 = b, 2un + 2 + un +1 − 10un − 3n − n3 + n 2 − 2n − 1 = 0 vanhoa@lqdqt.com Trang 20 10/1/2008
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
4=>1