Các đa thức dạng Fibonacci

Chia sẻ: Nguyễn Minh Hải | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

7
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu "Các đa thức dạng Fibonacci" trình bày các nội dung chính sau: Đa thức Fibonacci; Đa thức Lucas; Đa thức Morgan-Voyce; Nghiệm của các đa thức dạng Fibonacci;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các đa thức dạng Fibonacci

Các đa thức dạng Fibonacci Lê Kim Uyên Trường THPT Ngô Gia Tự, Eakar, Đak Lak 1 Đa thức Fibonacci và đa thức Lucas Định nghĩa 1. Dãy đa thức {fn (x)}, n ∈ Z+ thỏa mãn hệ thức truy hồi fn+2 (x) = xfn+1 (x) + fn (x), với mọi n ∈ Z+ trong đó f0 (x) = 0, f1 (x) = 1 được gọi là một dãy đa thức Fibonacci, ký hiệu {fn (x)}. Nhận xét 1. deg fn (x) = n − 1, ∀n ≥ 1. Định nghĩa 2. Dãy đa thức {ln (x)}, n ∈ Z+ thỏa mãn hệ thức truy hồi ln+2 (x) = xln+1 (x) + ln (x), với mọi n ∈ Z+ trong đó l0 (x) = 2, l1 (x) = x được gọi là một dãy đa thức Lucas, ký hiệu {ln (x)}. Nhận xét 2. deg ln (x) = n, ∀n ≥ 0. Định lý 1. Với mọi n ≥ 1 chúng ta có (n−1)/2 n−j−1 fn (x) = xn−2j−1 j j=0 Chứng minh. Cách 1: Đặt (n−1)/2 n−j−1 gn (x) = xn−2j−1 , n ≥ 1 j j=0 Ta sẽ chứng minh gn (x) = fn (x). Từ cách đặt ta thu được g1 (x) = 1 = f1 (x) và g2 (x) = x = f2 (x). Để chứng minh gn (x) = fn (x) ta chứng minh gn (x) thỏa mãn công thức truy hồi gn (x) = xgn−1 (x) + gn−2 (x), ∀n ≥ 2. + Với n chẵn, n = 2k, k ∈ Z+ chúng ta có xgn−1 (x) + gn−2 (x) = 168
(n−2)/2 (n−3)/2 n−j−2 n−2j−2 n−j−3 =x x + xn−2j−3 j j j=0 j=0 (n−2)/2 (n−1)/2 n−j−2 n−2j−1 n−j−2 = x + xn−2j−1 j j−1 j=0 j=1 (n−2)/2 (n−2)/2 n−1 n−j−2 n−2j−1 n−j−2 =x + x + xn−2j−1 j j−1 j=1 j=1 (n−2)/2 n−1 n−j−2 n−j−2 =x + + xn−2j−1 j j−1 j=1 (n−2)/2 (n−2)/2 n−1 n−j−1 n−2j−1 n−j−1 =x + x = xn−2j−1 j j j=1 j=0 (n−1)/2 n−j−1 = xn−2j−1 = gn (x). j j=0 + Với n lẻ, n = 2k + 1, k ∈ Z+ . Chứng minh tương tự ta cũng thấy gn (x) thỏa mãn công thức truy hồi gn (x) = xgn−1 (x) + gn−2 (x). Ta được gn (x) = fn (x), ∀n ≥ 1. Cách 2: Chúng ta có ∞ y = fn (x) y n (1) 1 − xy − y 2 n=0 Nhưng   ∞ n/2 1 n−j =  (−1)j (2t)n−2j z n (2) 1 − 2zt + z 2 j n=0 j=0 n/2 n−j Un (t) = (−1)j (2t)n−2j j j=0 là đa thức Chebyshev lọai hai. Đặt x = 2it; z = it thì ∞ 1 = in Un (x/2i)y n 1 − xy − y 2 n=0 Do đó ∞ y = in Un (x/2i)y n+1 (3) 1 − xy − y 2 n=0 169
Ta được fn+1 (x) = in Un (x/2i) n/2 n n−j =i (−1)j (x/i)n−2j j j=0 n/2 n−j = xn−2j j j=0 Do đó (n−1)/2 n−j−1 fn (x) = xn−2j−1 j j=0 Định lý 2. Giả sử α(x) và β(x) là nghiệm của phương trình bậc hai t2 − xt − 1 = 0; √ √ x + x2 + 4 x − x2 + 4 α(x) = và β(x) = 2 2 Khi đó αn (x) − β n (x) fn (x) = α (x) − β (x) và ln (x) = αn (x) + β n (x) Chứng minh. Tương tự với p(x) = x, q(x) = 1, a1 (x) = l1 (x) = x, a0 (x) = l0 (x) = 2 chúng ta được x − 2β(x) n x − 2α(x) n ln (x) = an (x) = α (x) − β (x) α(x) − β(x) α(x) − β(x) [α(x) + β(x)] − 2β(x) n [α(x) + β(x)] − 2α(x) n = α (x) − β (x) α(x) − β(x) α(x) − β(x) = αn (x) + β n (x) n Định lý 3. x fi (x) = fn+1 (x) + fn (x) − 1 1 Chứng minh. Sử dụng hệ thức truy hồi của đa thức Fibonacci, ta được n n n fi+1 (x) = x fi (x) + fi−1 (x) i=1 i=1 i=1 hay n f2 (x) + f3 (x) + ... + fn (x) + fn+1 (x) = x fi (x) + [f0 (x) + f1 (x) + ... + fn−1 (x) ] i=1 170
Do đó n fn (x) + fn+1 (x) = x fi (x) + f0 (x) + f1 (x) i=1 Mà f0 (x) = 0, f1 (x) = 1 nên n x fi (x) = fn+1 (x) + fn (x) − 1 1 n Hệ quả 1. Fi = Fn+1 − 1 1 Chứng minh. Ta có n fi (1) = fn+1 (1) + fn (1) − 1 1 Mà fi (1) = Fi và Fn+2 = Fn+1 + Fn nên ta được n Fi = Fn+1 − 1 1 Tính chất 1. (Liên hệ giữa đa thức Fibonacci và Lucas) i) ln (x) = fn+1 (x) + fn−1 (x) ii) ln (x) = xfn (x) + 2fn−1 (x) iii) xln (x) = fn+2 (x) − fn−2 (x) Mệnh đề 1. Giả sử {fn (x)} là một dãy đa thức Fibonacci. Khi đó, nếu x 1 Q(x) = 1 0 thì fn+1 (x) fn (x) Qn (x) = fn (x) fn−1 (x) trong đó n ≥ 1. Tính chất 2. Chúng ta có n i) x fi (x) = fn+1 (x) + fn (x) − 1 1 n ii) x li (x) = ln+1 (x) + ln (x) − x − 2 1 171
Tính chất 3. Chúng ta có một số tính chất sau i) fn+1 (x)fn−1 (x) − fn (x) = (−1)n (công thức Cassini) 2 ii) fn+1 (x)fn−2 (x) − fn (x)fn−1 (x) + x(−1)n = 0 iii) fm+n (x) = fm+1 (x)fn (x) + fm (x)fn−1 (x) iv) ln+1 (x)ln−1 (x) − ln (x) = (−1)n−1 (x2 + 4) 2 v) ln+1 (x)ln−2 (x) − ln (x)ln−1 (x) + x(−1)n−1 (x2 + 4) = 0 2 2 vi) fn (x) + fn+1 (x) = f2n+1 (x) n−1 vii) fn (x) = fi (x)fn−i (x) trong đó fn (x) là đạo hàm của fn (x) theo biến x và i=1 n ≥ 1. Tính chất 4. Chúng √ có một số kết quả sau ta n ln (x)+ x2 +4fn (x) i) α (x) = √2 ln (x)− x2 +4fn (x) ii) β n (x) = 2 Tính chất 5. (Liên hệ giữa đa thức Fibonacci và Lucas) i) fm (x) = lk (x)fm−k (x) + (−1)k+1 fm−2k (x) ii) ln (x) − (x2 + 4)fn (x) = 4(−1)n 2 2 iii) ln (x) + ln+1 (x) = (x2 + 4)f2n+1 (x) 2 2 iv) fm+n (x) + (−1)n fm−n (x) = fm (x)ln (x) v) fm (x)ln (x) + fn (x)lm (x) = 2fm+n (x) f(2m+1)n (x) Tính chất 6. fn (l2m+1 (x)) = f2m+1 (x) Hệ quả 2. i) Fm+n = Fm+1 Fn + Fm Fn−1 (n−1)/2 n−j−1 ii) Fn = j=0 j iii) Fm+n + (−1)n Fm−n = Fm Ln iv) Fn+1 .Fn−1 − Fn = (−1)n 2 v) Fm+n = Fm+1 Fn + Fm Fn−1 Ví dụ 1. i) 2 4−j f5 (x) = x4−2j j 0 4 3 2 = x4 + x2 + x0 0 1 0 = x4 + 3x2 + 1. √ √ √ ii)(x + x2 + 4)5 − (x − x2 + 4)5 = 32(x4 + 3x2 + 1) x2 + 4 Do đó f5 (x) = x4 + 3x2 + 1 iii) 4 x fi (x) = x[1 + x + (x2 + 1) + (x3 + 2x)] 1 172
= x4 + x3 + 3x2 + x f5 (x) + f4 (x) − 1 = (x4 + 3x3 + 1) + (x3 + 2x) − 1 = x4 + x3 + 3x2 + x 4 =x fi (x). 1 iv)Với m = 3 và n = 4 thì fm+1 (x)fn+1 (x) + fm (x)fn (x) = f4 (x)f5 (x) + f3 (x)f4 (x) = (x3 + 2x)(x4 + 3x2 + 1) + (x2 + 1)(x3 + 2x) = x7 + 6x5 + 10x3 + 4x = f8 (x) = fm+n+1 (x) v) f6 (x) =x5 + 4x3 + 3x f6 (x) =5x4 + 12x2 + 3 5 fi (x)f6−i (x) =f1 (x)f5 (x) + f2 (x)f4 (x) i=0 + f3 (x)f3 (x) + f4 (x)f2 (x) + f5 (x)f1 (x) 2 =2f1 (x)f5 (x) + 2f2 (x)f4 (x) + f3 (x) =5x4 + 12x2 + 3 =f6 (x) 2 Đa thức Gn(x) và đa thức Hn(x) Sử dụng dãy Pascal trong bảng 13.3, H. W. Gould năm 1965 đã nghiên cứu đa thức n Gn (x) = A(n, j)xj j=0 trong đó n − (j + 1)/2 A(n, j) = j/2 xác định điểm chuyển thứ j trên dòng n. n−k n−k−1 Vì A(n, 2k) = và A(n, 2k + 1) = , nên Gn (x) có thể viết k k lại n/2 (n−1)/2 n−k 2k n−k−1 Gn (x) = x + x2k+1 k k 0 0 173
Khi đó (n+1)/2 n/2 n−k+1 2k n−k Gn+1 (x) = x + x2k+1 k k 0 0 và n/2 (n−1)/2 2 n−k 2k+2 n−k−1 x Gn (x) = x + x2k+3 k k 0 0 (n+2)/2 (n+1)/2 n−k+1 2k n−k = x + x2k+1 k−1 k−1 1 1 Dùng đồng nhất thức Pascal ta được (n+2)/2 (n+1)/2 2 n−k+2 2k n−k+1 Gn+1 (x) + x Gn (x) = x + x2k+1 k k 0 0 = Gn+2 (x) Do đó Gn (x) thỏa mãn công thức truy hồi Gn+2 (x) = Gn+1 (x) + x2 Gn (x) Sử dụng đa thức Gn (x) Gould mở rộng nghiên cứu lên đa thức Hn (x) : n n Hn (x) = x Gn (1/x) = A(n, j)xn−j j=0 Chú ý rằng: Hn+2 (x) = xn+2 Gn+2 (1/x) = xn+2 [Gn+1 (1/x) + x−2 Gn (1/x)] = xn+2 Gn+1 (1/x) + xn [Gn (1/x) = xHn+1 (x) + Hn (x). trong đó H0 (x) = G0 (1/x) = 1 và H1 (x) = xG1 (1/x) = x + 1. Đây là một đa thức dạng Fibonacci được nghiên cứu bởi Catalan. Nhận xét 3. deg Hn (x) = n, ∀n ≥ 1 Tính chất 7. n x Hi (x) = Hn+1 (x) + Hn (x) − x − 2 1 Tính chất 8. Chúng ta có i) Hn+1 (x)Hn−1 (x) − Hn (x) = x(−1)n 2 ii) Hn+1 (x)Hn−2 (x) − Hn (x)Hn−1 (x) + x2 (−1)n = 0 174
Chứng minh. Suy ra trực tiếp từ định lý ?? và tính chất ?? với q(x) = 1, H0 (x) = 1, H1 (x) = x + 1, H2 (x) = x2 + x + 1. Định lý 4. Với n ≥ 0 chúng ta có n n − (i + 1)/2 Hn (x) = xn−i i/2 0 Chứng minh. Chứng minh tương tự đa thức fn (x). Định lý 5. Giả sử α(x) và β(x) là các nghiệm của phương trình đặc trưng t2 −xt−1 = 0; √ √ x + x2 + 4 x − x2 + 4 α(x) = và β(x) = 2 2 Khi đó 1 √ √ Hn (x) = −x + 2 + x2 + 4 αn (x) − −x + 2 − x2 + 4 β n (x) 2 (α(x) − β(x)) trong đó n ≥ 0. Chứng minh. Chúng minh định lý bằng các cách khác nhau bằng cách suy ra trực tiếp từ định lý ??, ??, ??. Tính chất 9. Chúng ta có một số kết quả sau √ 2 i) αn (x) = 1 ln (x) + x+2+x +4+4 Hn (x) 2 2 √ x2 √ 1 2 x2 +4 ii) β n (x) = 2 ln (x) − √ H (x) x+2+ x2 +4 n Chứng minh. Sử dụng công thức Binet của ln (x) và Hn (x) chúng ta có. i) √ 1 2 x2 + 4 1 ln (x) + √ Hn (x) = [αn (x) + β n (x) + αn (x) − β n (x)] 2 x + 2 + x2 + 4 2 = αn (x) ii) Chứng minh tương tự i). Tính chất 10. Với n ≥ 0 chúng ta có n i) fn+1 (x) = (−1)n+i Hi (x) i=0 ii) fn+1 (x) + fn (x) = Hn (x) Chứng minh. i) Vì f1 (x) + f0 (x) = 1 + 0 = 1 = H0 (x) và f2 (x) + f1 (x) = x + 1 = H1 (x), suy ra Hn (x) = fn+1 (x) + fn (x). Do đó (−1)i+1 Hi (x) = (−1)i+1 fi+1 (x) − (−1)i fi (x) 175
nên n n i+1 (−1) Hi (x) = [(−1)i+1 fi+1 (x) − (−1)i fi (x)] i=0 i=0 = −f0 (x) + (−1)n+1 fn+1 (x) = (−1)n+1 fn+1 (x). Vậy n fn+1 (x) = (−1)n+i Hi (x) i=0 ii) Theo tính chất i) chúng ta có n n−1 fn+1 (x) + fn (x) = (−1)n+i Hi (x) + (−1)n+i−1 Hi (x) i=0 i=0 n n−1 n+1 = (−1) H0 (x) + (−1) H0 (x) + (−1) H1 (x) + (−1)n H1 (x) + + ... + (−1)2n−1 Hn−1 (x) + (−1)2n−2 Hn−1 (x) + (−1)2n Hn (x) =Hn (x) Mệnh đề 2. (Liên hệ với số Fibonacci) i) Gn (1) = Fn+2 , n ≥ 0 ii) Hn (1) = Fn+1 , n ≥ 0 3 Đa thức gn(x) và đa thức hn(x) Chúng ta có thể thu được đa thức gn (x) và hn (x) từ đa thức fn (x) và ln (x) bằng cách thay đổi dấu cộng thành dấu trừ trong công thức truy hồi. g0 (x) = 0 g1 (x) = 1 gn (x) = xgn−1 (x) − gn−2 (x) n≥2 h0 (x) = 2 h1 (x) = x hn (x) = xhn−1 (x) − hn−2 (x) n≥2 Hai đa thức này có mối quan hệ với đa thức Chebyshev loại một và loại hai. Nhận xét 4. Chúng ta có deg gn (x) = n − 1, ∀n ≥ 1 deg hn (x) = n, ∀n ≥ 0 Tính chất 11. Chúng ta có n i) (x − 2) gi (x) = gn+1 (x) − gn (x) − 1 1 n ii) (x − 2) hi (x) = hn+1 (x) − hn (x) − x + 2 1 176
Tính chất 12. Chúng ta có một số tính chất sau : 2 i) gn+1 (x)gn−1 (x) − gn (x) = −1 ii) gn+1 (x)gn−2 (x) + gn (x)gn−1 (x) + x = 0 iii) hn+1 (x)hn−1 (x) − h2 (x) = x2 − 4 n iv) hn+1 (x)hn−2 (x) + hn (x)hn−1 (x) − x(x2 − 4) = 0 Chứng minh. Suy ra trực tiếp từ định lý ?? và tính chất ??. Định lý 6. Với n ≥ 0 chúng ta có n−1 2 n−i−1 gn (x) = (−1)i xn−2i−1 i 0 Chứng minh. Chứng minh tương tự như đa thức fn (x). Định lý 7. Giả sử γ(x) và δ(x) là các nghiệm của phương trình đặc trưng t2 − xt + 1 = 0; √ √ x + x2 − 4 x − x2 − 4 γ(x) = và δ(x) = 2 2 Khi đó γ n (x) − δ n (x) gn (x) = và hn (x) = γ n (x) + δ n (x) γ(x) − δ(x) trong đó x = 2. Chứng minh. Chúng minh định lý bằng các cách khác nhau bằng cách suy ra trực tiếp từ định lý ??, ??, ??. Tính chất 13. Chúng√ta có x2 i) γ n (x) = hn (x)+ √2 −4gn (x) hn (x)− x2 −4gn (x) ii) δ n (x) = 2 Chứng minh. Áp dụng công thức Binet của hn (x) và gn (x). Tính chất 14. (Liên hệ giữa đa thức gn (x) và đa thức hn (x)) i) h2 (x) − (x2 − 4)gn (x) = 4 n 2 ii) hn (x) = gn+1 (x) − gn−1 (x) Chứng minh. i) Áp dụng định lý 7 chúng ta có [γ n (x) − δ n (x)]2 h2 (x) − (x2 − 4)gn (x) = [γ n (x) + δ n (x)]2 − (x2 − 4). n 2 [γ(x) + δ(x)]2 = [γ n (x) + δ n (x)]2 − [γ n (x) − δ n (x)]2 n n n 1 2 2 2 = 4γ (x).δ (x) = 4 [x − (x − 4)] 4 =4 177
ii) Chúng ta chứng minh bằng phương pháp qui nạp. Với n = 1 chúng ta có h1 (x) = x = g2 (x) − g0 (x). Giả sử công thức đúng với mọi n = 1, 2, ..., n − 1 (n ≥ 2). Khi đó hn+1 (x) = xhn (x) − hn−1 (x) = x[gn+1 (x) − gn−1 (x)] − [gn (x) − gn−2 (x)] = [xgn+1 (x) − gn (x)] − [xgn−1 (x) − gn−2 (x)] = gn+2 (x) − gn (x) Vậy hn (x) = gn+1 (x) − gn−1 (x). f2mn (x) Tính chất 15. gn (l2m (x)) = f2m (x) fk (x).fn (lk (x)) nếu k lẻ Định lý 8. fnk (x) = fk (x).gn (lk (x)) nếu k chẵn Chứng minh. Suy ra từ tính chất 6 và 15. Hệ quả 3. fk (x)| fnk (x) (n−1)/2 n−j−1 n−2j−1 Hệ quả 4. fnk (x) = fk (x) (−1)(k+1)j lk (x) j=0 j Định lý 9. ln (l2m−1 (x)) = l(2m−1)n (x) và hn (l2m (x)) = l2mn (x) Chứng minh. Chúng ta có ln (l2m−1 (x)) = αn (l2m−1 (x)) + β n (l2m−1 (x)) = α(2m−1)n (x) + β (2m−1)n (x) = l(2m−1)n (x) Vì γ(l2m (x)) = α2m (x) và δ(l2m (x)) = β 2m (x); hn (x) = γ n (x) + δ 2m (x) nên hn (l2m (x)) = α2mn (x) + β 2mn (x) = l2mn (x) Hệ quả 5. ln (x) l(2m−1)n (x) Chứng minh. Chúng ta có l1 (x) = x, l2 (x) = x2 + 2 Hơn nữa theo công thức truy hồi ta có l2k−1 (x) = xl2k−2 (x) + l2k−3 (x) nên x |l2k−1 (x) ∀k ≥ 2. Tương tự x |h2k−1 (x) ∀k ≥ 2. Vì l2m−1 (l2k−1 (x)) = l(2m−1)(2k−1) (x) và l2k−1 (x) |l2m−1 (l2k−1 (x)) nên suy ra l2k−1 (x) l(2m−1)(2k−1) (x). Tương tự h2m−1 (l2k (x)) = l(2m−1)(2k) (x) và l2k (x) |h2m−1 (l2k (x)), vì vậy ta được l2k (x) l(2m−1)(2k) (x). Do đó khi n lẻ hoặc chẵn ta đều có ln (x) l(2m−1)n (x). 178
Hệ quả 6. Chúng ta có i) Fk |Fnk ii) Ln L(2m−1)n Ví dụ 2. Các ví dụ áp dụng i) 1 2−j 2−2j f6 (x) = f2 (x) (−1)j l2 (x) j 0 2 2 1 0 2 =x l2 (x) − l2 (x) = x x2 + 2 −1 0 1 = x5 + 4x3 + 3x ii) l3.4 (x) = l12 (x) = x12 + 12x10 + 54x8 + 12x6 + 105x4 + 36x2 + 2 = (x4 + 4x2 + 2)(x8 + 8x6 + 20x4 + 16x2 + 1) = l4 (x).[l8 (x) − 1] Vì vậy l4 (x) |l3.4 (x). 4 Đa thức Jacobsthal Định nghĩa 3. Đa thức Jn (x), n ∈ Z thỏa mãn hệ thức truy hồi Jn (x) = Jn−1 (x) + xJn−2 (x), n ≥ 2 trong đó J1 (x) = 1, J0 (x) = 0 được gọi là đa thức Jacobsthal. Nhận xét 5. Chúng ta có một số nhận xét sau: + Đa thức Jacobsthal J2n−1 (x) và J2n (x) có bậc giống nhau. + Bậc của Jn (x) là (n − 1)/2 . + Hệ số của số hạng cao nhất của J2n−1 (x) là 1, và của J2n (x) là n. + Các hệ số của Jn (x) giống các hệ số của fn (x) nhưng có bậc khác nhau. + Các hệ số của đa thức Jacobsthal nằm trên đường chéo tăng chỉnh trái của tam giác Pascal, với các bậc khác nhau. Định lý 10. Với mọi n ≥ 1 chúng ta có (n−1)/2 n/2 + j (n−1)/2 −j Jn (x) = x (n − 1)/2 − j j=0 Chứng minh. Vì các hệ số của Jn (x) giống các hệ số của fn (x) với các bậc khác nhau nên ta có điều phải chứng minh. 179
n Tính chất 16. x Ji (x) = Jn+1 (x) + xJn (x) − 1 1 Tính chất 17. Chúng ta có i) Jn+1 (x)Jn−1 (x) − Jn (x) = (−1)n xn−1 2 ii) Jn+1 (x)Jn−2 (x) − Jn (x)Jn−1 (x) + (−1)n xn−2 = 0 Chứng minh. Áp dụng trực tiếp từ định lý ?? và tính chất ?? với q(x) = x, J0 (x) = 0, J1 (x) = 1, J2 (x) = 1. Định lý 11. Giả sử r(x) và s(x) là nghiệm của phương trình đặc trưng t2 − t − x = 0; √ √ 1 + 1 + 4x 1 − 1 + 4x r(x) = và s(x) = 2 2 thì rn (x) − sn (x) Jn (x) = √ 1 + 4x trong đó n ≥ 1 Chứng minh. Chúng ta có thể chứng minh định lý bằng các cách khác nhau bằng cách sử dụng các định lý ??, ??, ?? với p(x) = 1, q(x) = x, a0 (x) = J0 (x) = 0, a1 (x) = J1 (x) = √ 1, α(x) = r(x), β(x) = s(x), α(x) − β(x) = 1 + 4x. Ví dụ 3. 3 3+j J7 (x) = x3−j 3−j 0 3 4 5 6 = x3 + x2 + x+ 3 2 1 0 = x3 + 6x2 + 5x + 1 Tương tự, J8 (x) = 4x3 + 10x2 + 6x + 1 5 Đa thức Kn(x) Định nghĩa 4. Đa thức Kn (x), n ≥ Z được xác định bởi hệ thức truy hồi Kn (x) = Kn−1 (x) + xKn−2 (x), n≥3 trong đó K1 (x) = 1 và K2 (x) = x. Nhận xét 6. Chúng ta có một số nhận xét sau: + Bậc của Kn (x) là n/2 , vì vậy K2n (x) và K2n+1 (x) có cùng bậc. + Hệ số của số hạng cao nhất của Kn (x) là 1 nếu n chẵn (n + 1)/2 nếu n lẻ + x |Kn (x) với mọi n ≥ 2. (Giả sử n = 0 ) + Khi n ≥ 3 thì hệ số của x là 2. 180
n Tính chất 18. i) x Ki (x) = Kn+1 (x) + xKn (x) − x 1 ii) Kn+1 (x)Kn−1 (x) − Kn (x) = (x − 2)(−x)n−1 2 iii) Kn+1 (x)Kn−2 (x) − Kn (x)Kn−1 (x) + (−1)n−1 (x − 2)xn−2 = 0 Chứng minh. Suy ra trực tiếp từ định lý ?? và tính chất ?? với q(x) = x, K0 (x) = x−1 x , K1 (x) = 1, K2 (x) = x. Định lý 12. Kn (x) = x[Jn−1 (x) + Jn−2 (x)] trong đó n ≥ 2. Mệnh đề 3. Hàm sinh của Kn (x) là t + (x − 1)t2 g(t) = ,n ≥ 1 1 − t − xt2 Hệ quả 7. Chúng ta có một số hệ quả sau i) Fn = Fn−1 + Fn−2 , n ≥ 3. n−1 n+3j−1 n+j−2 ii) F2n = 1 + 1 2j n−j−1 n−1 n+3j−1 n+j−1 iii) F2n+1 = 0 2j n−j−1 Chứng minh. Sử dụng Km (1) = Fm = Jm (1) và định lý 12, định lý ?? ta được điều phải chứng minh. Ví dụ 4. Một số ví dụ minh họa. i) K9 (x) = x[J8 (x) + J7 (x)] = x[(4x3 + 10x2 + 6x + 1) + (x3 + 6x2 + 5x + 1)] = 5x4 + 16x3 + 11x2 + 2x Tương tự, K8 (x) = x4 + 9x3 + 9x2 + 2x. ii) 2 2 2 + 3j 1+j K6 (x)/x = x + x2−j 2j 2−j 1 5 2 3 = x2 + x+2 2 1 0 = x2 + 5x + 2 K6 (x) = x3 + 5x2 + 2x Tương tự, 2 4 + 3j 2+j K7 (x)/x = x2−j 2j + 1 2−j 0 181
2 7 3 10 4 =4 x2 + x+ 2 3 1 5 0 = 4x2 + 7x + 2 K7 (x) = 4x3 + 7x2 + 2x iii) 4 6 + 3j 4+j F11 = 2j 4−j 0 49 5 12 6 15 7 18 8 =6 + + + + 43 2 5 2 7 1 9 0 = 6 + 30 + 36 + 15 + 2 = 89 5 5+3j 4+j và F12 = 1 + = 144 1 2j 5−j 6 Đa thức Morgan-Voyce Định nghĩa 5. Đa thức Morgan-Voyce bn (x) và Bn (x) được định nghĩa bởi hệ thức truy hồi bn (x) = xBn−1 (x) + bn−1 (x) (4) Bn (x) = (x + 1)Bn−1 (x) + bn−1 (x) (5) trong đó b0 (x) = 1 = B0 (x) và n ≥ 1. Trừ (4) và (5) vế theo vế chúng ta được bn (x) = Bn (x) − Bn−1 (x) (6) và từ hệ thức (4) chúng ta được xBn (x) = bn+1 (x) − bn (x) (7) Thế bn (x) từ (6) vào (4) chúng ta thu được hệ thức truy hồi: Bn (x) = (x + 2)Bn−1 (x) − Bn−2 (x) n≥2 (8) trong đó B0 (x) = 1 và B1 (x) = x + 2. Từ (4), (5), (7) chúng ta được bn (x) =xBn−1 (x) + bn−1 (x) =x[(x + 1)Bn−2 (x) + bn−2 (x)] + bn−1 (x) =x[Bn−2 (x) + bn−1 (x)] + bn−1 (x) =[bn−1 (x) − bn−2 (x)] + (x + 1)bn−1 (x) =(x + 2)bn−1 (x) − bn−2 (x) Vậy bn (x) = (x + 2)bn−1 (x) − bn−2 (x) n≥2 (9) trong đó b0 (x) = 1 và b1 (x) = x + 1. 182
Nhận xét 7. Với n ≥ 0 chúng ta có deg Bn (x) = n deg bn (x) = n Tính chất 19. Chúng ta có n i) x Bi (x) = Bn+1 (x) − Bn (x) − x − 1 1 n ii) x bi (x) = bn+1 (x) − bn (x) − x 1 Tính chất 20. (Một số tính chất cơ bản của đa thức Morgan-Voyce) i) xBn (x) = (x + 1)bn (x) − bn−1 (x) ii) Bn+1 (x) − Bn−1 (x) = bn+1 (x) + bn (x) iii) x[Bn (x) + Bn−1 (x)] = bn+1 (x) − bn−1 (x) Định lý 13. Với n ≥ 0 chúng ta có n n+i+1 Bn (x) = xi (10) n−i i=0 và n n+i bn (x) = xi (11) n−i i=0 Định lý 14. Giả sử r(x) và s(x) là nghiệm của phương trình đặc trưng t2 −(x+2)t+1 = 0; √ √ x + 2 + x2 + 4x x + 2 − x2 + 4x r(x) = và s(x) = 2 2 thì rn+1 (x) − sn+1 (x) Bn (x) = r(x) − s(x) và 1 √ √ bn (x) = x+ x2 + 4x rn (x) − x − x2 + 4x sn (x) r(x) − s(x) trong đó n ≥ 1 Chứng minh. Sử dụng kiến thức sai phân chúng ta sẽ chứng minh công thức Binet của Bn (x). Theo giả thiết nghiệm của phương trình đặc trưng của hệ thức truy hồi (8) là √ √ x + 2 + x2 + 4x x + 2 − x2 + 4x r(x) = và s(x) = 2 2 √ trong đó r(x) + s(x) = x + 2, r(x) − s(x) = x2 + 4x và r(x).s(x) = 1. Vì vậy nghiệm tổng quát của hệ thức truy hồi (8) là Bn (x) = Crn (x) + Dsn (x), trong đó hệ số C và D được xác định. 183
Sử dụng các điều kiện ban đầu B0 (x) = 1 và B1 (x) = x + 2 = r(x) + s(x) chúng ta được hệ phương trình tuyến tính sau C +D =1 Cr(x) + Ds(x) = r(x) + s(x) Giải hệ chúng ta được r(x) −s(x) C=√ và D = √ x2 + 4x x2 + 4x Do đó rn+1 (x) − sn+1 (x) Bn (x) = r(x) − s(x) trong đó n ≥ 0. Ngoài ra ta còn có thể chứng minh định lý bằng các cách khác nhau từ các định lý ??, ??, ??. Với bn (x) chúng ta chứng minh tương tự Bn (x). Mệnh đề 4. (Hàm sinh của đa thức Morgan-Voyce) 1 Bn (x)tn = n≥0 1 − (x + 2)t + t2 1−t bn (x)tn = n≥0 1 − (x + 2)t + t2 Chứng minh. Chúng ta có thể chứng minh mệnh đề bằng cách suy ra trực tiếp từ mệnh đề ??. Ngoài ra chúng ta cũng có thể chứng minh bằng cách sau Vì nghiệm của phương trình đặc trưng t2 − (x + 2)t + 1 = 0 là r(x) và s(x), nên 1 1 2 = 1 − (x + 2)t + t (1 − r(x)t)(1 − s(x)t) A B = + 1 − r(x)t 1 − s(x)t dùng đồng nhất thức ta được A = r/(r − s), B = −s/(r − s), r = r(x) và s = s(x). Từ đó ta được ∞ ∞ 1 (rn+1 − sn+1 )tn = = Bn (x)tn (12) 1 − (x + 2)t + t2 n=0 r−s n=0 Do đó ∞ ∞ t n+1 = Bn (x)t = Bn−1 (x)tn (13) 1 − (x + 2)t + t2 n=0 n=1 184
Vì vậy ∞ ∞ 1−t n = Bn (x)t − Bn−1 (x)tn 1 − (x + 2)t + t2 n=0 n=1 ∞ = B0 (x) + [Bn (x) − Bn−1 (x)]tn n=1 ∞ (14) =1+ bn (x)tn n=1 ∞ = bn (x)tn n=0 Phương trình (12) và (14) cho chúng ta hàm sinh của Bn (x) và bn (x). Mệnh đề 5. Giả sử Bn (x) là đa thức Morgan-Voyce. Khi đó, nếu x + 2 −1 S(x) = 1 0 thì Bn (x) −Bn−1 (x) S n (x) = Bn−1 (x) −Bn−2 (x) trong đó n ≥ 1. Tính chất 21. (Tính chất của đa thức Morgan-Voyce) 2 i) Bn+1 (x)Bn−1 (x) − Bn (x) = −1 ii) Bn+1 (x)Bn−2 (x) − Bn (x)Bn−1 (x) + (x + 2) = 0 iii) bn+1 (x)bn−1 (x) − b2 (x) = x n iv) bn+1 (x)bn−2 (x) − bn (x)bn−1 (x) − x(x + 2) = 0 v) Bm+n (x) = Bm (x)Bn (x) − Bm−1 (x)Bn−1 (x) 2 2 vi) B2n (x) = Bn (x) − Bn−1 (x) vii) B2n−1 (x) = [Bn (x) − Bn−2 (x)]Bn−1 (x) 2 2 viii) (x + 2)B2n−1 (x) = Bn (x) − Bn−2 (x) Tính chất 22. (Liên hệ giữa đa thức Morgan-Voyce và đa thức Fibonacci) i) f2n (x) = xBn−1 (x2 ) ii) f2n+1 (x) = bn (x2 ) trong đó n ≥ 0. Chứng minh. Cách 1: Sử dụng phương trình (13) và (14) chúng ta được ∞ t(1 − t2 ) = bn (x2 )t2n+1 1 − (x2 + 2)t2 + t4 n=0 và ∞ xt2 = xBn−1 (x2 )t2n 1 − (x2 + 2)t2 + t4 n=0 185
Cộng hai phương trình trên vế theo vế, chúng ta được ∞ ∞ t(1 + xt − t2 ) 2 2n = xBn−1 (x )t + bn (x2 )t2n+1 (1 + xt − t2 )(1 − xt − t2 ) n=0 n=0 ∞ ∞ t = xBn−1 (x2 )t2n + bn (x2 )t2n+1 1 − xt − t2 n=0 n=0 ∞ ∞ ∞ fn (x)tn = xBn−1 (x2 )t2n + bn (x2 )t2n+1 n=0 n=0 n=0 Do đó f2n (x) = xBn−1 (x2 ) và f2n+1 (x) = bn (x2 ). Tính chất 23. (Liên hệ giữa Bn (x) và bn (x)) i) bm+n (x) = bm (x)Bn (x) − bm−1 (x)Bn−1 (x) ii) b2n (x) = Bn (x)bn (x) − Bn−1 (x)bn−1 (x) iii) b2n+1 (x) = Bn (x)bn+1 (x) − Bn−1 (x)bn (x) iv) (x + 2)b2n+1 (x) = Bn+1 (x)bn+1 (x) − Bn−1 (x)bn−1 (x) v) (x + 2)B2n (x) = Bn+1 (x)Bn (x) − Bn−1 (x)Bn−2 (x) vi) b2n (x) − b2n−1 (x) = b2 (x) − b2 (x) n n−1 Chứng minh. i) Sử dụng đẳng thức v) mục tính chất 21 chúng ta được bm+n (x) = Bm+n (x) − Bm+n−1 (x) =[Bm (x)Bn (x) − Bm−1 (x)Bn−1 ] − [Bm (x)Bn−1 (x) − Bm−1 (x)Bn−2 (x)] =Bm (x)[Bn (x) − Bn − 1(x)] − Bm−1 (x)[Bn−1 (x) − Bn−2 (x)] =Bm (x)bn (x) − Bm−1 (x)bn − 1(x) ii) Trong i) thay m bởi n chúng ta được b2n (x) = Bn (x)bn (x) − Bn−1 (x)bn − 1(x) iii) Áp dụng i) với m = n + 1. iv) Áp dụng hệ thức iii), (8), (9) chúng ta được (x + 2)b2n+1 (x) =(x + 2)Bn (x)bn+1 (x) − (x + 2)Bn−1 (x)bn(x) =bn+1 (x)[Bn+1 (x) + Bn−1 (x)] − Bn−1 (x)[bn+1 (x) + bn−1 (x)] =Bn+1 (x)bn+1 (x) − Bn−1 (x)bn−1 (x) v) Áp dụng iii) tính chất 21 và hệ thức (8) chúng ta có (x + 2)B2n (x) = B2n+1 (x) + B2n−1 (x) = =[Bn (x)Bn+1 (x) − Bn−1 (x)Bn (x)] + [Bn (x)Bn−1 (x) − Bn−1 (x)Bn−2 (x)] =Bn (x)Bn+1 (x) − Bn−1 (x)Bn−2 (x) 186
vi) Áp dụng ii) và hệ thức i) tính chất 21 chúng ta được b2n (x) − b2n−1 (x) = =[Bn (x)bn (x) − Bn−1 (x)bn−1 (x)] − [Bn−1 (x)bn (x) − Bn−2 (x)bn−1 (x)] =bn (x)[Bn (x) − Bn−1 (x)] − bn−1 (x)[Bn−1 (x) − Bn−2 (x)] =b2 (x) − b2 (x) n n−1 Tính chất 24. (Công thức về tổng của đa thức Morgan-Voyce) n i) x Bi (x) = bn+1 (x) − 1 0 n ii) bi (x) = Bn (x) 0 n 2 iii) B2i (x) = Bn (x) 0 n iv) B2i−1 (x) = Bn (x).Bn−1 (x) 1 n v) b2i (x) = Bn (x).bn (x) 0 n vi) b2i−1 (x) = Bn−1 (x).bn (x) 1 2n vii) (−1)i bi (x) = b2 (x) n 0 Hệ quả 8. Với n ≥ 0 chúng ta có i) F2n = Bn−1 (1) ii) F2n+1 = bn (1) Hệ quả 9. (Một số kết quả của số Fibonacci) i) Fm+n = Fm+2 Fn − Fm Fn−2 2 2 ii) F2n+2 = Fn+2 − Fn iii) F2n = (Fn+2 − Fn−2 )Fn 2 2 iv) 3F2n = Fn+2 − Fn−2 n v) F2i = F2n+1 − 1 0 n vi) F2i−1 = F2n 0 Ví dụ 5. Chúng ta có một số ví dụ sau 5 6+i B5 (x) = xi 5−i i=0 6 7 8 9 10 11 = + x+ x2 + x3 + x4 + x5 5 4 3 2 1 0 = 6 + 35x + 56x2 + 36x3 + 10x4 + x5 187