Luận văn Toán tử sai phân và ứng dụng vào giải toán sơ cấp

+Q`(n) sinαn, với Pm(n), Q`(n) tướng ứng là các đa thức bậc m, ` của n. Ký hiệu k = max{m, `}. Ta thấy + Nếu α = cos β + i sin β, i2 = −1 không là nghiệm của phương trình đặc trưng thì u∗n = Tk(n) cosαn+ nRk(n) sinαn. 14 + Nếu α = cos β + i sin β, i2 = −1 là nghiệm của phương trình đặc trưng thì u∗n = nTk(n) cosαn+Rk(n) sinαn. Ví dụ 1.3.2. Giải phương trình sai phânu0 = 2, u1 = 5.un+2 = 5un+1 − 6un,∀n ∈ N. Giải. Xét phương trình đặc trưng λ2 − 5λ+ 6 = 0⇔ λ = 2 hoặc λ = 3. Khi đó số hạng tổng quát của dãy có dạng un = c12 n + c23 n. Theo giả thiếtu0 = 2,u1 = 5. ⇔ c1 + c2 = 2,2c1 + 3c2 = 5. ⇔ c1 = 1,c2 = 1. Vậy un = 2 n + 3n. Ví dụ 1.3.3. Giải phương trình un+2 = un+1 − un,∀n ∈ N,∗ u1 = u2 = 1. Giải. Xét phương trình đặt trưng λ2 − λ + 1 = 0 có hai nghiệm phức liên hợp λ1,2 = 1±√3i 2 = cos pi 3 ± i sin pi 3 . Suy ra un = C1 cos npi 3 + C2 sin npi 3 . Theo giả thiết u1 = u2 = 1 ta cóC1 ( 1 2 ) + C2 (√ 3 2 ) = 1 C2 (− 12)+ C2(√32 ) = 1 ⇔ C1 = 0C2 = 2√33 Vậy un = 2 √ 3 3 sin npi 3 . 15 Định nghĩa 1.3.7. [4]. Phương trình sai phân tuyến tính cấp 3 có dạng: aun+3 + bun+2 + cun+1 + duu = fn, a, d 6= 0 hoặc un+3 = pun+2 + qun+1 + kuu + fn, k 6= 0. + Nếu fn = 0 ta có phương trình sai phân tuyến tính cấp 3 thuần nhất. + Nếu fn 6= 0 ta có phương trình sai phân tuyến tính cấp 3 không thuần nhất. + Nếu a, b, c, d hay p, q, k là các hằng số thì ta có phương trình sai phân tuyến tính cấp 3 với hệ số hằng. + Nếu a, b, c, d hay p, q, k là các hàm của n thì ta có phương trình sai phân tuyến tính cấp 3 với hệ số biến thiên. Định nghĩa 1.3.8. [4]. Nghiệm tổng quát của phương trình sai phân tuyến tính cấp 3 không thuần nhất có dạng: un = un + u ∗ n, trong đó un là nghiệm tổng quát của phương trình sai phân tuyến tính cấp 3 thuần nhất và u∗n là nghiệm riêng của phương trình sai phân tuyến tính cấp 3 không thuần nhất. Cách tìm nghiệm tổng quát un của phương trình sai phân tuyến tính cấp 3 thuần nhất: Giải phương trình đặc trưng: aλ3 + bλ2 + cλ+ d = 0. + Nếu phương trình đặc trưng có ba nghiệm phân biệt λ1, λ2, λ3 thì số hạng tổng quát của dãy có dạng: un = c1λ n 1 + c2λ n 2 + c3λ n 3 . + Nếu phương trình đặc trưng có nghiệm bội λ1 = λ2 = λ3 = λ thì số hạng tổng quát của dãy có dạng: un = (c1n 2 + c2n+ c3)λ n. + Nếu phương trình đặc trưng có hai nghiệm phân biệt λ1 và λ2 = λ3 = λ thì số hạng tổng quát của dãy có dạng: un = c1λ n 1 + (c2n+ c3)λ n. 16 + Nếu phương trình đặc trưng có một nghiệm thực λ và hai nghiệm phức thì số hạng tổng quát của dãy có dạng: un = c1λ n + c2 cosnϕ+ c3 sinnϕ. Tìm Nghiệm riêng u∗n của phương trình sai phân tuyến tính cấp 3 không thuần nhất: * Trường hợp 1. Nếu fn = Pm(n) là đa thức bậc m của n,m ∈ N + và λ 6= 1 thì u∗n = Qm(n),m ∈ N. + và λ = 1 là nghiệm bội 1 thì u∗n = nQm(n),m ∈ N. + và λ = 1 là nghiệm bội 2 thì u∗n = n 2Qm(n),m ∈ N. + và λ = 1 là nghiệm bội 3 thì u∗n = n 3Qm(n),m ∈ N. * Trường hợp 2. Nếu fn = vµ n (hàm mũ) + và λ 6= µ thì u∗n = knµn. + và λ = µ là nghiệm đơn thì u∗n = kµ n. + và λ = µ là nghiệm bội s thì u∗n = kn sµn. Ví dụ 1.3.4. Giải phương trình un+2 = 7un+1 − 11un + 5un−1,∀n > 2, u1 = 0, u2 = 1, u3 = 3. Giải. Xét phương trình đặc trưng λ3 − 7λ2 + 11λ− 5 = 0⇔ (λ− 1)2(λ− 5) = 0. Phương trình này có ba nghiệm thực λ1 = λ2 = 1, λ3 = 5. Suy ra un = c1 + c2n+ c3.5 n. Với u1 = 0, u2 = 1, u3 = 3 ta có C1 + C3 = 0 C1 + 2C2 + 25C3 = 1 C1 + 3C2 + 125C3 = 3 ⇔  C1 = − 116 C2 = 3 4 C3 = 1 16 . Vậy un = 1 16 + 3 4 (n− 1) + 1 16 .5n−1 Hay un = 1 16 (5n−1 − 1) + 3 4 (n− 1) + 1 16 . 17 1.4 Phương trình sai phân phi tuyến Định nghĩa 1.4.1. [4]. Một phương trình sai phân không tuyến tính được gọi là phương trình sai phân phi tuyến tính. Ví dụ 1.4.1. Ta có các phương trình sai phân phi tuyến tính sau: un+1 = pun + q run + s ; un+1 = 5un + √ 24u2n + 1, u0 = 0. Định nghĩa 1.4.2. [4]. Tuyến tính hóa là sự chuyển đổi phương trình sai phân dạng phi tuyến tính về dạng tuyến tính. Trong nhiều trường hợp một số phương trình sai phân dạng phi tuyến có thể thực hiện được như vậy và dạng tuyến tính là có thể giải được, nhờ đó làm phong phú thêm ứng dụng của phương trình sai phân. Phương pháp để đưa phương trình sai phân phi tuyến tính thành phương trình sai phân tuyến tính: Giả sử phương trình sai phân un = ϕ(un−1, un−2, ..., un−k) là tuyến tính hóa được với k giá trị bạn đầu u1, u2, ..., uk. Khi đó cần tồn tại các hệ số a1, a2, ..., ak không đồng thời bằng 0 sao cho un = a1un−1 + a2un−2 + ...+ akun−k. Các giá trị uk+1, uk+2, ..., u2k tính trực tiếp qua k giá trị ban đầu u1, u2, ..., uk. Ta có hệ phương trình: uk+1 = a1uk + a2uk−1 + ...+ aku1 uk+2 = a1uk+1a2uk + ...+ aku2 ... uk+1 = a1u2k−1 + a2u2k−2 + ...+ akuk Giải hệ phương trình trên ta tìm được a1, a2, ..., ak. Từ đó ta tìm được un. Sau đó chứng minh tính đúng đắn của biểu thức tuyến tính với mọi n. Ví dụ 1.4.2. Tuyến tính hóa phương trình un = u2n−1 + 2 un−2 , u1 = u2 = 1, n > 3. 18 Giải. Ta tìm a, b sao cho un = aun−1 + bun−2 (1.6) và u3 = 3, u4 = 11. Thay vào phương trình (1.6) ta cóa+ b = 33a+ b = 11 ⇔ a = 4b = −1 Vậy un = 4un−1 − un−2. Ví dụ 1.4.3. Tuyến tính hóa và giải phương trình un+1 = 5un + √ 24u2n + 1, u0 = 0, n ∈ N∗. Giải. Ta tìm a, b sao cho un+1 = aun + bun−1 (1.7) và u0 = 0, u1 = 1, u2 = 10, u3 = 99. Thay vào phương trình (1.7) ta cóa = 1010a+ b = 99 ⇔ a = 10b = −1. Do đó un = 10un−1 − un−2. Xét phương trình đặc trưng λ2−10λ+ 1 = 0⇔ λ1,2 = 5±2 √ 6. Suy ra un = C1(5 + 2 √ 6)n + C2(5− 2 √ 6)n. Theo giả thiết u0 = 0, u1 = 1 ta cóC1 + C2 = 0C1(5 + 2√5) + C2(5− 2√6) = 1 ⇔ C1 = 14√6C2 = − 14√6 . Vậy un = 1 4 √ 6 [(5 + 2 √ 6)n − (5− 2 √ 6)n]. 19 Chương 2 Ứng dụng toán tử sai phân vào giải một số bài toán dành cho học sinh khá, giỏi Toán tử sai phân có nhiều ứng dụng quan trọng, nó không những góp phần giải quyết các bài toán về dãy số mà còn giúp giải một số bài toán khác như phương trình hàm, đa thức, bất đẳng thức. Trong chương này chúng tôi xét một số ứng dụng của toán tử sai phân vào giải một số bài toán sơ cấp như bài toán tìm số hạng tổng quát, bài toán tính tổng, bài toán về bất đẳng thức, bài toán chia hết, phần nguyên, bài toán tổ hợp, bài toán về giới hạn và một số bài toán khác. Nội dung chính của chương này được tham khảo từ các tài liệu [1], [3], [4], [5], [6]. 2.1 Ứng dụng toán tử sai phân vào giải bài toán tìm số hạng tổng quát Để tìm số hạng tổng quát của dãy {un} cho trước, ta đưa dãy đã cho về dạng phương trình sai phân tuyến tính giải được. Giải phương trình sai phân tuyến tính này ta sẽ tìm được số hạng tổng quát cần tìm. Bài toán 2.1.1. Cho dãy {un}: u1 cho trước, un+1 = aun + b với a, b cho trước. Hãy xác định số hạng tổng quát un của dãy số. Giải. Phương pháp 1. 20 + Nếu a = 1 thì dãy số là cấp số cộng với công sai là b nên ta có un = u1 + (n− 1)b. + Nếu a 6= 1, ta gọi {vn} là dãy số có các số hạng thỏa mãn un = vn+c. Thay vào hệ thức truy hồi ta có vn = avn−1 + (a− 1)c+ b. Ta chọn c sao cho (a− 1)c + b = 0 hay c = b/(1− a). Khi đó {vn} là một cấp số nhân với công bội q = a, số hạng đầu v1 = u1 − c. Tức là v1 = u1 − b/(1− a). Do đó số hạng tổng quát vn = ( u1 − b 1− a ) an−1,∀n > 2. Suy ra un = a n−1 ( u1 − b a− 1 ) + b a− 1 . Phương pháp 2. Sử dụng toán tử sai phân và các tính chất + Nếu a = 1 thì uk+1 − uk = b⇒ n−1∑ k=1 (uk+1 − uk) = un − u1 = (n− 1)b. Hay un = u1 + (n− 1)b. + Nếu a 6= 1 thì un+1 = aun + b⇒ un+1 an+1 = un an + b an+1 . Đặt vn = un an ⇒ vn+1 − vn = b an+1 . Suy ra n−1∑ k=1 (vk+1 − vk) = n−1∑ k=1 b ak+1 = b a(a− 1) ( 1− 1 an−1 ) . Vậy un = a n( u1 a ) + n−1∑ k=1 b ak+1 = ( b a(a− 1) ( 1− 1 an−1 ) + u1 a ) an = an−1 ( u1 − b a− 1 ) + b a− 1 . Bài toán 2.1.2. Tìm {un} biết u0 = 1, u1 = −1, un+2 = 6un+1 + 5un, n = 0, 1, .... 21 Giải. Xét phương trình sai phân un+2 − 6un+1 − 5un = 0. Phương trình đặc trưng λ2 − 6λ− 5 = 0, có hai nghiệm phân biệt λ1,1 = 3± √ 14. Suy ra un = C1(3 + √ 14)n + C2(3− √ 14)n. Theo giả thiết u0 = 1, u1 = −1, ta có hệ phương trìnhC1 + C2 = 1C1(3 +√14) + C2(3−√14) = −1 ⇔ C1 = 7−2 √ 14 14 C2 = 7+2 √ 14 14 . Do đó un = (7− 2√14)(3 +√14)n + (7 + 2√14)(3−√14)n 14 . Bài toán 2.1.3. Tìm {un} biết u0 = 1, u1 = 2, un+2 = 5un+1 − 6un + n+ 2. Giải. Phương trình đã cho có nghiệm tổng quát un = un + u ∗ n, Trong đó un là nghiệm tổng quát của phương trình thuần nhất un+2 − 5un+1 + 6un = 0 còn u∗n là nghiệm riêng của phương trình không thuần nhất. Xét phương trình sai phân thuần nhất un+2 − 5un+1 + 6un = 0. Phương trình đặc trưng λ2 − 5λ+ 6 = 0, có hai nghiệm phân biệt λ1 = 2, λ2 = 3. 22 Suy ra un = C12 n + C23 n. Theo giả thiết u0 = 1, u1 = 2, ta có hệ phương trìnhC1 + C2 = 12C1 + 3C2 = 2 ⇔ C1 = 1C2 = 0. Do đó un = 2 n Ta tìm nghiệm riêng u∗n của phương trình không thuần nhấtcó dạng u∗n = an+ b. Thay u∗n = an+ b vào phương trình đã cho ta có a(n+2)+b = 5[a(n+1)+b]−6(an+b)+n+2⇔ (2a−1)n−(3a−2b+2) = 0 ⇔ 2a− 1 = 03a− 2b+ 2 = 0 ⇔ 2 = 1/2b = 7/4. Suy ra u∗n = 1 2 n+ 7 4 . Vậy un = 2 n + 1 2 n+ 7 4 . 2.2 Ứng dụng toán tử sai phân vào giải bài toán tính tổng Trong một số bài toán ta cần tính tổng của một số số hạng đầu tiên. Có nhiều cách khác nhau để giải các bài toán như vậy. Trong mục này, chúng tôi sử dụng toán tử sai phân và các tính chất của nó để giải bài toán tính tổng. Bài toán 2.2.1. Tính tổng S = 13 + 23 + 33 + ...+ n3. Giải. Đặt k3 = uk+1 − uk; k = 1, 2, ..., n, ta có S = un+1 − u1. 23 Ta tìm un từ phương trình sai phân tuyến tính hệ số hằng sau un+1 − un = n3. Phương trình thuần nhất: un+1 − un = o. Ta có phương trình đặc trưng: k − 1 = 0⇔ k = 1. Nghiệm tổng quát của phương trình thuần nhất là: un = C. Ta tìm nghiệm của phương trình không thuần nhất dưới dạng ûn = n(An 3 +Bn2 + Cn+D) = An4 +Bn3 + Cn2 +Dn. Tính ûn+1, thay ûn, ûn+1 vào phương trình không thuần nhất so sánh các hệ số của n, ta có hệ phương trình: 4A = 1 6A+ 3B = 0 4A+ 3B + 2C = 0 A+B + C +D = 0 ⇔  A = 1/4 B = −1/2 C = 1/4 D = 0. Suy ra ûn = 1 4 n4 − 1 2 n3 + 1 4 n2;un = un + ûn = C + 1 4 n4 − 1 2 n3 + 1 4 n2. Do đó S = un+1 − u1 = 1 4 (n+ 1)4 − 1 2 (n+ 1)3 + 1 4 (n+ 1)2 − 1 4 + 1 2 − 1 4 = n2(n+ 1)2 4 . Bài toán 2.2.2. Tính tổng S = 1.21 + 2.22 + 3.22 + ...+ n.22. Giải. Đặt k.2k = uk+1 − uk.k = 1, 2, 3, ..., n, ta có S = un+1 − u1. Ta tìm un từ phương trình sai phân tuyến tính hệ số hằng sau: un+1 − un = n.2n. 24 Phương trình thuần nhất: un+1 − un = 0. Phương trình đặc trưng: k − 1 = 0⇔ k = 1. Nghiệm tổng quát của phương trình thuần nhất: un = C. Tìm một nghiệm riêng của phương trình không thuần nhất dưới dạng: ûn = 2n(An+B). Tính ûn+1, thay ûn và ûn+1 vào phương trình không thuần nhất, so sánh các hệ số của n, ta có hệ phương trình:A = 12A+B = 0 ⇔ A = 1B = −2. (2.1) Suy ra ûn = (n− 2)2n;un = un + ûn = C + (n− 2)2n. Do đó: S = un+1 − u1 = (2n− 2)2n + 2. Bài toán 2.2.3. Tính tổng S = 1!1 + 2!2 + 3!3 + ...+ n!n. Giải. Đặt k!k = uk+1 − uk với k = 1, 2, 3, ..., n, ta có S = un+1 − u1. Ta tìm un từ phương trình sai phân tuyến tính hệ số hằng sau: un+1 − un = n!n. Phương trình thuần nhất: un+1 − un = 0. Phương trình đặc trưng: k − 1 = 0⇔ k = 1. Nghiệm tổng quát của phương trình thuần nhất: un = C. Tìm một nghiệm riêng của phương trình không thuần nhất dưới dạng: ûn = n!(An+B). Tính ûn+1, thay ûn và ûn+1 vào phương trình không thuần nhất, so sánh các hệ số của n, ta có hệ phương trình: A = 0 A+B = 1 A = 0 ⇔ A = 0B = 1 (2.2) 25 Do đó ûn = n!;un = un + ûn = C + n!. Vậy S = un+1 − u1 = (n+ 1)!− 1. Bài toán 2.2.4. (Đề thi chọn đội tuyển IMO, Hồng Kông năm 1998) Cho dãy số {un} xác định bởi un+2 = un+1 − un. Giả sử tổng 1997 số hạng đầu tiên của dãy là 1879, tổng của 1897 số hạng đầu tiên là 1997. Hỏi tổng của 2000 số hạng đầu tiên là bao nhiêu. Giải. Xét phương trình đặc trưng λ2 − λ+ 1 = 0 có nghiệm phức λ = cos pi 3 + i sin pi 3 . Nghiệm un = c1 cos npi 3 + c2 sin npi 3 , với c1, c2 là các hằng số. Suy ra Sn = c1 n∑ k=1 cos npi 3 + c2 n∑ k=1 sin npi 3 . Sử dụng tính chất: sin(pi + α) = − sin(α), cos(pi + α) = − cos(α), ta có Sn+6 = Sn. Do vậy: S1997 = S5 = u1 + u2 + ...u5 = −c1 = 1897. S1897 = S1 = u1 = 1 2 (c1 + √ 3c2) = 1997⇒ c2 = 5873√ 3 . Vậy S2000 = S2 = u1 + u2 = √ 3c2 = 5873. Bài toán 2.2.5. Cho dãy {un} xác định bởiu0 = 13 ;u1 = 23 ,un+2 − 3un+1 − 2un = 0. Tính tổng S = [u0] + [u1] + ...+ [u2007]. 26 Giải. Xét phương trình đặc trưng λ2 − 3λ+ 2 = 0 có hai nghiệm λ = 1, λ = 2. Nghiệm un = c1 + c22 n với c1, c2 là các hằng số. Với u0 = 1 3 ;u1 = 2 3 ta có un = 2n 3 . Nếu a, b > 0, a, b 6∈ Z, a+ b ∈ Z thì [a] + [b] = a+ b− 1. Mặt khác 2 n 3 + 2n+1 3 = 2 n. Suy ra S = ([20 3 ] + [21 3 ]) + ([22 3 ] + [23 3 ]) + ... ([22006 3 ] + [22007 3 ] ) S = ( 20 3 + 21 3 + ...+ 22007 3 )− 1004 = 2 2008 − 1 3 − 1004. Bài toán 2.2.6. Cho dãy {un} xác định bởiu1 = 1;u2 = 2, n > 1un+2 − un+1 + un = 0, n > 1. Đặt Sn = u1 + u2 + ...+ un. Biết u2 − u1 = S22003 − S2003 + 1. Tính S2003. Giải. Xét phương trình đặc trưng λ2 − λ+ 1 = 0 có nghiệm phức λ = cos pi 3 + i sin pi 3 . Từ đó ta tìm nghiệm un = c1 cos npi 3 + c2 sin npi 3 với c1, c2 là các hằng số. Mặt khác ta có: cos pi 3 + cos 2pi 3 + ...+ cos 6pi 3 = 0, sin pi 3 + sin 2pi 3 + ...+ sin 6pi 3 = 0. Suy ra Sn+6 = Sn. Do đó S2003 = S5 = −c1. Với c21 − c1 + 1 = u2 − u1 = 1⇒ c1 = 1⇒ S2003 = −1. 2.3 Ứng dụng toán tử sai phân vào một số bài toán về bất đẳng thức Bất đẳng thức là một bài toán khó đối với người học. Trong một số trường hợp để giải được bài toán dạng này, chúng ta phải đưa nó về bài toán giải phương trình sai phân, xác định số hạng tổng quát, áp dụng các tính chất của dãy số để giải. 27 Bài toán 2.3.1. Cho dãy {un} xác định bởiu1 = 1;u2 = 2, n > 1un+2 − 3un+1 + un = 0, n > 1. Chứng minh rằng un+2 + un > 2 + u 2 n+1 un . Giải. Xét phương trình đặc trưng λ2 − 3λ+ 1 = 0 có hai nghiệm λ1,2 = 3±√5 2 . Từ đó ta tìm nghiệm un = c1 (3 +√5 2 )n + c2 (3−√5 2 )n với c1, c2 là các hằng số. Theo giả thiết u1 = 1;u2 = 2 từ đó ta tìm được un = 1√ 5 [ c1 (1 +√5 2 )2n−1 + c2 (−1 +√5 2 )2n−1] . Suy ra un+2un = u 2 n+1 hay un+2 = u2n+1 un . Vậy un+2 + un = u2n+1 un + ( 1 un + un ) > 2 + u 2 n+1 un ,∀n > 1. Bài toán 2.3.2. Cho dãy {un} xác định bởi: u1 = √ e √ 3 u1 = √ e un+1un−1 = u √ 3 n ,∀n > 2. (2.3) Chứng minh 1e 6 un 6 e với mọi n > 1. Giải. Ta thấy un > 0 với mọi n > 1. Suy ra lnun+1 + lnun−1 = √ 3lnun. Hay an+1 − √ 3an + an−1 = 0 với an = lnun, a1 = √ 3 2 , a2 = 1 2 . Xét phương trình đặc trưng λ2 −√3λ+ 1 = 0 có nghiệm phức λ = cos pi 6 + isin pi 6 . Do đó an = c1cos npi 6 + c2sin npi 6 . 28 Với a1 = √ 3 2 , a2 = 1 2 ta tìm được c1 = 1, c2 = 0. Suy ra an = cos npi 6 . Từ đó ta tìm được un = e cos npi6 . Vì −1 6 cos npi6 6 1 nên 1e 6 un 6 e với mọi n > 1. 2.4 Ứng dụng toán tử sai phân vào một số bài toán chia hết, phần nguyên Việc giải một số bài toán chia hết, phần nguyên có thể dẫn tới giải phương trình sai phân. Do đó ta có thể sử dụng toán tử sai phân và các tính chất của nó để giải các bài toán đó. Bài toán 2.4.1. Cho dãy số nguyên dương {un} xác định bởi u0 = 1, u1 = 9, un = 10un−1 − un−2. a)Hỏi 3u2k − 1 có chia hết cho 2 không? b) Hỏi 5uk − uk−1 có chia hết cho 4 không? Giải. Xét phương trình đặc trưng λ2 − 10λ+ 1 = 0 có hai nghiệm λ1,2 = 5± 2 √ 6. Nghiệm un = c1(5 + 2 √ 6)n + c2(5− 2 √ 6)n, với c1, c2 là các hằng số. Từ các giá trị ban đầu ta tìm được un = ( 1 2 + 1√ 6 )(5 + 2 √ 6)n + ( 1 2 − 1√ 6 )(5− 2 √ 6)n Theo giả thiết suy ra un+2 và un cùng tính chẵn lẻ. Vì u0 = 1, u1 = 9 là là các số lẻ nên un lẻ với mọi số nguyên dương n. Mặt khác ta có: u2k = ( 5 12 + 1√ 6 )(5 + 2 √ 6)2k + ( 5 12 − 1√ 6 )(5− 2 √ 6)2k + 1 6 . Suy ra 3u2k − 1 chia hết cho 2. Theo giả thiết ta có un+1 = 10un − un−1 = 10un − 10un−2 + un−3 ⇒ un+1 ≡ un−3 (mod 4). 29 Hơn nữa các giá trị ban đầu u0 = 1, u1 = 9, u2 = 89, u3 = 881 cùng số dư là 1 khi chia cho 4. Suy ra un ≡ 1(mod 4). Vậy 5uk − uk−1 chia hết cho 4. Bài toán 2.4.2. Cho hai dãy số nguyên {un}, {vn} được xác định bởi: 3un+1 = un + vn, 3vn+1 = 2vn − 7vn, v1 = 2, v1 = 1. Hỏi số hạng thứ 20072007 của hai dãy trên có chia hết cho 5 hay không. Giải. Ta có: 9un+2 = 3un+1+2vn−7un = 3un+1+2(3un+1−un)−7un. Suy ra un+2 = un+1 − un. Tương tự, ta có: vn+2 = vn+1 − vn. Xét phương trình đặc trưng λ2 = λ+ 1 = 0 có nghiệm phức λ = cos npi 3 + isin npi 3 . Suy ra un = acos npi 3 + bsin npi 3 , vn = ccos npi 3 + dsin npi 3 . Theo giả thiết u1 = 2, v1 = 1 ⇒ u2 = 1, v2 = −4. Thay các giá trị này vào un, vn ta có: a = 1, b = √ 3, c = 5, d = −√3. Vậy un = cos npi 3 + √ 3sin npi 3 , vn = 5cos npi 3 − √ 3sin npi 3 . Vì cos (α + pi) = −cos α, sin (α + pi) = −sin α nên ta có: un = −un+3 = un+6, vn = −vn+3 = vn+6. Vì 2007 ≡ 3 (mod 6), 3n ≡ 3 (mod 6) nên 20072007 ≡ 3 (mod 6). Mặt khác u3 = −1, v3 = −5. Vậy số hạng thứ 20072007 của dãy {un} không chia hết 5, còn số hạng thứ 20072007 của dãy {vn} chia hết 5. Bài toán 2.4.3. Cho dãy số nguyên dương {un} thỏa mãn: u0 = 20 u1 = 100 un+2 = 4un+1 + 5un + 20. Tìm số nguyên dương h nhỏ nhất để an+h− an chia hết cho 1998,∀n > 0. 30 Giải. Theo đầu bài ta có phương trình đặc trưng λ2 − 4λ − 5 = 0 có nghiệm λ1 = −1, λ2 = −5. Khi đó nghiệm tổng quá có dạng un = c15 n + c2(−1)n. Theo giả thiết u0 = 20, u1 = 100 ta tìm được nghiệm riêng x ∗ n = 5 2 . Vậy nghiệm tổng quát có dạng: un = 1 6 5n+2 + (−1)n10 6 − 5 2 . Suy ra un = 5un−1 + 20 nếu n chẵn,5un−1 nếu n lẻ. Điều kiện cần. Ta có un+h ≡ un (mod 1998), với mọi n > 0. Suy ra uh ≡ u0 ≡ 20(mod 1998), uh+1 ≡ u1 ≡ 100 (mod 1998). Hay 5uh−1 = uh+1 − 4uh − 20 ≡ 0 (mod 1998). Do 5 và 1998 nguyen tố cùng nhau nên uh−1 ≡ 0 (mod 1998). Mặt khác nếu h lẻ thì uh = 5uh−1 ≡ 0 (mod 1998) nên u1 ≡ 0 (mod 1998). Điều này vô lý vì u1 = 100. Suy ra h chẵn và uh−1 ≡ 0 (mod 1998). Điều kiện đủ. Với h chẵn và uh−1 ≡ 0 (mod 1998), ta chứng minh un+h ≡ xn (mod 1998). Thậy vậy với h chẵn ta có: uh = 5un−1 + 20 ≡ 0 (mod 1998) = x0; uh+1 = 4uh + 5uh−1 + 20 ≡ 100 (mod 1998) = x1. Kết hợp với un+2 = 4un+1 + 5un + 20 ⇒ un+h ≡ un( mod1998), với mọi n > 0. Như vậy h là số chẵn nhỏ nhất thỏa mãn uh−1 ≡ 0 (mod 1998). Ta có 5h ≡ 1 (mod 4),∀h, 554 ≡ 1 (mod 34), 536 ≡ (mod 37). Vậy 5108 ≡ 1 (mod 1998). Suy ra h = 108. 31 Bài toán 2.4.4. Cho dãy {un} xác định bởi: u1 = 1 u2 = 2 u3 = 40 un = 10u2n−1un−3−24un−1u2n−2 un−2un−3 , n = 4, 5, ... Xác định n nhỏ nhất để un ...2048. Giải. Xét un un−1 = 10u2n−1un−3 − 24u2n−2 un−2un−3 = 10un−1 un−2 − 24un−2 un−3 . Đặt vn = un un−1 ta có v2 = 2 v3 = 20 vn = 10vn−1 − 24vn−2, n = 4, 5, ... Xét dãy {vn} ta có phương trình đặt trưng λ2 − 10λ + 24 = 0 có hai nghiêm λ1 = 4, λ2 = 6. Suy ra vn = c14 n+c26 n. Với v2 = 2, v3 = 20 ta tìm được c1 = −14 , c2 = 16 . Suy ra vn = 6 n−1 − 4n−1. Do đó un = vnvn−1...v2 = (6n−1 − 4n−1)(6n−2 − 4n−2)...(6− 4) = 2n−12n−2...2(3n−1 − 2n−1)(3n−2 − 2n−2)...(3− 2) = 2n(n−1)/2(3n−1 − 2n−1)(3n−2 − 2n−2)...(3− 2). Vì (3n−1 − 2n−1)(3n−2 − 2n−2)...(3− 2) là số lẻ nên để un...2048 thì 2n(n−1)/2...2048. Hay 2n(n−1)/2...211. Do đó (n− 1)n/2 > 11. Suy ra n > 6. Vậy n = 6 là giá trị cần tìm. 32 Bài toán 2.4.5. Cho dãy số nguyên {un} xác định bởi: u0 = 1 u1 = −1 un = 6un−1 + 5an−2, với mọi n > 2. Chứng minh rằng u2012 − 2010 chia hết cho 2011. Giải. Xét dãy số nguyên {vn} xác định bởi: v0 = 1 v1 = −1 vn = 6uv−1 + 2016vn−2, với mọi n > 2. Dễ thấy với mọi n > 0 ta có un ≡ vn( mod 2011). Xét phương trình đặc trưng của dãy {vn}: λ2 − 6λ− 2016 = 0 có hai nghiệm thực λ1 = −42, λ2 = 48. Suy ra số hạng tổng quát của dãy {vn} có dạng: vn = C1(−42n) + C248n. Từ các điều kiện ban đầu của dãy {vn} ta có hệC1 + C2 = 142C1 − 48C2 = 1 ⇔ C1 = 49/90C2 = 41/90. Suy ra vn = 49(−42)n + 41.48n 90 ,∀n > 0. Vì 2011 là số nguyên tố nên theo định lý Fermat nhỏ, ta có: (−42)2010 ≡ 482010 ≡ 1( mod 2011). Do đó 90v2012 ≡ 49(−42)2012+42.482012 ≡ 49(−42)2+41.482 ≡ 90v2( mod 2011). Suy ra v2012 ≡ v2( mod 2011) vì ((90, 2011) = 1). Mà v2 = 6v1 + 2016b0 = 2010 nên b2012 ≡ 2010( mod 2011). Vì thế u2012 ≡ 2010( mod 2011). Ta có điều cần chứng minh. 33 Bài toán 2.4.6. Cho dãy {un} xác định bởi: u0 = 0 u1 = 1 un+1 = 2un − un−1 + 1, n > 1. Chứng minh rằng 4un+2un + 1 là số chính phương. Giải. Phương trình đặc trưng λ2−2λ+1 = 0 có nghiệm kép λ1 = λ2 = 1. Ta tìm g(n) = an2 sao cho g(n + 1) − 2g(n) + g(n − 1) = 1 với mọi n ∈ N∗. Giải ra ta có g(n) = n/2 hay u∗n = n 2/2 là một nghiệm của phương trình un+1 = 2un − un−1 + 1. Suy ra phương trình trên có nghiệm tổng quát un = C1 + nC2 + n 2/2. Với u0 = 0 ta tìm được C1 = 0. Với a1 = 1 nên C2 = 1/2. Vậy un = 1 2 n+ n2 2 = n(n+ 1) 2 . Do đó 4un+2un + 1 = 4 (n+ 2)(n+ 3) 2 n(n+ 1) 2 + 1 = n(n+ 1)(n+ 2)(n+ 3)+ = (n2 + 3n)(n2 + 3n+ 2) + 1) = (n2 + 3n+ 1)2. Ta có điều cần chứng minh. 2.5 Ứng dụng toán tử sai phân vào một số bài tổ hợp Một số bài toán tổ hợp để giải được chúng ta phải đưa nó về giải phương trình sai phân tuyến tính xác định số hạng tổng quát và các tính chất của nó. Trong mục này chúng tôi sẽ trình bày ứng dụng của toán tử sai phân vào một số bài toán tổ hợp. 34 Bài toán 2.5.1. Cho dãy số nguyên {un} xác định bởi: u0 = 1 u1 = 45 un+2 = 45un+1 − 7un = 0. Tìm số các ước dương của biểu thức: u2n+1 − unun+2 Giải. Xét phương trình đặc trưng Xét phương trình đặc trưng λ2 − 45λ+ 7 = 0 có hai nghiệm λ1,2 = 45±√1997 2 . Do đó nghiệm tổng quát un = c1( 45 + √ 1997 2 )n + c2( 45−√1997 2 )n. Với n = 0 ta có u0 = 1 = c1 + c2. Với n = 1 ta có u1 = 45 = c1 45+ √ 1997 2 + c2 45−√1997 2 . Suy ra c1 = 45 + √ 1997 2 √ 1997 , c2 = 45−√1997 2 √ 1997 . Từ đó ta tìm được un = 1√ 1997 [(45 +√1997 2 )n+1 + c2 (45−√1997 2 )n+1] . Suy ra u2n+1 − unun+2 = 7n+1. Vì 7 là số nguyên tố nên 7n+1 có các ước là 1, 7, 72, ..., 7n+1. Suy ra 7n+1 có n+ 2 ước. Vậy số các ước dương của u2n+1 − unun+2 là n+ 2. Bài toán 2.5.2. (Học sinh giỏi Vũng Tàu 2009-2010) Cho số nguyên dương n. GọiMn là tập các số tự nhiên (viết trong hệ thập phân)có n chữ số, các chữ số lớn hơn 1 và không có hai chữ số cùng nhỏ hơn 7 đứng liền nhau. Tính số phần tử của Mn. Giải. Kí hiệu un = |Mn|. Gọi Xn, Yn lần lượt là tập các số tự nhiên theo thứ tự: Có chữ số tận cùng nhỏ hơn 7 và các số có tận cùng lớn hơn 6. Ta có: Mn = Xn ∪ Yn, Xn ∩ Yn 6= φ. 35 Lấy một phần tử của Mn+1 bỏ đi phần tử cuối cùng ta được một phần tử của Mn. Ngược lại, xét một phần tử x của Mn. + Nếu x có tận cùng nhỏ hơn 7 thì có một cách thêm chữ số 0 vào vị trí đầu ta có một phần tử của Xn+1 và có đúng 3 cách thêm vào chữ số cuối để tạo ra một phần tử của Yn+1. + Nếu có tận cùng lớn hơn 6 thì có 5 cách thêm chữ số 0 vào vị trí đầu ta có một phần tử của Xn+1 và có 3 cách thêm vào chữ số cuối để tạo ra một phần tử của Yn+1. Vậy |Xn+1| = |Xn|+ 5|Yn||Yn+1| = 3|Xn|+ 3|Yn|. Suy ra |Mn+1| = 4(|Xn|+ |Yn|) + 4|Yn| = 4(|Xn|+ |Yn|) + 12|Xn−1|+ |Yn−1|. Do đó un+1 = 4un + 12un−1, n > 2. Từ đó ta tìm được un = 1 2 ( 15.6n−1 + (−2)n−1 ) . Vậy |Mn| = 1 2 ( 15.6n−1 + (−2)n−1 ) . 2.6 Ứng dụng toán tử sai phân vào một số bài toán về giới hạn Xét bài toán tổng quát: Cho dãy {un} thỏa mãn điều kiện f(un+k, un+k−1, ..., un) = 0. Tìm limn→∞ un. Để giải bài toán trên, trước hết ta giải phương trình f(un+k, un+k−1, ..., un) = 0. Từ đó ta tìm được số hạng tổng quát un. Sau đó tính limn→∞ un. 36 Bài toán 2.6.1. Cho dãy (un) xác định bởi un+2 − 2(n+2) 2 (n+1)(n+3)un+1 + (n+1)(n+2) n(n+3) un = 2(n+2) n+3 ,∀n > 2, u1 = 0, u2 = −3 (2.4) Tìm limunn2 . Giải. Trước hết ta tìm số hạng tổng quát. Xét un+2− 2(n+ 2) 2 (n+ 1)(n+ 3) un+1+ (n+ 1)(n+ 2) n(n+ 3) un = 2(n+ 2) n+ 3 ,∀n > 2, (2.5) với điều kiện ban đầu u1 = 0 và u2 = −3. Nhân cả hai vế của (2.5) với n+3n+2 ta được: n+ 3 n+ 2 un+2 − 2(n+ 2) n+ 1 un+1 + n+ 1 n un = 2,∀n > 2. (2.6) Đặt vn = n+1 n un ta có phương trình vn+2 − 2vn+1 + vn = 2∀n > 2 (2.7) và v1 = 0, v2 = −9/2. Xét phương trình đặc trưng λ2 − 2λ + 1 = 0 có nghiệm kép λ = 1. từ đó, ta tìm được vn = 13 12 − 15 12 n+ n2. Suy ra: un = n n+ 1 vn = n n+ 1 (13 12 − 15 12 n+ n2 ) = 13n 2(n+ 1) − 15n 2 2(n+ 1) + n3 n+ 1 . Vậy limunn2 = 1. Bài toán 2.6.2. D