Chuyên đề Tìm số hạng tổng quát của dãy truy hồi tuyến tính cấp 2 để giải quyết một số bài toán về dãy số

Chuyên đề ôn thi học sinh giỏi Quốc gia Chuyên đề: TÌM SỐ HẠNG TỔNG QUÁT CỦA DÃY TRUY HỒI TUYẾN TÍNH CẤP 2 ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN VỀ DÃY SỐ Trường THPT chuyên Hưng Yên Phần I: Tìm số hạng tổng quát của dãy truy hồi tuyến tính cấp 2. I. LÝ THUYẾT: Đó là các dãy số thực có dạng n 2 n 1 nu au bu   (*) với mọi n 0 , trong đó a và b là các hằng số thực. Cách xác định số hạng tổng quát của dãy như sau: Xét phương trình ẩn t sau đây: 2t at b 0   (**) được gọi là phương trình đặc trưng của (*). Phương trình có biệt thức 2a 4b   . Trường hợp 1: 2a 4b 0    khi đó (**) có hai nghiệm thực phân biệt 1 2t ; t . Số hạng tổng quát của (*) có dạng n nn 1 2u x.t y.t  , với mọi n 0 và x, y là hai số thực tuỳ ý; x và y sẽ hoàn toàn xác định khi cho trước 0u và 1u . Trường hợp 2: 2a 4b 0    khi đó (**) có một nghiệm kép thực t. Số hạng tổng quát của (*) có dạng n n 1nu x.t y.nt   , với mọi n 0 ( ở đây ta qui ước 10 0  ) và x, y là hai số thực tuỳ ý; x và y sẽ hoàn toàn xác định khi cho trước 0u và 1u . Trường hợp 3: 2a 4b 0    , ( **) có hai nghiệm phức. Thuật toán làm trong trường hợp này như sau: Bước 1: Giải phương trình 2t at b 0   và nhận được nghịêm phức a iz . 2    Bước2: Đặt r = | z | là module của z, còn Argz  , ta nhận được n nu r (pcos n q sin n )   với mọi p, q là các số thực. Bước 3: Xác định p, q theo các giá trị cho trước 0 1u ;u . Về cơ sở lí thuyết của cách làm trên được chứng minh bằng kiến thức của đại số tuyến tính. Ở đây, tôi xin trình bày chứng minh trường hợp 1 và trường hợp 2 bằng kiến thức trung học phổ thông. Trường hợp 1: 0  (**) có hai nghiệm phân biệt 1 2t , t khi đó theo định lí Vi-et ta có: 1 2 1 2 t t a t t b      . Khi đó n 1 1 2 n 1 2 n 1u (t t )u t t u    2 n n 1 1 n 2 n 1 n 1 2 n 1 1 n 2 2 1 1 0u t u t (u t u ) t (u t u ) ... t (u t u )            . Như vậy nn 1 1 n 2 1 1 0u t u t (u t u )    (1); Tương tự nn 1 2 n 1 1 2 0u t u t (u t u )    (2). Trừ từng vế (2) cho (1) ta có: Chuyên đề ôn thi học sinh giỏi Quốc gia n n 1 2 n 1 2 0 1 1 1 0 2(t t )u (u t u )t (u t u )t     . Do 1 2t t nên n n1 2 0 1 1 0 n 1 2 1 2 1 2 (u t u ) (u t u )u t t t t t t       . Vậy nu có dạng n n n 1 2u x.t y.t  với x,y là hai số thực. Trường hợp 2: 0  khi đó 2ab 4   , (**) có nghiệm kép at 2  . Ta có 2 n n 1 n n 1 n 1 n n n 1 1 0u 2t.u t u u tu t(u tu ) ... t (u tu )            Như vậy nn 1 n 1 0u tu t (u tu )    (3); Tương tự n 1n n 1 1 0u tu t (u tu )     (4); n 2n 1 n 2 1 0u tu t (u tu )      (5); . 1 0 1 0u tu u tu   (n+3). Nhân hai vế của (4) với t, hai vế của (5) với 2t , , hai vế của (n+3) với nt và cộng lại ta được: n 1 nn 1 0 1 0u t .u n.t .(u tu )      . Do đó nu có dạng n n 1xt yn.t  với x, y là hai số thực. II. CÁC VÍ DỤ: Ví dụ 1: X¸c ®Þnh sè h¹ng tæng qu¸t cña d·y sè tho¶ m·n: 0 1 n 2 n 1 n u 1,u 2 .1 2u u u , n 0 3 3           Giải: Phương trình đặc trưng 2 1 2t t 0 3 3    của dãy có hai nghiệm thực phân biệt là 1 2 2t , t 1 3    . Do đó n n n 2u x. y.( 1) 3        với x, y . Ta lại có: 0 1 x y 1 9xu 1 5 2u 2 4x y 2 y 53                  . Vậy n nn 9 2 4u ( ) ( 1) , n 0. 5 3 5      Trong công thức tổng quát (*), khi chọn những giá trị a và b thích hợp ta có thể đưa ra đề toán thuộc vào trường hợp 2 và 3 được nói đến ở trên. Hoặc là bằng cách biến đổi nu ta cũng có thể đưa ra được những đề toán khá hay. Chẳng hạn trong đề bài trên: Chuyên đề ôn thi học sinh giỏi Quốc gia *) Đặt n n 1u v  , 0 0 1 1 1u 1 v 1;u 2 v 2       . n n 1 n 2 n 1 n n 2 n 2 n 1 n n n 1 1 2 1 1 2 3v vu u u v , n 0 3 3 v 3v 3v v 2v                     . Như vậy ta có đề toán mới như sau: Xác định số hạng tổng quát của dãy số thoả mãn: 0 1 n n 1 n 2 n n 1 1v 1, v 2 3v vv , n 0. v 2v             *) Đặt n nu ln v , 2 0 0 1 1u 1 v e;u 2 v e .      2 n3n 2 n 1 n n 2 n 1 n n 2 n 1 1 2 1 2 vu u u ln v ln v ln v v , n 0 3 3 3 3 v                 . Như vậy ta có đề toán mới như sau: Xác định số hạng tổng quát của dãy số thoả mãn: 2 0 1 2 n3n 2 n 1 v e,v e vv , n 0. v           Ví dụ 2: Tìm nu biết 1 2 n 1 n n u u a.u b.u c       . Trong đó: 2a b 1, 0,a 1     . Giải: Từ (*) 2 2n 1 n n n 1 n nu a.u b.u c u a.u b.u c 0         2 2 2 2 2 2 n 1 n n n 1 n n 1 n n(u a.u ) b.u c u 2.a.u .u a u b.u c           2 2 2 2 2 n 1 n n 1 n n 1 n n 1 nu 2.a.u .u u (a b) c u 2.a.u .u u c            n 1  2 2 2 2 n 1 n n 1 n n n n 1 n 1u 2.a.u .u u u 2.a.u .u u         2 2 n 1 n 1 n n 1 n 1 n 1 n 1 n 1 n n 1u u 2.a.u (u u ) (u u ).(u 2.a.u u ) 0                (**) Bằng quy nạp ta CM được: 1 2 n n 1 n 1u u ... u ... u u 0        n 1 n n 1u 2.a.u u 0     Từ đó: 2 1 2 n 1 n n 1 u ;u a. b. c u 2.a.u u 0              Ta tính được nu theo dạng (1). Chuyên đề ôn thi học sinh giỏi Quốc gia Phần II: Áp dụng việc tìm số hạng tổng quát của dãy truy hồi tuyến tính cấp 2 trong một số bài toán về dãy số. Ví dụ 1: Cho dãy n(u ) thoả mãn 0 1 n 2 n 1 n u 0;u 1 .1u u u ,n 0 2         Tìm nlim u . Giải: Phương trình đặc trưng của dãy là 2 1t t 0 2    có một nghiệm phức là 1 it 2   ; |t|= 1 2 , Argt= 4  . Do đó số hạng tổng quát của dãy có dạng n n 2 n nu (x.cos ysin ),n 0;x, y . 2 4 4             Từ giả thiết 0 1u 0;u 1  ta suy ra x= 0; y= 2. Vậy số hạng tổng quát của dãy là n n nn n 2 2 nu 2sin ( ) sin , lim u 0 4 2 4( 2)      vì n n 2| u | 0. ( 2)   Ví dụ 2: Cho dãy n(x ) thoả mãn 0 1 n 1 n n 1 x 1;x 5 . x 6x x , n 1         Hãy tìm n nlim x { 2x }. Giải: Bằng phương pháp xác định số hạng tổng quát ở trên, ta xác đinh được số hạng tổng quát của dãy là n nn 2 2 2 2x ( )(3 2 2) (3 2 2) 4 4           . Hay 2n 1 2n 1n 1 1x ( 2 1) ( 2 1) 2 2 2 2      2n 1 2n 1 n 2n 1 2n 1 2n 1 n 2n 1 2n 1 2n 1 k 2n 1 k k 2n 1 k k n 2n 1 2n 1 k 0 k 0 1 12x ( 2 1) ( 2 1) 2 2 2 12x ( 2 1) ( 2 1) ( 2 1) 2 12x ( 2 1) C ( 2) C ( 2) ( 1) 2                                            Chuyên đề ôn thi học sinh giỏi Quốc gia 2n 1 n 2t 1 2n 1 2k 1 2t 1 (n t ) 2n 1 2n 1 2t 1 1 t 0 C ( 2) C 2 .                  n 2n 1 2t 1 (n t ) n 2n 1 t 0 2x ( 2 1) C 2          n 2n 1 2t 1 n t n 2n 1 t 0 2n 1 2n 1 n n n 0 2 1 1 0 ( 2 1) 1 2x C .2 2x 2x ( 2 1) 2x ( 2 1)                                 2(2n 1) 4n 2 n n 4n 2 n n 1 1x 2x (1 ( 2 1) ) (1 ( 2 1) ) 2 2 2 2 1 1 1lim x 2x lim( 2 1) . 2 2 2 2 2 2               Ví dụ 3: Cho dãy số nu được xác định như sau: n n n (2 3) (2 3)u ;n 0,1,2.... 2 3      a. Chứng minh rằng nu là số nguyên với mọi n = 0, 1, 2, . b. Tìm tất cả số hạng của dãy chia hết cho 3. Giải: a) Với 0 1n 0 u 0;n 1 u 1.      Đặt 2 3; 2 3      , ta có 4 . 1       Dễ thấy nu là số hạng tổng quát của dãy số cho bởi công thức: 0 1 n 2 n 1 n u 0;u 1 u 4u u 0        Do 0 1u 0;u 1   ; n 2 n 1 nu 4u u   nên nu  , n 0,1,...  . b) Ta có n 2 n 1 n 1 nu 3u (u u )     . Do n 1u   nên n 2 n 1 nu u u   (mod 3). Bằng phép tính trực tiếp ta thấy 8 số hạng đầu tiên của dãy 0 1 7u ,u ,...,u khi chia cho 3 có các số dư tương ứng là 0,1,1,0,2,2,0,1. Suy ra n 6 nu u  (mod 3). Từ đó ta thấy trong dãy số nói trên mọi số hạng có dạng 3ku , k=0,1,2 chia hết cho 3 và chỉ những số hạng ấy mà thôi. Chuyên đề ôn thi học sinh giỏi Quốc gia Ví dụ 4: (Thi HSG QG năm 2011): Cho dãy số nguyên n(a ) xác định bởi: a0 = 1, 1 n n 1 n 2a 1,a 6a 5a     với mọi n 2 . Chứng minh rằng 2012a 2010 chia hết cho 2011. Giải: Cách 1: Xét dãy ( nb ) được xác định như sau: 0 1 n n 1 n 2b 1;b 1;b 6b 2016b      , với mọi n 2 . Dãy này có phương trình đặc trưng là 2x 6x 2016 0   có hai nghiệm là x = -42, y = 48. Từ đây suy ra số hạng tổng quát của dãy là n n n 41.48 49.( 42)b , n . 90      Ngoài ra, ta cũng dễ dàng chứng minh bằng qui nạp rằng n na b (mod2011), n .   Do đó ta chỉ cần chứng minh 2012b 1 0(mod 2011)  . Ta có: 2012 2012 2012 41.48 49.( 42) 90b 1 . 90      Do 2011 là số nguyên tố và 2011, 90 là hai số nguyên tố cùng nhau nên ta chỉ cần chứng minh: 2012 201241.48 49.( 42) 90 0(mod 2011).    (1) Mà theo định lí Fermat nhỏ , ta có 2012 2012 2 241.48 49.( 42) 90 41.48 49.42 90(mod 2011)      = 90. 2b +90 = 90 [6(-1)+2016.1]+90 = 90.2010 + 90 = 90.20110 (mod 2011). Vậy (1) đúng, bài toán được chứng minh. Cách 2: Phương trình đặc trưng của dãy đã cho là 2x 6x 5 0   có hai nghiệm là 3 14 và 3 14 , do đó ta tìm được số hạng tổng quát của dãy là na  n n(7 2 14)(3 14) (7 2 14)(3 14) 14      n 1 n 1 n n ( 7 14)(3 14) (7 14)(3 14) 14 u 2v .            Trong đó n 1 n 1 n 1 n 1 n n (3 14) (3 14) (3 14) (3 14)u ,v 2 2 14            Sử dụng công thức khai triển nhị thức Niu-Tơn, ta có Chuyên đề ôn thi học sinh giỏi Quốc gia 1005 1005 2k 2011 2k k 2011 2k 2011 2k k 2012 2011 2011 k 0 k 1 u C 3 14 3 C 3 14 .        Do 1<2k<2011 với 1 k 1005  và 2011 là số nguyên tố nên 2k 1 2k 2010 2011 CC 2011( ) 2011 2k    Mặt khác, theo định lí Fermat nhỏ thì 20113 3 (mod 2011). Do vậy, kết hợp các lập luận lại với nhau ta được 2012u 3 (mod 2011) (2) Tương tự với nv , ta cũng sử dụng khai triển Niu-Tơn và thu được 1006 1005 2k 1 2012 2k k 1 2k 1 2012 2k k 1 2012 2011 2011 k 1 k 1 v C 3 14 C 3 14 .           Đến đây, cũng bằng cách sử dụng tính nguyên tố của 2011, ta thấy 2k 2 2k 1 2010 2011 CC 2011 2011 2k 1         Với  k 1,2,...,1005 . Vì vậy 1005 2012v 14 (mod 2011). Do 2 214 2025 2011 45 2011 45     (mod 2011) nên áp dụng định lí Fermat nhỏ, ta có 1005 201014 45 1  (mod 2011). Suy ra 2012v 1 (mod 2011). (3) Từ (2) và (3), ta có 2012a 2010 3 2.1 2010 0      (mod 2011) Bài toán được chứng minh xong. Ví dụ 5: Cho ( nu ) xác định:   1 2 n 1 n n 1 u 7 u 50 u 4.u 5.u 1975 1          CMR: 1996u chia hết 1997 Giải: Tìm công thức xác định số hạng TQ: Xét dãy n n n 1 n n 1 1975x u x 4.x 5.x 8        Chuyên đề ôn thi học sinh giỏi Quốc gia Giải PT đặc trưng: 2 X 1 X 4.X 5 0 X 5        n n n n n n 1747 2005 1747.( 1) 2005.( 1) 1975x .5 ( 1) . u 30 3 120 8             1996 1996 1747.5 49675u 120     1996 1996u .120 1747.(5 1) 1997.24     Suy ra 1996u chia hết 1997 vì 19965 1 (mod 1997) Ví dụ 6: Cho dãy số  na : 0 2 n 1 n n a 2 a 4a 15a 60      Chứng minh rằng số 2n 1A (a 8) 5   có thể biểu diễn thành tổng bình phương của ba số nguyên liên tiếp với mọi n 1 . Giải: 2 n 1 n n 2 2 n 1 n n a 4a 15a 60 (a 4a ) 15a 60          2 2 n 1 n 1 n na 8a a a 60 0     (1) Áp dụng biểu thức trên với n ta có 2 2n n 1 n n 1a 8a a a 60 0     (2) Trừ từng vế (1) và (2) ta có 2 2 n 1 n 1 n 1 n 1 n n 1 n 1 n 1 n 1 n a a 8(a a )a 0 (a a )(a a 8a ) 0(*)                  Từ giả thiết suy ra n n 1 n na 0, n a 4a a     suy ra n(a ) là dãy tăng. Suy ra n 1 n 1a a 0   . Từ (*) suy ra n 1 n 1 na a 8a 0    . Giải phương trình đặc trưng 2 1,2t 8t 1 0 t 4 15      n n n 2n 2n 2n a (4 15) (4 15) a (4 15) (4 15)           Với mỗi n 1 tồn tại k để n n(4 15) (4 15) 15k    2n n 2 2n 2n 2 2 2n (4 15) (4 15) 15k (4 15) (4 15) 2 15k a 15k 2                 Chuyên đề ôn thi học sinh giỏi Quốc gia 2 2 2 2 2 2n 1 1A (a 8) (15k 10) 3k 2 (k 1) k (k 1) 5 5            (đpcm). Ví dụ 7: Cho dãy ( nu ) xác định: 1 2 n 2 n n 1 u 0,u 1 u u u 1        CMR: p là số nguyên tố p>5: thì p p 1u .(u 1)  chia hết cho p. Giải: Xét dãy: 2 11n n n n nx u x x x      Suy ra số hạng tổng quát: 1 1 1 5 1 1 5 2 25 n n nx                   . 1 1 1 5 1 1 5 1 2 25 n n nu                          11 .2 ( 5 1) ( 5 1) ( 5 1) ( 5 1) 2 5 p p p pu        .    1 1( 5 1) ( 5 1) ( 5 1) ( 5 1)2 2 5 p p p p        0 0 0 0 1 1( ( 5) ( 5) ( 1) ) ( ( 5) ( 5) ( 1) ) 2 2 5 p p p p k k k k p k k k k k p k p p p p k k k k C C C C                 1 1 2 2 2 2 2 1 2 1 0 0 1 11 .2 ( 2( 5) ( 2( 5) 2 2 5 p p p k k k k p p p k k u C C             1 2 2 2 1 0 1 .2 ( )5 p p k k k p p p k u C C       ; ! 0( )! ! k p pC p k k    (mod ) 1 1p k p      1 1 0 0 2 22 . 1 .5 .5 5 1 p p p p p p pu C C        (mod )p (2) Ta có 15 1p  (mod )p 1 1 2 2(5 1)(5 1) 0 p p      (mod )p . Nếu 1 25 1 0 p   (mod )p Từ (2)  2 . 1 0p pu   (mod )p mà (2;p)=1. 1 0pu   (mod )p ( 1)p pu u p   (đpcm) Nếu 1 25 1 p  (mod )p 1 25 1 2 p    (mod )p Từ (2):  2 . 1 2p pu   (mod )p ; (2,P)=1 2 2(mod ) 2 . 0(mod )p p pp u p    , (2,P)=1 0(mod ) ( 1)p p pu p u u p     (Đpcm). Phần III. Một số bài tập tự luyện: Chuyên đề ôn thi học sinh giỏi Quốc gia Bài 1: Tìm số hạng tổng quát của dãy n(u ),n 0 xác định bởi: 0 1 n 2 n 1 n u u 1 . u 6u 9u ,n 0        Bài 2: Cho dãy số n(u ),n 0 xác định như sau: n n n 3 5 3 5u ( ) ( ) 2,n 1,2,.... 2 2       a. Chứng minh rằng nu là số tự nhiên n 1,2,....  b. Chứng minh rằng 2011u là số chính phương. Bài 3: Cho dãy số n(u ),n 0 xác định như sau: 0 1 n 2 n 1 n u 0,u 1 u 2u 4u , n 0.          Tìm n nn n u ulim ;lim . 2 2