Xem mẫu
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
PHƯƠNG PHÁP HÀM SINH XÁC ĐỊNH DÃY SỐ
Lương Thị Hằng
THPT Chuyên Hưng Yên
1 Cơ sở lý thuyết
Phương pháp hàm sinh là một phương pháp hiện đại, sử dụng kiến thức về chuỗi, chuỗi
hàm (Công thức Taylor), chuyển các bài toán về dãy số thành những bài toán về hàm số. Đây
là phương pháp mạnh để giải các bài toán về dãy số mà đôi khi ta hoàn toàn bó tay với các
phương pháp khác.
Ý tưởng của phương pháp hàm sinh đơn giản như sau: Giả sử ta cần tìm công thức tổng
∞
quát của dãy số { an } nào đó. Từ công thức truy hồi ta tìm được hàm sinh f ( x ) = ∑ an x n
n =0
của dãy số. Và từ đó, hệ số ai của xi trong khai triển của f ( x ) thành chuỗi lũy thừa chính là
số hạng thứ i của dãy { an }. Hay nói cách khác, ta tìm f ( x ) rồi lấy đạo hàm cấp n của nó tại
0 là tìm được an .
Các loại hàm sinh gồm hàm sinh thường, hàm sinh mũ, hàm sinh Dirichlet. . . . Trong bài này
ta chỉ đề cập đến một loại hàm sinh thường dùng: Hàm sinh thường.
1.1 Định nghĩa
Cho dãy số a0 ; a1 ; a2 ; . . . an ; . . . . Chuỗi lũy thừa hình thức
∞
f ( x ) = a0 + a1 x + a2 x 2 + · · · = ∑ an x n (1.1)
n =0
được gọi là hàm sinh thường của dãy { an }.
Kí hiệu tương ứng giữa một dãy số và hàm sinh như sau:
{ an } ←→ f ( x ) = a0 + a1 x + a2 x2 + . . .
1
Chẳng hạn như {1, 1, 1, . . . } ←→ 1 + x + x2 + · · · = .
1−x
Khai triển Taylor
∞
f ( n ) (0) n
f (x) = ∑ n!
x (1.2)
n =0
131
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
và công thức khai triển Newton mở rộng
∞
x2 xn
(1 + x ) =α
∑ Cαn xn = 1 + αx + α(α − 1) 2! + · · · + α(α − 1) . . . (α − n + 1) n! + . . . (1.3)
n =0
là những cơ sở quan trọng để chúng ta tìm công thức tường minh cho hàm sinh của hàng
loạt các dãy số.
1.2 Các phép toán
∞ ∞
Cho f ( x ) = ∑ an x n và g( x ) = ∑ bn x n là hàm sinh tương ứng của các dãy { an } và {bn }.
n =0 n =0
Khi đó ta định nghĩa các phép toán như sau:
a) Phép cộng
∞ ∞ ∞
f ( x ) ± g( x ) = ∑ an x n ± ∑ bn x n = ∑ ( a n ± bn ) x n (1.4)
n =0 n =0 n =0
Ví dụ 1.
1
{1, 1, 1, . . . } ←→
1 1 2
1−x
⇒ {2, 0, 2, 0, . . . } ←→ + = (1.5)
1 1−x 1+x 1 − x2
{1, −1, 1, −1, . . . } ←→
1+x
∞ ∞
b) Phép nhân với một số k f ( x ) = k ( ∑ an x n ) = ∑ (kan ) x n
n =0 n =0
1 2
Ví dụ 2. {1, 0, 1, 0, . . . } ←→ 2
, nhân với 2 ta được {2, 0, 2, 0, . . . } ←→
1−x 1 − x2
c) Tích
∞ ∞ ∞
f ( x ).g( x ) = ( ∑ an x n ).( ∑ bn x n ) = ∑ cn x n (1.6)
n =0 n =0 n =0
n
với cn = ∑ ai bn−i .
i =0
∞
Ví dụ 3. Giả sử { an } ←→ f ( x ) = ∑ an x n = a0 + a1 x + a2 x2 + . . . .
n =0
1 f (x)
Ta biết = 1 + x + x2 + .., do đó = a0 + ( a0 + a1 ) x + ( a0 + a1 + a2 ) x 2 + . . .
1−x 1−x
f (x) n
suy ra ←→ { ∑ ai }
1−x i =0
∞ ∞
d) Nghịch đảo Ta nói f ( x ) = ∑ an x n có nghịch đảo là g( x ) = ∑ bn x n nếu f(x).g(x)=1.
n =0 n =0
a0 .b0 = 1 1 n
=⇒ n suy ra bn = − . ∑ ai .bn−i
∑ ai .bn−i = 0, n ≥ 1 a 0 i =1
i =0
e) Dịch chuyển sang phải: Nếu { a0 ; a1 ; a2 ; . . . } ←→ f ( x ) thì
132
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
{0; 0; . . . 0; a0 ; a1 ; a2 ; . . . } ←→ x k . f ( x )
| {z }
k số 0
1
Ví dụ 4. {1, 1, 1, . . . } ←→ thì
1−x
xk
{0; 0; . . . 0; 1; 1; 1; . . . } ←→
| {z } 1−x
k số 0
∞
f) Đạo hàm: Nếu { a0 ; a1 ; a2 ; . . . } ←→ f ( x ) = ∑ an x n thì
n =0
∞
{ a1 ; 2a2 ; 3a3 ; . . . } ←→ f 0 (x) = ∑ nan x n −1
n =1
Đạo hàm cấp n>1 được xác định bởi f (n+1) = ( f (n) )0 .
1
Ví dụ 5. {1, 1, 1, . . . } ←→ f ( x ) = 1 + x + x2 + x3 + · · · = .
1−x
Lấy đạo hàm ta được
∞
1
2
= 1 + 2x + 3x + · · · = ∑ (n + 1) x n
2
(1 − x ) n =0
là hàm sinh của dãy {1, 2, 3, . . . }.
Một hệ quả tất yếu của đạo hàm là: Nếu { an } ←→ f ( x ) thì {nan } ←→ x. f 0 ( x ).
Ví dụ 6. Tìm hàm sinh cho dãy {0, 1, 4, 9, . . . }.
1
Ta xuất phát từ {1, 1, 1, . . . } ←→
1−x
1
Lấy đạo hàm ta được {1, 2, 3, . . . } ←→
1 − x2
x
Dịch chuyển sang phải 1 vị trí, ta được {0, 1, 2, 3, . . . } ←→ .
1 − x2
1+x
Lấy đạo hàm, ta được {1, 4, 9, . . . } ←→
(1 − x )3
x (1 + x )
Dịch chuyển sang phải 1 vị trí, ta được {0, 1, 4, 9, . . . } ←→ .
(1 − x )3
x (1 + x )
Vậy hàm sinh của dãy là f ( x ) = .
(1 − x )3
1.3 Một số kết quả quan trọng
f ( x ) − a 0 − a 1 x − · · · − a k −1 x k −1
Định lý 1. Nếu { an } ←→ f ( x ) thì với k > 0, { an+k } ←→ .
xk
Định lý 2. Dãy số { an } được gọi là dãy xác định kiểu tuyến tính nếu dãy có dạng
a0 = α0 ; . . . ak−1 = αk−1 ; ak+n = γ1 ak+n−1 + γ2 ak+n−2 · · · + γk an , n ≥ 0
133
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
p( x )
. Khi đó, hàm sinh thường f ( x ) của dãy { an } là một hàm hữu tỉ ( f ( x ) = với p(x) là đa
q( x )
thức có bậc nhỏ hơn q(x)) khi và chỉ khi { an } là dãy xác định kiểu tuyến tính.
Định lý 3. Nếu dãy số { an } là dãy xác định kiểu tuyến tính và ak+n = γ1 ak+n−1 +
γ2 ak+n−2 · · · + γk an , n ≥ 0. Gọi r1 , r2 , . . . , rt là các nghiệm bội tương ứng s1 , s2 , . . . , st
của phương trình − x k + γ1 x k−1 + γ2 x k−2 + · · · + γk = 0. Khi đó, tồn tại các đa thức
p1 (n), p2 (n), . . . , pt (n) thỏa mãn 0 ≤ deg pi (n) ≤ si − 1, i = 1, 2, . . . , t và an = p1 (n).r1n +
p2 (n).r2n + · · · + pt (n).rtn .
1.4 Một số khai triển thường gặp
1 ∞
1 + x + x2 + x3 + · · · = ∑ x n
1−x n =0
1 ∞
1 + ax + a2 x 2 + a3 x 3 + · · · = ∑ an x n
1 − ax n =0
1 ∞
1 − x + x2 − x3 + · · · = ∑ (−1)n x n
1+x n =0
1 ∞
1 + x k + x2k + x3k + · · · = ∑ x nk
1 − xk n =0
1 ∞
1 − x k + x2k − x3k + · · · = ∑ (−1)n x nk
1 − xk n =0
1 ∞
1 + 2x + 3x2 + · · · = ∑ ( n + 1) x n
(1 − x ) 2
n =0 .
1 ∞
2
1 + 2ax + 3a2 x2 + · · · = ∑ (n + 1) an x n
(1 − ax ) n =0
n
(1 + x ) n 1 + Cn1 x + Cn2 x2 + · · · + Cnn x n = ∑ Cnk x k
k =0
x2 xn ∞
(1 + x ) α 1 + αx + α(α − 1) + · · · + α(α − 1) . . . (α − n + 1) + · · · = ∑ Cαn x n
2! n! n =0
1 x 2 x k ∞
1 + nx + n(n + 1) + · · · + n(n + 1) . . . (n + k − 1) + · · · = ∑ Cnk +k−1 x k
(1 − x ) n 2! k! k =0
x x 2 x 3 ∞ xn
ex 1+ + + +··· = ∑
1! 2! 3! n=0 n!
2 Ứng dụng hàm sinh giải các bài toán dãy số
(
a0 = 0
Ví dụ 7. Cho dãy số xác định như sau . Tìm an .
an+1 = 2an + 1, n ≥ 1
Lời giải. Giả sử { an } ←→ f ( x ), ta suy ra {0; 2a0 + 1; 2a1 + 1; . . . } ←→ f ( x ).
Ta xuất phát từ
134
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
1 x
{1; 1; 1; . . . } ←→ ⇒ {0; 1; 1; 1; . . . } ←→ . (1).
1−x 1−x
và
{2a0 ; 2a1 ; 2a2 ; . . . } ←→ 2 f ( x ) ⇒ {0; 2a0 ; 2a1 ; 2a2 ; . . . } ←→ 2x f ( x ). (2).
x
Cộng (1) và (2) suy ra {1; 2a0 + 1; 2a1 + 1; 2a2 + 1; . . . } ←→ 2x f ( x ) + .
1−x
x x
Do đó, f ( x ) = 2x f ( x ) + ⇒ f (x) = .
1−x (1 − x )(1 − 2x )
x
Như vậy hàm sinh của dãy là f ( x ) = .
(1 − x )(1 − 2x )
Bây giờ ta khai triển f ( x ) thành chuỗi lũy thừa
x 2 1
f (x) = = x( − )
(1 − x )(1 − 2x ) 1 − 2x 1 − x
∞ ∞ ∞
⇒ f ( x ) = x (2 ∑ 2n x n − ∑ x n ) = ∑ (2n +1 − 1 ) x n +1 .
n =0 n =0 n =0
Vậy số hạng tổng quát của dãy là an = 2n − 1.
(
a1 = 1
Ví dụ 8. Tìm an biết .
a n = a n −1 + a n −2 + · · · + a 1 , n ≥ 2
Lời giải. Gọi f ( x ) là hàm sinh của dãy cần tìm.
f ( x ) = a1 x + a2 x 2 + · · · + a n x n + . . .
= a 1 x + a 1 x 2 + ( a 1 + a 2 ) x 3 + ( a 1 + a 2 + a 3 ) x 4 · · · + ( a 1 + a 2 + · · · + a n −1 ) x n + . . .
= a1 ( x + x 2 + · · · + x n + . . . ) + a2 ( x 3 + x 4 + · · · + x n +
. . . ) + a3 ( x 4 + x 5 + · · · + x n + . . . ) + . . .
= xa1 + xa1 ( x + x2 + . . . ) + x2 a2 ( x + x2 + . . . ) + . . .
= x + ( x + x2 + . . . )( a1 x + a2 x2 + . . . )
1 x
= x+( − 1). f ( x ) = x + ( ). f ( x )
1−x 1−x
x (1 − x )
suy ra f ( x ) =
1 − 2x
Khai triển f ( x ), ta được:
∞ ∞ ∞ ∞
f ( x ) = x (1 − x ). ∑ 2n x n = ∑ 2n x n +1 − ∑ 2n x n +2 = x + x 2 + ∑ 2n −2 x n .
( n =0 n =0 n =0 n =2
a1 = 1; a2 = 1
Vậy .
a n = 2n −2 , n ≥ 2
(
a0 = 2; a1 = 0; a2 = −2
Ví dụ 9. Cho dãy số . Tìm an .
an+3 = 6an+2 − 11an+1 + 6an , n ≥ 0
f ( x ) − 2 + 2x2 f (x) − 2 f (x) − 2
Lời giải. Áp dụng Định lý 1, ta có: 3
= 6. 2
− 11. + 6 f (x)
x x x
20x2 − 12x + 2 20x2 − 12x + 2 5 4 1
suy ra f ( x ) = 2 3
= = − + .
1 − 6x + 11x − 6x (1 − x )(1 − 2x )(1 − 3x ) 1 − x 1 − 2x 1 − 3x
135
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Khai triển f ( x ) thành chuỗi lũy thừa ta được:
f ( x ) = 5 ∑ x n − 4 ∑ 2n x n + ∑ 3n x n = ∑ (5 − 2n +2 + 3n ) x n .
Vậy an = 5 − 2n+2 + 3n .
(
a0 = a1 = 0
Ví dụ 10. Cho dãy . Tìm an .
an+2 − 6an+1 + 9an = 2n + n, n ≥ 0
1 x
Lời giải. Ta biết hàm sinh của dãy {2n } là và hàm sinh của dãy {n} là .
1 − 2x (1 − x )2
Giả sử f ( x ) là hàm sinh của dãy { an }. Khi đó ta có:
f (x) f (x) 1 x
2
− 6. + 9 f (x) = +
x x 1 − 2x (1 − x )2
− x4 − x3 + x2 1 1 5
suy ra f ( x ) = 2 2
= 2
+ − +
(1 − 2x )(1 − x ) (1 − 3x ) 4(1 − x ) 1 − 2x 3(1 − 3x )
5
.
12(1 − 3x )2
Khai triển thành chuỗi lũy thừa ta được:
2n +2 + n + 1 + 5 ( n − 3 )3n −1 n
f (x) = ∑ x .
4
2n +2 + n + 1 + 5 ( n − 3 )3n −1
Vậy số hạng tổng quát của dãy là an = .
4
Ví dụ 11. Cho dãy số
a1 = 1 F ( n ) (0)
1 a1 a2 a . Chứng minh rằng an = ,
an = + + + · · · + n −1 , n > 1 n!
n! (n − 1)! (n − 2)! 1!
−1
với F ( x ) = x .
e −2
∞
Lời giải. Đặt a0 = 1 và gọi f ( x ) = ∑ an x n là hàm sinh của dãy đã cho. Khi đó ta có:
n =0
x x2 xn
f ( x )(e x − 1) = ( a0 + a1 x + a2 x2 + · · · + an x n + . . . )( + +···+ )
1! 2! n!
1 a 1 a a
= x + x2 ( + 1 ) + x3 ( + 1 + 2 ) + . . .
2! 1! 3! 2! 1!
2 3 n
= a1 x + a2 x + a3 x + · · · + a n x + . . .
= f (x) − 1
−1
Từ đó suy ra f ( x ) = .
ex−2
F ( n ) (0) −1
Theo khai triển Taylor thì an = , với F ( x ) = x .
n! e −2
136
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
(
a0 = 0; a1 = 1
Ví dụ 12. Dãy số Fibonacci:
a n = a n −1 + a n −2 , n ≥ 2
∞ an 1
Tìm số hạng tổng quát an của dãy và chứng minh rằng ∑ = .
n =0 4 +1
n 11
Lời giải. Giả sử f ( x ) là hàm sinh của dãy đã cho.
f (x) f (x) − x x 1 1
Theo Định lý 1, ta có: f ( x ) = + 2
⇒ f ( x ) = 2
= √ ( −
√ x
√ x 1 − x − x 5 1 − αx
1 1+ 5 1− 5
), với α = ;β = .
1 − βx 2 2
1 ∞
Khai triển f ( x ) thành chuỗi lũy thừa ta được: f ( x ) = √ ∑ (αn − βn ) x n .
√ √ 5 n =0
1 1+ 5 1− 5
Vậy an = √ (αn − βn ), với α = ;β= .
5 2 2
x ∞ ∞ an
n , nên với x = 1 ta suy ra được 1
Hơn nữa, ta có f ( x ) = 2
= ∑ a n x ∑ n + 1
= .
1−x−x n =0 4 n =0 4 11
Trong trường hợp hàm sinh của dãy là hàm phân thức với mẫu là đa thức có nghiệm phức,
ta vẫn thao tác như bình thường!
(
a0 = 0; a1 = 2
Ví dụ 13. Cho dãy số: . Tìm số hạng tổng quát an của dãy.
an+2 = −4an+1 − 8an , n ≥ 0
Lời giải. Giả sử f ( x ) là hàm sinh của dãy { an }.
f ( x ) − 2x f (x)
Ta có 2
= −4. − 8 f (x)
x x
i
2x 2x −
suy ra f ( x ) = = = 2 +
1 + 4x + 8x 2 [1 − (−2 + 2i ) x ][1 − (−2 − 2i ) x ] 1 − (−2 + 2i ) x
i
2 .
1 − (−2 − 2i ) x
i i
Khai triển f ( x ) thành chuỗi lũy thừa ta được: f ( x ) = ∑[− .(−2 + 2i )n + .(−2 − 2i )n ] x n .
2 2
i i
Như vậy, số hạng tổng quát của dãy là an = − .(−2 + 2i )n + .(−2 − 2i )n .
2 2
√ 3π 3π
Ta có thể chuyển đổi như sau: −2 ± 2i = 2 2(cos ± i sin )
4 4
√ 3nπ 3nπ
suy ra (−2 ± 2i )n = (2 2)n (cos ± i sin ).
4 4
137
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Do đó,
i √ n 3nπ 3nπ 3nπ 3nπ
an = (2 2) [(cos − i sin ) − (cos + i sin )]
2 4 4 4 4
i √ 3nπ
= (2 2)n (−2i sin )
2 4
√ 3nπ
= (2 2)n sin
4
0 nếu n = 8k; n = 8k + 4
√
(2 2)n nếu n = 8k + 6
√
−(2 2)n nếu n = 8k + 2
= 1 √
√ (2 2)n nếu n = 8k + 1; n = 8k + 3
2
1 √
− √ (2 2)n nếu n = 8k + 5; n = 8k + 7
2
(
a0 = 5; a1 = 13; a2 = 35
Ví dụ 14. Cho dãy số .
an+3 = 6an+2 − 11an+1 + 6an , n ≥ 0
Chứng minh rằng an ≡ 2n+1 (mod3n+1 ) và an ≡ 3n+1 (mod2n+1 ).
Lời giải. Áp dụng Định lý 3, xét phương trình x3 − 6x2 + 11x − 6 = 0 có các nghiệm đơn
x1 = 1; x2 = 2; x3 = 3.
Do đó số hạng tổng quát của dãy số có dạng an = a1n + b2n + c3n = a + b2n + c3n .
Từ điều kiện đã cho a0 = 5; a1 = 13; a2 = 35, ta tìm được an = 2n+1 + 3n+1 . Ta suy ra điều
phải chứng minh.
(
a0 = 11; a1 = 6; a2 = 18; a3 = 104; a4 = 346
Ví dụ 15. Cho dãy số . Tìm số
an+5 = 6an+4 − 13an+3 + 14an+2 − 12an+1 + 8an , n ≥ 0
nguyên dương lớn nhất m để a2017 chia hết cho 2m .
Lời giải. Xét đa thức p( x ) = x5 − 6x4 + 13x3 − 14x2 + 12x − 8 = ( x − 2)3 ( x − i )( x + i ).
Áp dụng Định lý 3, ta có an = p1 (n).2n + a.in + b.(−i )n với 0 ≤ deg p1 (n) ≤ 2. Từ giả thiết
của bài toán, ta tìm được an = (n2 + n + 1)2n + 5.in + 5.(−i )n .
suy ra a2017 = (20172 + 2017 + 1)22017 .
Vậy số m cần tìm là 2017.
(
c0 = 1
Ví dụ 16 (Số Catalan). Cho dãy số . Tìm công
c n = c 0 c n −1 + c 1 c n −2 + · · · + c n −1 c 0 , n ≥ 1
thức tính cn .
Lời giải. Gọi f ( x ) là hàm sinh của dãy {cn }.
Từ công thức truy hồi ở trên, ta có
cn+1 = c0 cn + c1 cn−1 + · · · + cn c0 , n ≥ 0. (3)
f (x) − 1
Theo quy tắc nhân thì {cn+1 } có hàm sinh là f ( x ). f ( x ). Do đó = f 2 ( x ),
√ x
1 ± 1 − 4x
suy ra f ( x ) = .
2x
138
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
√
1− 1 − 4x
Nhưng do f (0) = c0 = 1 nên f ( x ) = .
2x
Khai triển f(x):
1 1 1 1 1
( − 1)( − 2) . . . ( − n + 1)
Ta có (1 − 4x ) 2 = ∑ C n1 (−4x )n , với C n1 = 2 2 2 2 =
n!
2 2
(−1)n−1 [2(n − 1)]!
. .
22n (n − 1)!n!
1
∞ 2
suy ra (1 − 4x ) 2 = 1 − ∑ .C2nn x n +1 .
n =0 n + 1
1 ∞ 2 ∞ Cn
n n + 2n
suy ra f ( x ) = ∑ .C2n x 1 = ∑ .x n .
2x n=0 n + 1 n =0 n + 1
Cn
Vậy số hạng tổng quát của dãy là an = 2n .
n+1
(
a0 = 12; a1 = 4; a2 = 31
Ví dụ 17. Cho dãy số ( an ) xác định bởi: .
an+3 = 4an+2 + 3an+1 − 18an , n ≥ 0
Chứng minh rằng a2016 ≡ 1 (mod 2017).
Lời giải. Gọi hàm sinh của dãy là f ( x ) = a0 + a1 x + . . . an x n + . . . . Theo Định lý 1 ta có:
f ( x ) − 2 − 4x − 31x2 f ( x ) − 2 − 4x f (x) − 2
= 4 + 3 − 18 f ( x )
x3 x2 x
9x2 − 4x + 2 1 1
suy ra f ( x ) = 2 3
= + .
1 − 4x − 3x + 18x 1 + 2x (1 − 3x )2
Khai triển f ( x ) ta được f ( x ) = ∑((−2)n + (n + 1)3n ) x n . Do đó an = (−2)n + (n + 1)3n , và
ta có a2016 = 22016 + 2017.32016 .
Vì 2017 là số nguyên tố và (2,2017)=1 nên 22016 ≡ 1 (mod 2017). Vậy a2016 ≡ 1 (mod 2017).
1.3.5 . . . (2n + 1) ∞
Ví dụ 18. Cho dãy ( an ) xác định bởi an = , n ≥ 0. Tính ∑ an .
2017n .n! n =0
Lời giải. Dễ thấy từ công thức tổng quát của dãy số ta suy ra công thức truy hồi:
2n + 3
a0 = 1; an+1 = an , n ≥ 0
2017(n + 1)
a n +1 2
, hay 2017(n + 1) an+1 = 2nan + 3an và ⇒ , n → +∞.
an 2017
Gọi f ( x ) là hàm sinh của dãy ( an ).
Ta có f ( x ) = ∑ an x n hội tụ và 2017(∑ an+1 x n+1 )0 = 2x (∑ an x n )0 + 3(∑ an x n ).
suy ra 2017( f ( x ) − 1)0 = 2x ( f ( x ))0 + 3 f ( x )
nên (2017 − 2x ) f 0 ( x ) = 3 f ( x )
f 0 (x) 3
⇒ = .
f (x) 2017 − 2x
139
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
−3
3
Lấy nguyên hàm hai vế ta được ln f ( x ) = − ln(2017 − 2x ) + a ⇒ f ( x ) = (2017 − 2x ) 2 .e a .
2
Do f (0) = a0 = 1 nên suy ra e a = 20173/2 .
3 3
−
Vậy f ( x ) = 2017 2 .(2017 − 2x ) 2 .
Như vậy
∞
3
−
3 2017 3
∑ an = f (1) = 2017 2 .(2015) 2 = 2.
n =0 2015
Ví dụ 19 (VMO-2011). Cho dãy số nguyên { an } được xác định như sau:
a0 = 1, a1 = −1 và an = 6an−1 + 5an−2 với mọi n=2,3,4,. . . . Chứng minh rằng a2012 − 2010
chia hết cho 2011.
giải. Áp dụng Định lý 3, xét phương trình x2√− 6x − 5 = 0 √
Lời √ có hai nghiệm đơn x =
3 ± 14 nên số hạng tổng quát có dạng an = a(3 + 14) + b(3 − 14)n .
n
1 2 1 2
Từ giả thiết a0 = 1; a1 = −1 ta suy ra a = − √ ; b = + √ .
2 14 2 14
1 2 √ n 1 2 √ n
Do đó an = ( − √ )(3 + 14) + ( + √ )(3 − 14) .
2 14 2 14
1 2 √ 1 2 √
Với số nguyên tố p=2011 ta có a p+1 = ( − √ )(3 + 14) p+1 + ( + √ )(3 − 14) p+1 .
√ p +1 √ 2 √14 p+1 2 √ 14
Mà (3 + 14) = A p+1 + B p+1 . 14; (3 − 14) = A p+1 − B p+1 . 14,
( p+1)/2
p+1 ( p+1)/2
p+1
−i −i
2i 2i 2i − 1 2i − 1
(trong đó A p+1 = ∑ C p+1 .3 .14 2 và B p+1 = ∑ C p+1 .3 .14 2 )
i =0 i =0
suy ra a p+1 = A p+1 − 4B p+1 .
Do p là số nguyên tố nên ta có C kp ≡ 0 (mod p) k=1;2;. . . ;p-1, mà C kp+1 = C kp + C kp−1 nên
p+1 p−1
C kp+1 ≡ 0. Từ đó suy ra A p+1 ≡ (14 2 + 3 p+1 ) (mod p) và B p+1 ≡ 3( p + 1)(14 2 +
p−1
3 ) ≡ 3(14 2 + 3 p−1 ) (mod p). Vậy a p+1 ≡ (−3 p + 2.14( p−1)/2 ) (mod p).
p − 1
Mặt khác, ta có 452 ≡ 14 (mod p) và (p,45)=1 nên theo Định lý Phéc-ma nhỏ ta có 3 p ≡ 3
(mod p) và 14( p−1)/2 ≡ 45 p−1 ≡ 1 (mod p).
Như vậy a2012 ≡ −3 + 2 = −1 ≡ 2010 (mod p), hay a2012 − 2010 chia hết cho 2011.
Ví dụ 20 (VMO-2015). Cho f n ( x ) là dãy đa thức xác định bởi f 0 ( x ) = 2; f 1 ( x ) = 3x; và
f n ( x ) = 3x f n−1 ( x ) + (1 − x − 2x2 ) f n−2 ( x ), n ≥ 2. Tìm tất cả các số nguyên dương n để f n ( x )
chia hết cho x3 − x2 + x.
Lời giải. ( Ta coi x là hằng số và tìm công thức tổng quát cho dãy số ( an ) xác định bởi công
a0 = 2; a1 = 3x
thức: .
an = 3xan−1 + (1 − x − 2x2 ) an−2 , n ≥ 2
Áp dụng Định lý 3 ta xét phương trình t2 − 3xt − 1 + x + 2x2 = 0 có hai nghiệm đơn t = x + 1
và t = 2x − 1, do đó an = a( x + 1)n + b(2x − 1)n . Từ giả thiết a0 = 2; a1 = 3x ta suy ra a=b=1.
Vậy f n ( x ) = ( x + 1)n + (2x − 1)n .
140
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Vì f n ( x ) chia hết cho đa thức g( x ) = x3 − x2 + x nên f n (0) = 0 hay 1 − (−1)n = 0 nên n lẻ.
Lại có f n (−2) = −(5n + 1) chia hết cho (−2)2 − (−2) + 1 = 7 (do n lẻ). Mà 125 ≡ 1 (mod 7)
nên ta xét các trường hợp:
TH1: n=3k, k lẻ, thì 5n + 1 = 53k + 1 ≡ (−1)k + 1 = 0 (mod 7).
TH2: n=3k+1, k chẵn, thì 5n + 1 = 5.53k + 1 ≡ 6 (mod 7).
TH3: n=3k+2, k lẻ, thì 5n + 1 = 25.53k + 1 ≡ −24 ≡ 3 (mod 7).
Vậy điều kiện cần của n là n = 3k với k lẻ. Khi đó, f n ( x ) = ( x + 1)3k + (2x − 1)3k chia hết
cho ( x + 1)3 + (2x − 1)3 = 9( x3 − x2 + x ).
Như vậy tất cả các số n cần tìm có dạng n=3k với k lẻ, hay n=6m+3 với m là số nguyên
dương.
Ví dụ 21. Xét dãy ( an ) có a1 = 1; an = −1.an−1 + 2.an−2 − · · · + (−1)n−1 (n − 1) a1 ; n ≥ 2.
a2 = −1
Chứng minh rằng a3 + 3a2 = 0 . Từ đó tìm dư của phép chia an cho 3.
an+2 + 3an+1 + an = 0, n ≥ 2
Lời giải. Gọi f ( x ) = a1 x + a2 x2 + . . . là hàm sinh của dãy ( an ). Xét tích
F ( x ) = f ( x )(−1 + 2x2 − 3x3 + . . . )
= −1.a1 x2 + (−1.a2 + 2a1 ) x3 + (−1.a3 + 2a2 − 3a1 ) x4 + . . .
= a2 x2 + a3 x3 + a4 x4 + · · · = f ( x ) − x. (4)
1
Lại có khai triển = 1 − x + x2 − x3 + . . .
1+x
−1 2 + 4x 3 − · · · ⇒ −x
nên = − 1 + 2x − 3x = −1.x + 2x2 − 3x3 + 4x4 − . . . .
(1 + x )2 (1 + x )2
−x
Thay vào (4) ta được f ( x )( ) = f ( x ) − x ⇒ f ( x )( x2 + 3x + 1) = x3 + 2x2 + x
(1 + x )2
hay
( a1 x + a2 x2 + . . . )( x2 + 3x + 1) = x3 + 2x2 + x. Từ đó suy ra ngay
a2 = −1
a3 + 3a2 = 0 .
an+2 + 3an+1 + an = 0, n ≥ 2
Ta có a3 ≡ 0 (mod 3). Mà an+ 2 + 3an+1 + an = 0 nên an+2 + an ≡ 0 (mod 3) với n ≥ 2. Do
a2k+1 ≡ 0( mod 3 )
đó, với số nguyên k ≥ 1 ta có a4k+2 ≡ a2 ≡ 2( mod 3 ) .
a4k ≡ 1( mod 3 )
3 Một số bài tập tương tự
Bài 1 (VMO-1997). Cho dãy số nguyên { an } được xác định như sau: a0 = 1, a1 = 45 và
an+2 = 45an+1 − 7an với mọi n ∈ N.
(i) Tính số ước dương của a2n+1 − an an+2 theo n.
(ii) Chứng minh rằng 1997a2n + 7n+1 .4 là số chính phương với mỗi n.
141
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Bài 2 (VMO-1998-A). Cho dãy số nguyên { an } được xác định như sau: a0 = 20, a1 = 100 và
an+2 = 4an+1 + 5an + 20 với mọi n ∈ N.
(i) Tìm số nguyên dương h nhỏ nhất có tính chất an+h − an chia hết cho 1998.
(ii) Tìm số hạng tổng quát của dãy.
Bài 3. Dãy số ( an ) xác định bởi a1 = 1 và an = 1.2.an−1 + 2.3.an−2 + · · · + (n − 1).n.a1 , n ≥ 2.
n
Chứng minh rằng an+3 − 4an+2 − an+1 = 2 ∑ ak ; n ≥ 2.
k =1
n
Bài 4. Với số nguyên dương n, tính tổng an = ∑ (−1)k Cn3k . Xét tính tuần hoàn của dãy ( an )
k =1
và chỉ ra an chia hết cho 3[n/2]−1 .
Bài 5. Xét dãy số ( an ) với a1 = 1; an = 12 an−1 + 22 an−2 + · · · + (n − 1)2 a1 , n ≥ 2.
a2 = 4a1 − 3
Chứng minh rằng a3 = 4a2 − 2a1 + 3 . Từ đó tìm công thức tổng quát an .
an+3 = 4an+2 − 2an+1 + an , n ≥ 2
(
a0 = 1,
Bài 6. Tìm số hạng tổng quát của dãy số ( an ) biết
an = 2an−1 + n.3n .
(
u0 = 1
Bài 7. Tìm công thức tổng quát cho dãy (un ) với .
un = a.un−1 + bn , n ≥ 1
(
a0 = a1 = 0
Bài 8. Tìm số hạng tổng quát của dãy ( an ) cho bởi .
an+2 − 6.an+1 + 9an = 2n + n, n ≥ 0
a1 = 1
Bài 9. Cho dãy số ( an ) biết a2n = an . Tìm số hạng tổng quát của dãy.
a2n+1 = an + an+1
2n + 3 ∞
Bài 10. Cho dãy ( an ) xác định bởi a1 = 1 và an+1 = an , n ≥ 0. Tính tổng T = ∑ an .
4( n + 1) n =0
a n −1 a a1
Bài 11. Dãy ( an ) xác định bởi a1 = 1 và an = −( + n −2 + · · · + ), n ≥ 2. Tìm
1! 2! ( n − 1) !
tất cả các số nguyên dương n sao cho n!an+1 = 1.
Tài liệu
[1] Srini Devadas and Eric Lenhman, Generating Funtions, Lectures Notes, April 2005.
[2] Trần Nam Dũng, Hàm sinh, Bài giảng 2011.
[3] Nguyễn Văn Mậu (Chủ biên), Toán rời rạc và các dạng toán liên quan, NXB Giáo dục 2008.
142
nguon tai.lieu . vn
