Xem mẫu

  1. Hội thảo khoa học, Hưng Yên 25-26/02/2017 MỘT SỐ BÀI TOÁN VỀ DÃY SỐ TRUY HỒI TUYẾN TÍNH CẤP HAI Quách Thị Tuyết Nhung THPT Chuyên Hưng Yên 1 Dãy số truy hồi tuyến tính cấp hai 1.1 Các định nghĩa và ví dụ Định nghĩa 1. Dãy số truy hồi tuyến tính cấp hai là dãy số cho bởi công thức un+2 = aun+1 + bun (1.1) với mọi n ≥ 0 và a, b là các hằng số thực. Ví dụ 1. Dãy số (un ) cho bởi công thức   u0 = 1  u1 = 2 1 2 u = − u n +1 + u n , ∀ n ≥ 0  n +2 3 3 là một dãy số truy hồi tuyến tính cấp hai. 1.2 Phương pháp xác định số hạng tổng quát của dãy số truy hồi tuyến tính cấp hai Để xác định công thức số hạng tổng quát của dãy số truy hồi tuyến tính cấp hai ta thực hiện như sau: Xét phương trình đặc trưng của (1.1) t2 − at − b = 0. (1.2) Phương trình có biệt thức ∆ = a2 + 4b. Ta xét các trường hợp: Trường hợp 1. ∆ > 0 khi đó (1.2) có hai nghiệm thực phân biệt t1 , t2 . Số hạng tổng quát của (1.1) có dạng un = x.t1n + y.t2n , ∀n ≥ 0, x, y ∈ R. 278
  2. Hội thảo khoa học, Hưng Yên 25-26/02/2017 x, y sẽ hoàn toàn xác định khi cho trước u0 , u1 . Trường hợp 2. ∆ = 0 khi đó (1.2) có một nghiệm kép thực t. Số hạng tổng quát của (1.1) có dạng un = x.tn + y.n.tn−1 , ∀n ≥ 0 (ta qui ước 0−1 = 0) x, y ∈ R. x, y sẽ hoàn toàn xác định khi cho trước u0 , u1 . Trường hợp 3. ∆ < 0 khi đó (1.2) có hai nghiệm phức. Thuật toán tìm số hạng tổng quát trong trường hợp này như sau: Bước 1. Giải phương trình t2 − at − b = 0 ta nhận được hai nghiệm phức √ a + i. −∆ z= . 2 Bước 2. Đặt r = |z| là module của Z, ϕ = Argz, ta nhận được un = r n .( p cos 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ị u0 , u1 cho trước. Cách làm trên được chứng minh bằng kiến thức đại số tuyến tính. Ở đây, tôi sẽ 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 khi đó (1.2) có hai nghiệm thực phân biệt t1 , t2 , theo định lí Vi-et ta có t1 + t2 = a, t1 .t2 = −b. Khi đó un+1 = (t1 + t2 )un − t1 .t2 .un−1 . Ta có un+1 − t1 un = t2 (un − t1 un−1 ) = t22 (un−1 − t1 un−2 ) = · · · = t2n (u1 − t1 u0 ). Như vậy un+1 − t1 .un = t2n (u1 − t1 u0 ). (1.3) Tương tự un+1 − t2 .un = t1n (u1 − t2 u0 ). (1.4) Trừ từng vế (1.4) và (1.3) ta có (t1 − t2 )un = (u1 − t2 u0 )t1n − (u1 − t1 u0 )t2n . Do t1 6= t2 nên u1 − t2 u0 n u1 − t1 u0 n un = t − t . t1 − t2 1 t1 − t2 2 279
  3. Hội thảo khoa học, Hưng Yên 25-26/02/2017 Vậy un có dạng un = x.t1n + y.t2n , ∀n ≥ 0, x, y ∈ R. − a2 a Trường hợp 2: ∆ = 0 khi đó b = , (1.2) có nghiệm kép t = . Ta có 4 2 un+1 = 2tun − t2 un−1 ⇔ un+1 − tun = t(un − tun−1 ) = · · · = tn (u1 − tu0 ) Như vậy, un+1 − tun = tn (u1 − tu0 ) (1.5) un − tun−1 = tn−1 (u1 − tu0 ) (1.6) n −2 un−1 − tun−2 = t (u1 − tu0 ) (1.7) .................................. (1.8) u1 − tu0 = u1 − tu0 (1.9) Nhân hai vế của (1.6) với t, hai vế của (1.7) với t2 , . . . , hai vế của (1.9) với tn và cộng lại, ta được un+1 = tn+1 .u0 + n.tn .(u1 − tu0 ). Do đó un có dạng x.tn + y.n.tn−1 với x, y là hai số thực. 2 Một số ví dụ Ví dụ 2. Xác định số hạng tổng quát của dãy số thỏa mãn 1 2 u0 = 11, u1 = 2, un+2 = − un+1 + un , ∀n = 0, 1, 2 . . . 3 3 Lời giải. 1 2 Xét phương trình đặc trưng t2 + t − = 0 của dãy có hai nghiệm thực phân biệt là 3 3 2 t1 = , t2 = −1 3 Do đó, 2 un = x.( )n + y.(−1)n , ∀ x, y ∈ R. 3 Ta lại có  x+y = 1  x=9  (  u0 = 1 5 ⇔ 2 ⇔ 4 u1 = 2 x−y = 2 y = −  3 5 9 2 n 4 Vậy un = ( ) − (−1)n , ∀n ≥ 0. 5 3 5 Ví dụ 3. Xác định số hạng tổng quát của dãy số thỏa mãn 1 −3vn vn+1 v0 = 1, v1 = , vn+2 = , ∀n ≥ 0. 2 vn − 2vn+1 280
  4. Hội thảo khoa học, Hưng Yên 25-26/02/2017 Lời giải. Ta có −3.vn .vn+1 1 1 2 v n +2 = ⇔ =− + vn − 2.vn+1 v n +2 3.vn+1 3.vn 1 1 Bằng việc đặt un = ta được v0 = 1, v1 = suy ra u0 = 1, u1 = 2. Bài toán qui về việc tìm vn 2 số hạng tổng quát của dãy số trong ví dụ 1. Nhận xét. Bằng cách biến đổi un , ta có những bài toán khá hay. Chẳng hạn, trong ví dụ 1 khi đặt un = lnvn ta được bài toán Xác định số hạng tổng quát của dãy số thỏa mãn s v2n v0 = e, v1 = e2 , vn+2 = 3 , ∀n ≥ 0. v n +1 3 Một số dạng toán về dãy số truy hồi tuyến tính cấp hai Trước hết, ta xét một số bài toán được giải quyết thông qua việc tìm số hạng tổng quát của dãy truy hồi tuyến tính cấp hai. Ví dụ 4. Cho dãy số un thỏa mãn 1 u0 = 0, u1 = 1, un+2 = un+1 − un , ∀n ≥ 0. 2 Tìm lim un . Lời giải. 1 Phương trình đặc trưng của dãy là t2 − t + = 0. Phương trình có một nghiệm phức 2 1+i 1 π t= , |t| = √ , Argt = . 2 2 4 Do đó, số hạng tổng quát của dãy có dạng √ n 2 nπ nπ un = ( ).( x cos + y sin ), ∀n ≥ 0, x, y ∈ R. 2 4 4 Từ giả thiết u0 = 0, u1 = 1 suy ra x = 0, y = 2. Vậy số hạng tổng quát của dãy là √ nπ 2 2 un = 2sin ( )= √ . 4 2 ( 2) n 2 Khi đó lim un = 0 vì |un | ≥ √ → 0. ( 2) n 281
  5. Hội thảo khoa học, Hưng Yên 25-26/02/2017 Ví dụ 5. Cho dãy ( xn ) thỏa mãn x0 = 1, x1 = 5, xn+1 = 6xn − xn−1 , ∀n ≥ 1. √ Tìm lim( xn 2xn ). Lời giải. Bằng phương pháp xác định số hạng tổng quát ở trên, ta xác định được số hạng tổng quát của dãy là √ √ 2+ 2 √ n 2− 2 √ xn = ( )(3 + 2 2) + ( )(3 − 2 2)n . 4 4 Hay 1 √ 1 √ xn = √ ( 2 + 1)2n+1 + √ ( 2 − 1)2n+1 2 2 2 2 √ 1 √ 1 √ ⇔ 2xn = ( 2 + 1)2n+1 + ( 2 − 1)2n+1 2 2 √ √ + 1 √ √ ⇔ 2xn − ( 2 − 1) 2n 1 = [( 2 + 1)2n+1 − ( 2 − 1)2n+1 ] 2 √ √ n +1 ( n − t ) ⇔ 2xn − ( 2 − 1)2n+1 = ∑ (2n 2t+1 )2 ∈ Z. √ t =0 Lại có 0 < 2 − 1 < 1 suy ra √ 0 < ( 2 − 1)2n+1 < 1 √ n  2n + 1  [ 2xn ] = ∑ .2n−t t =0 2t + 1 √ √ √ 2xn − [ 2xn ] = ( 2 − 1)2n+1 √ √ 2xn = ( 2 − 1)2n+1 √ 1 √ 1 √ √ Nên xn 2xn = √ [1 + ( 2 − 1)2(2n+1) = √ [1 + ( 2 − 1)4n+2 ]. Vậy lim xn 2xn = 2 2 2 2 1 1 √ 1 √ + √ lim( 2 − 1)4n+2 = √ . 2 2 2 2 2 2 Ví dụ 6. Cho dãy số (un ) được xác định bởi u1 = 7, u2 = 50, un+1 = 4.un + 5.un−1 − 1975 Chứng minh rằng u1996 chia hết cho 1997. Lời giải. 1975 Xét dãy xn = un − . Ta có xn+1 = 4xn + 5xn−1 . 8 Phương trình đặc trưng x2 − 4x − 5 = 0 có hai nghiệm x = 1, x = 5. Ta xác định được −1747 n 2005 xn = .5 + (−1)n . . 30 3 Do đó −1747.(−1)n + 2005.(−1)n 1975 un = + . 120 8 282
  6. Hội thảo khoa học, Hưng Yên 25-26/02/2017 Suy ra −1747.51996 + 49675 u1996 = . 120 Từ đó u1996 .120 = −1747.(51996 − 1) + 1997.24 Vì 51996 ≡ 1 (mod 1997) nên u1996 chia hết cho 1997. Ví dụ 7. Cho dãy số ( an ) xác định bởi công thức q a0 = 2, an+1 = 4.an + 15.a2n − 60. 1 Chứng minh rằng số A = ( a2n + 12) có thể biểu diễn thành tổng của ba số nguyên liên tiếp 5 với mọi n ≥ 1. Lời giải. Từ giả thiết p an+1 − 4an = 15a2n − 60 ⇔ ( an+1 − 4an )2 = 15a2n − 60 ⇔ a2n+1 − 8.an+1 .an + a2n + 60 = 0, ∀n ≥ 1 Ta có a2n − 8an−1 an + a2n−1 + 60 = 0. Từ đó suy ra a2n+1 − a2n−1 − 8( an+1 − an−1 ) an = 0 ⇔ ( an+1 − an−1 )( an+1 + an−1 − 8an ) = 0. Từ giả thiết suy ra an ≥ 0, ∀n. Như vậy, an+1 ≥ 4an > an dãy ( an ) là một dãy tăng. Suy ra, an+1 − an−1 6= 0. Từ đó an+1 + an−1 − 8an = 0. Giải phương trình đặc trưng t2 − 8t + 1 = 0 √ √ n √ n ta được t1,2 = 4 ± √ 15. Ta tìm được√ 2na n = ( 4 + 15 ) + ( 4 − 15) . 2n Suy ra a2n = (4 + 15) + (4 − 15) . Với mỗi n ≥ 1, tồn tại số k ∈ N để √ √ √ (4 + 15)n + (4 − 15)n = 15k √ √ ⇔ [(4 + 15)n + (4 − 15)n ]2 = 15k2 √ √ ⇔ (4 + 15)2n + (4 − 15)2n + 2 = 15k2 . Suy ra a2n = 15k2 − 2. 1 1 Ta có A = ( a2n + 12) = (15k2 + 10) = 3k2 + 2 = (k − 1)2 + k2 + (k + 1)2 . Bài toán được 5 5 chứng minh. Đôi khi, việc bắt đầu từ công thức tổng quát của dãy số để tìm hệ thức truy hồi giữa các số hạng trong dãy cũng giúp ta giải quyết được khá nhiều bài tập. Ta xét một số bài toán như vậy 283
  7. Hội thảo khoa học, Hưng Yên 25-26/02/2017 √ √ (2 + 3) n − (2 − 3) n Ví dụ 8. Cho dãy (un ) thỏa mãn un = √ , ∀n = 0, 1, 2, . . . . 2 3 a. Chứng minh rằng un là số nguyên ∀n = 0, 1, 2, . . . . b. Tìm tất cả các số hạng của dãy chia hết cho 3. Lời giải. a. Với n = √ 0 thì u0 = √ 1, n = 1 thì u1 = 1. Đặt α = 2 + 3, β = 2 − 3. Ta có: α + β = 4, α.β = 1. Dễ thấy un là số hạng tổng quát của dãy số được cho bởi công thức u0 = 0, u1 = 1, un+2 − 4un+1 + un = 0. Do u0 , u1 ∈ Z, un+2 = 4un+1 − un nên un ∈ Z, ∀n = 0, 1, . . . . b. Ta có un+2 = 3un+1 + (un+1 − un ). Do un+1 ∈ Z nên un+2 ≡ un+1 − un (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 u0 , u1 , . . . , u7 khi chia cho 3 có các số dư tương ứng là 0, 1, 1, 0, 2, 2, 0, 1. Suy ra u n +6 ≡ u n (mod 3). Từ đó ta thấy trong dãy số nói trên mọi số hạng có dạng u3k , k = 0, 1, 2, . . . chia hết cho 3 và chỉ nhưng số hạng đó mà thôi. √ √ Ví dụ 9. Chứng minh rằng với mọi n ∈ N thì [( 3 + 2)2n ] không chia hết cho 5 ( kí hiệu [ x ] chỉ phần nguyên của số x. Lời giải. √ √ √ √ √ Đặt A = ( 3 + 2)2n = (5 + 2 6)n và x1 = 5 + 2 6, x2 = 5 − 2 6. Khi đó x1 + x2 = 10, x1 .x2 = 1, hay x1 , x2 là nghiệm của phương trình x2 − 10x + 1 = 0. √ √ Đặt Sn = (5 + 2 6)n + (5 − 2 6)n , n ∈ N. Ta có Sn+2 − 10Sn+1 + Sn = 0 ⇔ Sn+2 = 10Sn+1 − Sn . Mặt khác S0 = 2, S1 √= 10, bằng phương pháp qui nạp ta suy ra Sn là số nguyên với mọi n ∈ N. Vì 0 < (5 − 2 6)n < 1 nên √ √ √ √ q (5 + 2 6) n + (5 − 2 6) n − 1 ≤ (5 + 2 6) n < (5 + 2 6) n + (5 − 2 6) n . Suy ra √ √ Sn − 1 ≤ (5 + 2 6)n < Sn ⇒ [(5 + 2 6)n ] = Sn − 1, ∀n ∈ N. Lại có Sn+2 ≡ −Sn (mod 5), dẫn tới Sn ≡ −Sn−2 (mod 5). Vậy S2k ≡ (−1)k S0 (mod 5) S2k ≡ (−1)k .2 (mod 5)   ⇒ S2k+1 ≡ (−1)k S1 (mod 5) S2k+1 ≡ (−1)k .10 ≡ 0 (mod 5) √ √ √ Mà [(5 + 2 6)n ] = Sn − √1 nên [(5 + 2 6)n ] ≡ 2.(−1)k − 1 (mod 5) hoặc [(5 + 2 6)n ] ≡ −1 (mod 5) suy ra [(5 + 2 6)n ] không chia hết cho 5. 284
  8. Hội thảo khoa học, Hưng Yên 25-26/02/2017 √ √ Ví dụ 10. Chứng minh rằng biểu thức Sn = (9 + 4 5)n + (9 − 4 5)n nhận giá trị nguyên và không chia hết cho 17 với mọi n ∈ N. Lời giải. Ta chứng minh được S0 = 2, S1 = 18, Sn+2 = 18Sn+1 − Sn . Suy ra Sn ∈ Z. Lại có Sn+3 + Sn = 18Sn+2 − Sn+1 + Sn = 17(Sn+2 + Sn+1 ) chia hết cho 17. Ta có S0 = 2 không chia hết cho 17 nên S3k cũng không chia hết cho 17. Ta có S1 = 18 không chia hết cho 17 nên S3k+1 cũng không chia hết cho 17. Ta có S2 = 322 không chia hết cho 17 nên S3k+2 cũng không chia hết cho 17. Vậy Sn không chia hết cho 17 với mọi n ∈ N. Ví dụ 11. Tìm số nguyên d lớn nhất sao cho d|16n + 10n − 1 với mọi n ∈ N∗ . Lời giải. Với mỗi n ∈ N∗ , đặt un = 16n + 10n − 1, vn = un + 1 = 16n + 10n và d là ước chung lớn nhất của un với mọi n ∈ N∗ . Ta kiểm tra được dãy số (vn ) thỏa mãn hệ thức truy hồi vn+2 − (16 + 10)vn+1 + 16.10vn = 0, ∀n ∈ N∗ . Từ đó un+2 = 26un+1 − 160un − 135, ∀n ∈ N∗ . Vì d là ước của un , un+1 , un+2 nên d là ước của 135. Mặt khác d là ước của u1 = 25, suy ra d|(135, 25) = 5. Vậy d = 5. Các bài toán liên quan đến công thức số hạng tổng quát của dãy truy hồi tuyến tính cấp hai cũng xuất hiện nhiều trong các đề thi trong nước và khu vực. Ta xét một số bài toán như vậy. Ví dụ 12 (VMO 2011). Cho dãy số nguyên ( an ) xác định bởi a0 = 1, a1 = −1, an = 6an−1 + 5an−2 , ∀n ≥ 2. Chứng minh rằng a2012 − 2010 chia hết cho 2011. Lời giải. Xét dãy (bn ) được xác định như sau: b0 = 1, b1 = −1, bn = 6bn−1 + 2016bn−2 , ∀n ≥ 2 Dãy này có phương trình đặc trưng x2 − 6x − 2016 = 0, phương trình này có hai nghiệm x = −42, y = 48. Từ đây suy ra số hạng tổng quát của dãy là 41.48n + 49.(−42)n bn = , ∀n ∈ N. 90 285
  9. Hội thảo khoa học, Hưng Yên 25-26/02/2017 Ngoài ra, ta cũng dễ dàng chứng minh được bằng qui nạp rằng a n ≡ bn (mod 2011), ∀n ∈ N. Do đó ta chỉ cần chứng minh b2012 + 1 ≡ 0 (mod 2011). Ta có 41.482012 + 49.(−42)2012 + 90 b2012 + 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 41.482012 + 49.(−42)2012 + 90 ≡ 0 (mod 2011). Thật vậy, theo định lí Fecma nhỏ ta có 41.482012 + 49.(−42)2012 + 90 ≡ 41.482 + 49.4262 + 90 (mod 2011). Lại có: 41.482 + 49.4262 + 90 = 90.b2 + 90 = 90[6.(−1) + 2016.1] + 90 = 90.2010 + 90 = 90.2011 ≡ 0 (mod 2011). Bài toán được chứng minh. Ví dụ 13 (Chọn đội tuyển Việt Nam thi toán Quốc tế năm 2012). Cho dãy số ( xn ) gồm vô hạn các số nguyên dương được xác định bởi x1 = 1, x2 = 2011, xn+2 = 4022xn+1 − xn , ∀n ∈ N∗ x2012 + 1 Chứng minh rằng là số chính phương. 2012 Bài toán có thể phát biểu tổng quát như sau. Bài toán mở rộng 1. Cho p là số nguyên dương lẻ lớn hơn 1. Xét dãy số ( xn ) gồm vô hạn các số nguyên dương được xác định bởi x1 = 1, x2 = p, xn+2 = 2pxn+1 − xn , ∀n ∈ N∗ x p +1 + 1 Chứng minh rằng là số chính phương. p+1 Lời giải. Phương trình đặc trưng của dãy số đã cho là q q 2 t − 2pt + 1 = 0 ⇔ t1 = p + p2 − 1, t2 = p − p2 − 1 Vậy số hạng tổng quát của dãy ( xn ) có dạng xn = A.t1n + B.t2n , ∀n = 1, 2, . . . . 286
  10. Hội thảo khoa học, Hưng Yên 25-26/02/2017 Do x1 = 1, x2 = p nên ta có t2 t A.t1 + B.t2 = 1, A.t21 + B.t22 = p ⇔ ( A, B) = ( , 1 ). 2 2 Như vậy ta có t1n−1 + t2n−1 xn = , ∀n = 1, 2, . . . (dot1 t2 = 1). 2 Do đó p p t1 + t2 p p +1 p p 2 2 x p +1 + 1 2 t + t 2 + 2 ( t 2 + t 2) = = 1 = 1 p+1 p+1 2( p + 1) 2( p + 1) Chú ý rằng t1 + t2 = 2p, t1 t2 = 1 nên √ √ q √ p q t1 + t2 = t1 + t2 + 2 t1 t2 = 2p + 2 = 2( p + 1). Nếu đặt Sn = t1n + t2n , ta có: Sn+2 = 2pSn+1 − Sn , ∀n ∈ N∗ . √ √ Mà S1 = 2p ∈ N, S2 = 4p2 − 2 ∈ N nên suy ra Sn ∈ N, ∀n = 1, 2, . . . Đặt t1 = a, t2 = b p p thì a + b = 2( p + 1), ab = 1 và t12 + t22 = a p + b p . Vì p là số nguyên dương lẻ lớn hơn 1 p nên ta có v p −1 p −1 u a + b = ( a + b) ∑ (−1) a b = 2( p + 1) ∑ (−1)i ai b p−i−1 . u p p i i p − i −1 t i =0 i =0 Xét biến đổi sau p −1 ∑ a i b p − i −1 i =0 p −3 2 p −1 p −1 p −1 p −1 = ∑ (−1)i ai b p−i−1 + (−1) 2 a 2 b 2 + ∑ (−1)i ai b p−i−1 i =0 p +1 i= 2 p −3 2 p −1 p −1 = ∑ (−1)i ( ab)i b p−1−2i + ∑ (−1)i ( ab)i b p−1−2i + (−1) 2 i =0 p +1 i= 2 p −3 2 p−1−2i p −1 p−1−2i p −1 = ∑ (−1)i t2 2 + ∑ (−1)i t2 2 + (−1) 2 i =0 p +1 i= 2 p −3 p−1−2i p−1−2i   2 p −1 = ∑ (−1)i t2 2 + t1 2 + (−1) 2 i =0 p −3 2 p −1 = ∑ (−1)i S p − 1 − 2i + (−1) 2 = N ∈ N. i =0 2 287
  11. Hội thảo khoa học, Hưng Yên 25-26/02/2017 p p p Như vậy, ta có t12 + t22 = N 2( p + 1). Ta thu được  p p 2 2 2 t1 + t2 x p +1 + 1 N 2 2( p + 1)) = = = N2. p+1 2( p + 1) 2( p + 1) x p +1 + 1 Tóm lại = N 2 là số chính phương. Bài toán chứng minh xong. p+1 4 Một số bài tập tương tự Bài 1. Tìm số hạng tổng quát của dãy số được xác định bởi u0 = 1, u1 = 1, un+2 = 6un+1 − 9un , ∀n ≥ 0. √ √ 3+ 5 n 3− 5 n Bài 2. Cho dãy số (un ) xác đinh như sau un = ( ) +( ) − 2, ∀n = 1, 2, . . . 2 2 a. Chứng minh rằng un là số tự nhiên ∀n = 1, 2, . . . b. Chứng minh rằng u2011 là một số chính phương. Bài 3. Cho dãy (un ) xác định bởi u1 = 0, u2 = 1, un+2 = un + un+1 + 1. Chứng minh rằng: u p (u p+1 + 1) chia hết cho p với p là một số nguyên tố lớn hơn 5. Tài liệu [1] Phan Huy Khải (2000), Các bài toán về dãy số, NXB Giáo dục. [2] Nguyễn Tài Chung (2006), Bồi dưỡng học sinh giỏi chuyên khảo dãy số, NXB Đại Học Quốc Gia. [3] Các tài liệu khác trên Internet. 288
nguon tai.lieu . vn