Tài liệu Chuyên đề giải các hệ thức truy hồi

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: tn = c1 | n = 0 c2 + tn −1 | n ∈ * (II.1.1) 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 ∈ [email protected] Trang 1 10/1/2008 VanHoa Ví d II.1.2 Xét h th c truy h i: Chuyên dãy s - Gi i các h th c truy h i c | n =1 t (n) = n + nc | n ∈ b at 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 n t ( n ) = at + nc b = a at * ,n ≥ 2 (II.1.2) ng pháp th cho ta: n n + c + nc 2 b b n a + nc + nc 2 b b = a 2t n n a + c 2 + nc + 1 3 b b b = a 2 at 2 n a = a t 3 + nc b b 3 + nc n n + c 4 + nc 4 b b = a 3 at n = a t 4 + nc b 3 a b 4 a + b a +1 b 2 a b + 2 + a +1 b a +1 b = ... k −1 n = a t k + nc b i =0 = a k t (1) + nc k −1 k −1 a b k = a c + nc i =0 a b = nc k = nc i= 0 k k −1 + nc i =0 a b i a b i =0 i a b k i a b i i k +1 Khi a = b , k i =0 a b [email protected] i k = k + 1 , khi a ≠ b , i =0 a b i a −1 b = . a −1 b Trang 2 10/1/2008 VanHoa Chuyên dãy s - Gi i các h th c truy h i nc ( k + 1) | a = b V y, ta c: t ( n ) = k +1 a b nc −1 |a ≠b a −1 b , k = log b n n (I.1.3) + g (n) | n ∈ * b v i a và b là nh ng h&ng s ã bi t. Gi s r&ng t (1) ã Xét h th c t ( n ) = at khi t (1) = c và g ( n ) = nc . L i s d ng ph t ( n ) = at ng pháp th , ta có: n + g ( n) b = a at = a 2t c bi t. Rõ ràng, (I.1.3) tr thành (I.1.2) n n +g 2 b b + g ( n) n n + ag + g ( n) 2 b b = ... k −1 = a k t (1) + ai g i =0 n bi V i k = logb n . $ ng th c này có th t ( n ) = a k t (1) + c làm k −1 ai g i=0 k −1 = a k t (1) + n bi ( a g ( n )) i i=0 n gi n h n nh sau: k = a k t (1) + k −i ( a g (b )) −j j =1 j Do a k = a logb n = n logb a , nên bi u th c cho t ( n ) tr thành: t ( n ) = n logb a t (1) + k −j j =1 =n log b a k t (1) + j =1 = n logb a t (1) + k j g (b j ) j logb a (b ) ( h (b )) j j =1 [email protected] ( a g (b )) Trang 3 10/1/2008 VanHoa V i h (b Chuyên j )= k j logb a (b ) j =1 ( h (b )) . Xét m t s g ( n) n + c , lúc này log b a = 0 và h ( n ) = logb a = c . T( công n 2 log b a c t (n) = n ( t (1) + c log 2 n ) = t (1) + c log 2 n a = 7, b = 2, g ( n ) = 18n 2 h ( n) = cho 18n 2 = 18n 2 −log 2 7 , log 2 7 n = n log 2 7 t (1) + 18 k j =1 • tr )ng h p riêng c a (II.1.3): a = 1, b = 2, g (n) = c cho ta t ( n ) = t th c trên, ta • . 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 f (n) = • g (b j ) dãy s - Gi i các h th c truy h i ( 2( ta công th c cho k 2 − log 2 7 ) 4 (3 j ) là t (n) lúc này log b a = log 2 7 t ( n ) = nlog 2 7 t (1) + k 18 ( 2 j ) và 2 − log 2 7 j =1 ) j = n log 2 7 t (1) + 18 4 = n 2 t (1) + j =1 2 ( 2− log2 7 )( k +1) 2 ( 2 −log 2 7 ) −2 −1 ( 2−log 2 7 ) . 4n 6 n + 4n 6 , lúc này log b a = 2 và h ( n ) = 2 = 4n 4 , nên n 3 a = 9, b = 3, g ( n ) = 4n6 cho ta t ( n ) = 9t t ( n ) = n 2 t (1) + n + 18n 2 , 2 t ( n ) = 7t 81log3 n +1 − 81 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 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 ng trình truy h i (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. [email protected] Trang 4 10/1/2008 VanHoa H th c (II.1.2): Chuyên dãy s - Gi i các h th c truy h i c | n =1 t (n) = at n + nc | n ∈ * , n ≥ 2 b ng trình truy h i tuy n tính b c k v i h&ng s k nào b i v i n là l'y th(a c a b không ph i là m t ph n 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: vì s xu%t hi n c a t 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: h (k ) = c | n =1 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 t ( 0 ) = 0 và t (1) = 1 , chúng ta có th th vào t ( n ) = c1 2n + c2 3n xác nh là c1 và c2 . N u 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 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 vi c tìm f h ( n ) xác nh ng trình f ( n ) . Nên c ng vào f p ( n ) là i u c n thi t. [email protected] Trang 5 10/1/2008 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 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 (II.3.1.1) 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 ai x k −i = 0 x n−k x k − i =1 Ph 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 ng trình (II.3.1.2) x k − a1 x k −1 − a2 x k − 2 − ... − ak = 0 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 Là Nghi m c a ph ng trình truy h i t ( n ) = 5t ( n − 1) − 6t ( n − 2 ) | n ∈ * ,n ≥ 2 2 ng trình x − 5x + 6 = 0 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 . (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) n Ph n n n 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 [email protected] Trang 6 10/1/2008 VanHoa Chuyên Dãy truy h i cho các s Fibonacci là thu n nh t và có ph ng trình dãy s - Gi i các h th c truy h i c tr ng x 2 − x − 1 = 0 . Các nghi m c a 1+ 5 1− 5 và r2 = . Do các nghi m này phân bi t, nên u1 ( n ) = c1 2 2 1− 5 nó là r1 = 2 và n 1+ 5 u2 ( n ) = c2 2 . Vì v y 1− 5 F ( n ) = c1 2 n 1+ 5 + c2 2 n Là nghi m chung c a dãy Fibonacci. S d ng i u ki n F ( 0 ) = 0 và F (1) = 1 , ta 1− 5 1+ 5 + c2 = 1 . Gi i cho c1 , c2 ta 2 2 c1 n c c1 = − c c1 + c2 = 0 và 1 1 , c2 = . Nên các s Fibonacci thõa mãn 5 5 ng th c n n 1 1− 5 1 1+ 5 F (n) = − + 2 2 5 5 $ 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 . Khi g ( n ) = d 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 Có g ( n ) = 3n + 2 , ph u ( n ) = 3u ( n − 1) + 6u ( n − 2 ) + 3n + 2 ng trình c tr ng c a nó là x 2 − 3 x − 6 = 0 . Ph (III.3.2.1.2) 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 [email protected] Trang 7 10/1/2008 VanHoa So sánh 2 v c a Chuyên ng th c trên, ta dãy s - Gi i các h th c truy h i c 61 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 p0 = − p0 = 9 p0 − 15 p1 + 2 Ph ng trình có d ng: c tr ng t (III.3.2.1.3) 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 ) 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 ⇔ p0 = 48 5 Nên m t nghi m riêng c a (III.3.2.1.4) là f p ( n ) = [email protected] 48 ⋅ 2n . 5 Trang 8 10/1/2008 VanHoa Xét h th c truy h i Chuyên dãy s - Gi i các 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: n ( p0 + p1n ) 3 = 5 ( p0 + p1 ( n − 1) ) 3n −1 − 6 ( p0 + p1 ( n − 2 ) ) 3n −2 + 4 ⋅ 3n , ∀n ∈ , n ≥ 2 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 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 (II.3.3.1) 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 ai x k −i = 0 k x − 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 . [email protected] Trang 9 10/1/2008 VanHoa Chuyên Khi g ( n ) = • d dãy s - Gi i các h th c truy h i 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 ph ng trình c tr ng. 5. N u g ( n ) ≠ 0 , s d ng f p ( n ) trên ng trình c tr ng, và b&ng k v i a là nghi m b i k c a 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. u 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 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 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 u x2 − 6 x + 4 = 0 x1 = 3 − 5, x2 = 3 + 5 Là Có 2 nghi m phân bi t ( Nên un = c1 3 − 5 ) n ( + c2 3 + 5 ) n | 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 ⇔ 4 5 = c (3 − 5 ) + c (3 + 5 ) u = c (3 − 5 ) + c (3 + 5 ) c c a u là u = −2 ( 3 − 5 ) + 2 ( 3 + 5 ) | n ∈ u0 = c1 3 − 5 2 1 1 1 V y bi u th 1 1 1 2 n n 2 2 c1 = −2 c2 = 2 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 ∈ [email protected] Trang 10 10/1/2008 VanHoa Chuyên Do g ( n ) = 3n 2 và 1 không ph i là nghi m c a ph d ng: Th vào h th c ban ng trình dãy s - Gi i các h th c truy h i c tr ng nên nghi m riêng c a un có pn = a0 + a1n + a2 n 2 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 a1 = − a1 + 14a2 ⇔ a0 = a2 = 3 − a2 45 21 3 , a1 = , a2 = 2 2 2 V y nghi m chung c a un là 45 21 3 + 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 + c = −30 2 2 ⇔ 1 9 69 c2 = 10 = 2c1 + 3c2 + 2 2 45 21 3 un = −30 ⋅ 2n + 10 ⋅ 3n + + n + n 2 , ∀n ∈ V y nê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 un = hn + pn = c1 2n + c2 3n + 2 ( x − 3) ( x − 2 ) 2 =0 Có các nghi m Do các nghi m x1 = x2 = 2 và x3 = x4 = 3 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ó: Nên Nghi m chung c a h th c ban [email protected] p0 = 10 p0 − 37 p0 + 60 p0 − 36 p0 + 4 p0 = 1 u s là: f h ( n ) = ( c1 + c2 n ) 2n + ( c3 + c4 n ) 4n + 1 Trang 11 10/1/2008 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 ∈ Bây gi) n u thay t nh . Chúng ta có th d dàng ki m tra i u này b&ng quy n p. i i u ki n trên ta bài thành f ( 0 ) = f (1) = f ( 2 ) = 1, f ( 3) = 4 thì sau khi l p h t s tìm 3 c1 = 6, c2 = , c3 = −6, c4 = 1 , 2 c lúc ng này 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: +∞ (II.4.1) ci z i G ( z) = i =0 Ta nói r&ng m t hàm sinh G ( z ) t 2zi t Ví d II.4.1. G ( z ) = ng ng v i hàm s f: n u và ch n u ci = f ( i ) , ∀i ∈ → . ng ng v i hàm f ( n ) = 2, ∀n ∈ ; i≥0 iz i t G ( z) = ng ng v i hàm f ( n ) = n, ∀n ∈ ; i ≥0 0 | ∀n ∈ , 0 ≤ n ≤ 7 . 2 | ∀n ∈ ,8 ≤ n i ≥8 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 G ( z) = 2zi t ng ng v i hàm f ( n ) = i ≥0 v , ta có G ( z ) − zG ( z ) = z i = 1 , d,n zi − i ≥0 1 th(a z i là . 1− z i≥0 1 = z i ch L u ý r&ng 1 − z i ≥0 n v%n này ây. i ≥1 úng v i nh ng giá tr c a z làm chu i n i 3 3⋅ 2 = = 3; 2 2 ⋅1 [email protected] z i h i t . Chúng ta không bàn i≥0 V i n là s nguyên và i là s t nhiên, h s nh th c Ví d II.4.3. i ≥1 1 n G ( z) = . Vì v y d ng t )ng minh c a chu i l'y 1− z = n i c xác nh nh sau: n ( n − 1)( n − 2 ) ... ( n − i + 1) 4 4⋅3 = = 6; 2 2 ⋅1 i ( i − 1)( i − 2 ) ... (1) −3 ( −3) ⋅ ( −4 ) = 6 = 2 2 ⋅1 Trang 12 10/1/2008 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 −i i n a z ,n∈ (a + z) = i i =0 T ng quát h n, nh lý c phát bi u d i d ng: m n i n z ,n∈ (II.4.2) (1 + z ) = i i =0 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 −2 i 1 = z 2 (1 + z ) i≥0 i −2 Mà i ( −2 )( −2 − 1)( −2 − 2 ) ... ( −2 − i ) = −1 i i + 1 ( )( ) i ( i − 1)( i − 2 ) ... (1) = 1 Nên (1 + z ) 2 i ≥0 1 Th z b i – z, ta u c (1 − z ) ( ( i + 1) z ) là V y d ng t )ng minh c a i≥0 $ ng th c (II.4.2) có th dùng 2 (1 − z ) i ( ( i + 1) z ) i = i≥0 1 i (( −1) ( i + 1) z ) i = 2 . tìm d ng t )ng minh c a 1 (1 − z ) n | n∈ * . 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 ci z i G1 ( z ) = là hàm sinh t ng ng v i hàm f , thì i≥0 aci z i là hàm sinh ng v i a ⋅ f , a là h&ng s . G2 ( z ) = aG1 ( z ) = i≥0 Do z k G1 ( z ) = ci z i + k là hàm sinh ng v i hàm s g (n) = i ≥0 hàm sinh v i z k t [email protected] ng 0 f (n − k ) | n ∈ , n ≥ k ng v i vi c d ch chuy n dãy s sang ph i k Trang 13 | n∈ ,0 ≤ n < k , nên nhân m t nv. 10/1/2008 VanHoa Chuyên dãy s - Gi i các h th c truy h i ( ( i + 1) z ) = Ví d II.4.5. " ví d II.4.4, chúng ta ã ch ra r&ng i≥0 z i +1 ( ( i + 1) z ) = c i≥0 ng v i hàm s (1 − z ) ( iz ) = hay 2 z i i≥0 1 i (1 − z ) 2 . Nên (1 − z ) z (1 − z ) , nhân c 2 v v i z, ta nh n 2 là d ng t )ng minh cho hàm sinh 2 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 ) = i≥0 hàm sinh th 3 G3 ( z ) = ei z . Có th d dàng ki m tra c r&ng ei i di z i là m t i≥0 c cho b i: i≥0 i c j di − j , i ∈ ei = (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: 1− z i ≥0 i cj,i ∈ ei = (II.4.1.2) j =0 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 ) = n i . T( ví d II.4.5, chúng ta i =1 ã bi t r&ng z (1 − z ) II.4.2, ta bi t r&ng 2 là d ng t )ng minh cho hàm sinh ng v i hàm s 1 là d ng t )ng minh cho hàm sinh 1− z 1 z z ⋅ = là d ng t )ng minh cho 2 3 1 − z (1 − z ) (1 − z ) z (1 − z ) 3 là th c ta nh n ei z i . Theo (II.4.1.2), en = i≥0 n ng v i hàm s ví d f ( n ) = 1 . Nên, z i . Gi s r&ng d ng chu i l'y th(a c a iz i i≥0 f ( n ) = n . H n n a, i ≥0 i = s ( n ) . Bây gi) chúng ta s tính ei . S d ng nh lý nh i=0 c: (1 − z ) −3 −3 i ( −1) z i i = i ≥0 Vì v y h s c a z n −1 trong khai tri n c a (1 − z ) −3 là: −3 ( −3)( −4 ) ... ( −3 − n + 2 ) −1 n −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 [email protected] Trang 14 10/1/2008 VanHoa Chuyên Nên, h s en c a z n trong khai tri n l'y th(a c a o hàm: L%y z (1 − z ) o hàm (II.4.1) theo z cho ta: d (G ( z )) = dz +∞ 3 là dãy s - Gi i các h th c truy h i n ( n + 1) = s (n) . 2 ici z i −1 (II.4.1.3) ( ic )i z i (II.4.1.4) i =0 Hay +∞ d (G ( z )) = dz II.4.4, khai tri n nh th c z Ví d II.4.7. " ví d ( ( i + 1) z ) . Chúng ta c'ng có th i tìm i =0 ã c dùng tìm d ng t )ng minh cho c k t qu này b&ng phép o hàm. T( ví d II.4.2, ta bi t i≥0 r&ng zi = i≥0 1 . , s d ng (II.4.1.3) cho ta 1− z Tích phân: L%y tích phân (II.4.1) theo z, ta +∞ d 1 dz 1 − z iz i −1 = i =0 +∞ hay ( i + 1) z i = i =0 1 (1 − z ) 2 . c: z ci −1 z i i +∞ G ( u )du = i =1 0 1 Ví d II.4.8. D ng t )ng minh cho hàm sinh c a hàm f ( n ) = , n ∈ n cách l%y tích phân c a f ( n ) = 1 , t( ví d II.4.2, ta có: 1 = 1− u (II.4.1.5) * có th c xác nh b&ng ui i≥0 Vì v y, z 1 du = 1− u 0 z u i du i≥0 0 = i≥0 = i >0 1 i +1 z z +1 1 i z z Nh ng z 1 du = − ln (1 − z ) 1− u 0 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 ∈ * [email protected] Trang 15 10/1/2008 VanHoa Nh ng b Chuyên dãy s - Gi i các h th c truy h i 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 b c 2 ta s 3. Nhân 2 v c a c: úng. " ví d này, ta c c v i z n và l%y t ng 2 v c a t%t c các n mà an z n = 2 n ≥1 ví d này sau khi th c hi n * an = 2an −1 + 7, ∀n ∈ ng th c nh n ng ng, 7zn an −1an z n + n ≥1 ng th c còn n ≥1 D ng t )ng minh 1 (1 − az ) Chu i l'y th(a −1 ai z i i≥0 2 (1 − az ) −2 ( i + 1) a i z i i≥0 n i i az i m 3 (1 − az ) i =0 n m= ( −1) ln (1 + az ) 4 n |n≥0 +∞ | n < 0 i ≥1 5 − ln (1 − az ) 6 eaz B ng 1. M t s d ng t 4. Thay th t%t c các t ng ch a ai b&ng bi u th c t ng i +1 ai z i i 1 i i az i ≥1 i 1 i i az i≥0 i ! ng minh và chu i l y th a t ng 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 1 − 2 z n ≥1 n 7. Xác nh h s c a z trong khai tri n l'y th(a c a ng th c nh n an = F ( n ) . V ví d c a chúng ta: G ( z) = 2i z i ⋅ G ( z) = i≥0 [email protected] Trang 16 c b c 6. H s này là 7zn n ≥1 10/1/2008 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 7 ⋅ 2n −i = 7 ( 2n − 1) an = i =1 F ( n ) = 7 ( 2 n − 1) , n ∈ Nê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: * ,n ≥ 2 an = an −1 + an − 2 , ∀n ∈ Nhân 2 v v i z n và l%y t ng t( n = 2 n +∞ , ta an z n = n≥2 n≥2 an −1 z n −1 + z 2 n≥2 n≥2 n +∞ do Fn = Fn −1 + Fn − 2 ch * ,n ≥ 2. * ,n ≥ 2 n ≥0 c: z 1− z − z2 z 1− = úng v i ∀n ∈ an z n = zG ( z ) − a0 z + z 2G ( z ) , ∀n ∈ ng th c trên cho G ( z ) , ta = −1 an z n + z 2 n ≥1 G ( z) = Do khai tri n l'y th(a c a (1 − az ) ,n ≥ 2 n≥2 an − 2 z n − 2 = z Th a0 = F0 = 0 và a1 = F1 = 1 và gi i * an − 2 z n , ∀n ∈ an −1 z n + Nh n xét r&ng t ng trên không th l%y t( n = 0 $ ng th c trên có th c vi t l i nh sau: G ( z ) − a1 z − a0 = z c: 1 5 là 1+ 5 z 2 1− 1− 5 z 2 1 1 − 1+ 5 1− 5 1− z 1− z 2 2 a i z i nên: i≥0 1 G ( z) = 5 1 = 5 V y nên [email protected] 1 Fn = an = 5 i≥0 i≥0 1+ 5 2 i i z − i≥0 1+ 5 2 1+ 5 2 n i 1− 5 − 2 1− 5 − 2 Trang 17 1− 5 2 i zi i zi n , ∀n ≥ 0 . 10/1/2008 VanHoa Chuyên Ví d II.4.2.2. Xét dãy: $ t G ( z) = 0 tn = dãy s - Gi i các h th c truy h i |n=0 atn −1 + bn | n ≥ 1 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 +∞ cho ta: n cn z n = a n ≥1 cn −1 z n + bnz n n ≥1 n ≥1 Hay cn −1 z n −1 + G ( z ) − c0 = az n ≥1 bnz n n ≥1 bnz n = azG ( z ) + n ≥1 1 1 − az Áp d ng công th c tích c a 2 hàm sinh, ta có: Th c0 = 0 và bi n i, ta c: G ( z ) = bnz n = n ≥1 an zn n ≥0 n n i =1 Nên tn = cn = ba n n i =0 n ≥1 ia n −i = ba n cn = b bnz n i =0 i . ai i ,n ≥ 0 . ai Ví d II.4.2.3. " ví d tr c, chúng ta ã ch ng minh n c r&ng cn = ba n i =0 c tìm m t cách r%t cho hàm s z, ta n i . V i a = 1 bi u th c này có i i =0 a 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 minh h n cho cn có th nh n th i . M t bi u th c t )ng ai c t( bi u th c t )ng minh c a d n = i −1 f ( i ) = i . Ta ã bi t r&ng (1 − z ) = a z z . Nên, 1 − a i i ≥0 −1 = i≥0 zi . L%y ai o hàm theo bi n c d 1 d = dz 1 − z dz a a Hay ( z − a) Nhân 2 v v i z, ta Nhân 2 v v i i≥0 zi = ai 1 , ta 1− z az c ( z − a) 2 = i≥0 = i≥0 = i ≥0 iz i −1 ai iz i −1 ai iz i ai c az 2 ( z − a ) (1 − z ) [email protected] 2 i≥0 d zi dz a i = 1 1− z i≥0 iz i = a i n ≥0 Trang 18 n i =0 i z n = ( dn z n ) ai n ≥0 10/1/2008 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 = az ( a − z ) 2 ( z − a ) (1 − z ) z a i ≥0 (1 − z ) −2 z z = 1− a a = −2 (1 − z ) −1 −1 i +1 i z zi i a i≥0 Nên, dn = = 1 a 1 a n −1 i =1 i +1 ai n −1 i =1 i n −1 1 + a i i =1 a i n 1 −1 1 n a = dn − n + 1 a a −1 a Suy ra dn = a n +1 − an − a + n a n ( a − 1) 2 . 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 −1 z n −1 − 6 z 2 cn z n = 5 z n≥2 n≥2 cn − 2 z n − 2 + n≥2 2nz n , 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 [email protected] Trang 19 10/1/2008 VanHoa Nên Chuyên dãy s - Gi i các h th c truy h i 2nz n G ( z) = n≥2 (1 − 3z )(1 − 2 z ) 3 2 − 1 − 3z 1 − 2 z = = 3 2 jz j j≥2 3i z j − 2 i ≥0 2i z j i ≥0 2 jz j j ≥2 Có th th%y r&ng h s cn c a z lúc này là: n n n 6 j ⋅ 3n − j − cn = j =2 4 j ⋅ 2n − j j =2 n = 6 ⋅ 3n n j j n − 4 ⋅ 2 j j j =2 3 j =2 2 T( ví d II.4.2.3, ta bi t r&ng: j 3n +1 − 2n − 3 1 = − j 4 ⋅ 3n 3 j =2 3 Và j 2n +1 − n − 2 1 = − j 2n 2 j =2 2 n n cn = 6 ⋅ 3n Nên V y n +1 3n +1 − 2n − 3 1 −n−2 1 n 2 4 2 − − ⋅ − n 4⋅3 3 2n 2 3 n +1 3 − 2n − 3) − 6 ⋅ 3n −1 − 4 ( 2n +1 − n − 2 ) + 4 ⋅ 2 n −1 ( 2 5 ⋅ 3n 7 = − 3 ⋅ 2n +1 + n + 2 2 n 5⋅3 7 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 Tìm s h ng t ng quát c a dãy s ( un ) trong các tr )ng h p sau sau: ng pháp nêu trên: 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. u1 = a , un4+1un − un2+1un + un − aun +1un − bun +1un4 + bun +1un2 − 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 [email protected] Trang 20 10/1/2008