Tài liệu Số fibonacci dãy lucas

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THU TRANG SỐ FIBONACCI, DÃY LUCAS LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2014 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THU TRANG SỐ FIBONACCI, DÃY LUCAS LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên nghành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số 60.46.01.13 Người hướng dẫn khoa học PGS. TS. NÔNG QUỐC CHINH THÁI NGUYÊN - NĂM 2014 1 Mục lục Mở đầu 3 1 Các 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 4 4 4 6 7 8 9 12 19 28 khái niệm, tính chất cơ bản Dãy Lucas . . . . . . . . . . . . . . . . . . . . . . Các trường hợp đặc biệt của dãy Lucas . . . . . . Công thức Binet . . . . . . . . . . . . . . . . . . . Sự phát triển và tính toán số . . . . . . . . . . . . Các mối quan hệ đại số . . . . . . . . . . . . . . . Tính chất chia hết . . . . . . . . . . . . . . . . . . Một số tính chất của số Fibonacci và số Lucas . . Bổ sung các công thức của số Fibonacci, số Lucas . Số Fibonacci, số Lucas bình phương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Ứng dụng của số Fibonacci, dãy Lucas trong Toán phổ thông 33 Kết luận 44 Tài liệu tham khảo 45 2 Mở đầu Dãy số Fibonacci xuất hiện lần đầu tiên trong cuốn sách Liber Abacci năm 1202 khi Leonardo Fibonacci (hay còn có tên tên khác là Leonardo Pisano) là một nhà toán học người Ý giải quyết bài toán liên quan đến việc sinh nở của bầy thỏ. Số Fibonacci xuất hiện và biến hóa vô tận trong tự nhiên, với rất nhiều tính chất đẹp và ứng dụng quan trọng. Công trình quan trọng đầu tiên nghiên cứu về số Fibonacci là của nhà toán học François Édouard Anatole Lucas (1842–1891) được công bố trong bài seminal của ông năm 1878. Giống như dãy Fibonacci, mỗi số trong dãy Lucas bằng tổng của hai số liền trước nó. Dãy số gồm thương giữa hai số Lucas liền nhau sẽ hội tụ đến giới hạn bằng tỉ lệ vàng. Tuy vậy khác với dãy Fibonacci, hai số đầu tiên trong dãy Lucas là L0 = 2 và L1 = 1. Chính vì thế mà một số tính chất của số Lucas sẽ khác với số Fibonacci. Hiện nay tài liệu tiếng Việt về số Fibonacci, dãy Lucas và các ứng dụng của dãy Lucas trong Toán phổ thông chưa có nhiều và còn rời rạc. Vì vậy việc tìm hiểu sâu và giới thiệu số Fibonacci, dãy Lucas là rất cần thiết cho học tập và giảng dạy, ôn thi học sinh giỏi. Bản luận văn "Số Fibonacci, dãy Lucas" được tiến hành chủ yếu dựa vào các tài liệu tham khảo. Bản luận văn "Số Fibonacci, dãy Lucas" gồm có: mở đầu, hai chương nội dung, kết luận và tài liệu tham khảo. Chương 1 Các khái niệm, tính chất cơ bản Trong chương này trình bày định nghĩa số Fibonacci, dãy Lucas và các trường hợp đặc biệt của dãy Lucas. Một số tính chất của số Fibonacci và dãy Lucas. Công thức Binet, các mối quan hệ đại số, các công thức số học, tính chất chia hết và một số công thức của số Fibonacci và số Lucas. Chương 2 Ứng dụng của số Fibonacci, dãy Lucas trong Toán phổ thông 3 Trong chương này trình bày về một số bài toán ứng dụng của số Fibonacci, dãy Lucas trong chương trình toán phổ thông, ôn thi học sinh giỏi. Luận văn được hoàn thành dưới sự hướng dẫn và chỉ bảo tận tình của PGS.TS Nông Quốc Chinh - ĐH Khoa Học - Đại Học Thái Nguyên. Em xin bày tỏ lòng biết ơn sâu sắc đối với sự quan tâm, động viên và sự chỉ bảo hướng dẫn tận tình của thầy. Em xin trân trọng cảm ơn các Thầy Cô trong trường Đại Học Khoa Học - Đại Học Thái Nguyên, phòng Đào Tạo Trường Đại Học Khoa Học. Đồng thời tôi xin gửi lời cảm ơn tới tập thể lớp Cao Học Toán K6B, cùng gia đình tôi đã động viên giúp đỡ tôi trong quá trình học tập và làm luận văn này. Tuy nhiên do sự hiểu biết của bản thân và khuôn khổ luận văn thạc sĩ, nên chắc chắn rằng trong quá trình nghiên cứu không tránh khỏi những thiếu sót, tôi rất mong được sự chỉ dạy và đóng góp của các Thầy Cô và các bạn đồng nghiệp. Tác giả Nguyễn Thu Trang 4 Chương 1 Các khái niệm, tính chất cơ bản 1.1 Dãy Lucas Định nghĩa 1.1. Cho P, Q 6= 0, P, Q ∈ Z. Giả sử biệt thức D = P 2 − 4Q 6= 0. Đa thức X 2 − P X + Q được gọi là đa thức đặc trưng, có nghiệm √ √ P− D P+ D và β = . α= 2 2 Do D 6= 0 suy ra α 6= β, α + β = P, α.β = Q, (α − β)2 = D. Với mỗi n ≥ 0 xác định Un = Un (P, Q), Vn = Vn (P, Q) như sau: U0 = 0, U1 = 1, Un = P.Un−1 − Q.Un−2 (n ≥ 2), (1.1) V0 = 2, V1 = P, Vn = P.Vn−1 − Q.Vn−2 (n ≥ 2). (1.2) Dãy U = {Un (P, Q)}n≥0 , V = {Vn (P, Q)}n≥0 được gọi là dãy Lucas với tham số (P, Q). Dãy V = {Vn (P, Q)}n≥0 còn được gọi là dãy Lucas đồng hành với tham số (P, Q). 1.2 Các trường hợp đặc biệt của dãy Lucas Ta sẽ xem xét về trường hợp đặc biệt của dãy, những dãy mà có tầm quan trọng trong lịch sử. Đó là các dãy của số Fibonacci, số Lucas, số Pell và nhiều dãy số khác liên quan tới nhị thức. 5 Định nghĩa 1.2. Từ công thức (1.1) cho P = 1, Q = −1. Do đó D = 5. Ta có U0 = 0, U1 = 1, Un = Un−1 + Un−2 (n ≥ 2). Khi đó F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 (n ≥ 2). (1.3) Fn = Un (1, −1) được gọi là các số Fibonacci, Fn là số Fibonacci thứ n. Dãy số 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . . được gọi là dãy số Fibonacci. Định nghĩa 1.3. Từ công thức (1.2) cho P = 1, Q = −1. Do đó D = 5. Ta có V0 = 2, V1 = 1, Vn = Vn−1 + Vn−2 (n ≥ 2). Khi đó L0 = 2, L1 = 1, Ln = Ln−1 + Ln−2 (n ≥ 2). (1.4) Ln = Vn (1, −1) được gọi là các số Lucas, Ln là số Lucas thứ n. Dãy số 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, . . . được gọi là dãy số Lucas. Định nghĩa 1.4. Từ công thức (1.1) và (1.2) cho P = 2, Q = −1 do đó D = 8. Các số U0 = 0, U1 = 1, Un = Un (2, −1) = 2Un−1 + Un−2 (n ≥ 2), (1.5) U0 = 2, V1 = 2, Vn = Un (2, −1) = 2Vn−1 + Vn−2 (n ≥ 2) (1.6) là các số Pell và số Pell đồng hành. Un (2, −1) : 0, 1, 2, 5, 12, 29, 70, 169, ... Vn (2, −1) : 2, 2, 6, 14, 34, 82, 198, 478, ... Định nghĩa 1.5. Giả sử a, b ∈ Z sao cho a > b ≥ 1. Cho P = a + b, Q = a.b do đó D = (a − b)2 . Với mỗi n ≥ 0 giả sử Un = an − bn và Vn = an + bn . a−b 6 Sau đó dễ dàng xác định rằng: U0 = 0, U1 = 1, V0 = 2, V1 = a + b = P . Khi đó (Un )n≥0 , (Vn )n≥0 là dãy Lucas thứ nhất và thứ 2 với tham số (P, Q). Đặc biệt • Nếu b = 1 ta thu được dãy số có dạng Un = an − 1 và Vn = an + 1, a−1 với tham số là P = a + 1, Q = a. • Nếu a = 2 ta thu được dãy số có dạng Un = 2n − 1 và Vn = 2n + 1, với tham số là P = 3, Q = 2. 1.3 Công thức Binet Binet (1943) đã chỉ ra các biểu thức sau đây về nghiệm α, β của đa thức đặc trưng X 2 − P X + Q. Bổ đề 1.1. Công thức Binet αn − β n , Vn = αn + β n . α−β Lưu ý bằng công thức của Binet thì: Un = Un (−P, Q) = (−1)n−1 Un (P, Q), Vn (−P, Q) = (−1)n−1 Vn (P, Q). Vì vậy sau đây ta luôn giả định rằng P ≥ 1. Đặc biệt Khi P = 1, Q = −1 đa thức đặc trưng có dạng x2 − x − 1 có nghiệm là √ √ 1− 5 1+ 5 α= và β = . 2 2 Khi đó theo công thức của Binet thì Fn = αn − β n √ và Ln = αn + β n với n ≥ 1. 5 7 1.4 Sự phát triển và tính toán số α là căn của phần tử đơn vị. β (với α, β là nghiệm của đa thức X 2 − P X + Q). Khi đó dãy U (P, Q), V (P, Q) gọi là suy biến. α β P 2 − 2Q −1 Từ đó η + η = + = là một số nguyên đại số. β α Q   α β  Vì  +  ≤ 2 sau đó P 2 − 2Q = 0, ±Q, ±2Q suy ra P 2 = Q, 2Q, 3Q, 4Q. β α Nếu (P, Q) = 1 thì (P, Q) = (1, 1), (−1, 1), (2, 1), (−2, 1) và các dãy là Cho (P, Q) sao cho tỉ số η = U (1, 1) : 0, 1, 1, 0, −1, −1, 0, 1, 1, 0, −1, . . . U (−1, 1) : 0, 1, −1, 0, 1, −1, 0, 1, −1, 0, 1, . . . V (1, 1) : 2, 1, −1, −2, −1, 1, 2, 1, −1, −2, −1, . . . V (−1, 1) : 2, −1, −1, 2, −1, −1, 2, . . . U (2, 1) : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, . . . U (−2, 1) : 0, 1, −2, 3, −4, 5, −6, 7, −8, 9, −10, . . . V (2, 1) : 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, . . . V (−2, 1) : 2, −2, 2, −2, 2, −2, 2, −2, 2, −2, 2, . . . Nếu các dãy U (P, Q) , V (P, Q) là không suy biến thì |Un | , |Vn | tiến dần ra vô cùng (khi n → ∞). Nếu Q ≥ 2, (P, Q) = 1, D < 0 thì cứ mỗi ε > 0 và n đủ lớn: |Un | ≥ |β n |1−ε . Các tính toán  của Un ,Vn có thể được thực hiện như sau: P −Q Giả sử M = 1 0 . Khi đó với n ≥ 1,     Un n−1 1 0 Un−1 = M và  Vn Vn−1    2 = M n−1 P . Để tính toán bậc M k của ma trận M, phương pháp nhanh nhất là tính liên tục các bậc của M, M 2 , M 4 , ..., M 2e khi 2e ≤ k < 2e+1 . Điều này được thực hiện bằng cách liên tục bình phương các ma trận. 8 Tiếp theo, nếu sự khai triển của k là k = k0 + k1 .2 + k2 .22 + ... + ke .2e k k khi ki = 0 hoặc 1 thì M k = M k0 .(M 2 ) 1 ....(M 2e ) e . (chú ý các yếu tố chỉ thực sự xuất hiện khi ki = 1). Công thức của Binet cũng cho phép trong một số trường hợp tính toán nhanh Un , Vn . Nếu D ≥ 5 và |β| < 1 thì   n   α Un − √  < 1 (n ≥ 1)  D 2 1 và |Vn − αn | < ( với n sao cho n.(− log |β|) > log 2). 2 αn √ Do đó cUn là số nguyên gần nhất với và Vn là số nguyên gần nhất D với αn . Điều√này đặc biệt đúng với số Lucas√và số Fibonacci khi D = 5, α = 1+ 5 1− 5 ≈ 1, 616... (số vàng), β = ≈ −0, 616... 2 2 1.5 Các mối quan hệ đại số Các con số trong dãy Fibonacci, dãy Lucas thỏa mãn nhiều tính chất hữu ích và có nhiều ứng dụng. Các chứng minh các tính chất hầu như là các bài tập đơn giản, một số khác được chứng minh bằng cách áp dụng các công thức của Binet hoặc bằng phương pháp quy nạp. Tính chất 1.1. Mở rộng với các chỉ số âm: U−n = − V−n = 1 Un Qn 1 Vn Qn (∀n ≥ 1). (1.7) (∀n ≥ 1). (1.8) Tính chất 1.2. Các mối quan hệ bậc hai: Vn2 − DUn2 = 4Qn (∀n ∈ Z). (1.9) 9 Điều này cũng biểu diễn dưới dạng: 2 Un+1 − P Un+1 Un + QUn2 = Qn . (1.10) Tính chất 1.3. Các công thức chuyển đổi: DUn = Vn+1 − QVn−1 (∀n ∈ Z). (1.11) Vn = Un+1 − QUn−1 (∀n ∈ Z). (1.12) Tính chất 1.4. Cộng các chỉ số: Um+n = Um Vn − Qn Um−n (∀m, n ∈ Z) . (1.13) Vm+n = Vm Vn − Qn Vm−n = DUm Un + Qn Vm−n (∀m, n ∈ Z) . (1.14) Các công thức khác cùng loại là: 2Um+n = Um Vn + Un Vm (∀m, n ∈ Z) . (1.15) 2Qn Um−n = Um Vn − Un Vm (∀m, n ∈ Z) . (1.16) Tính chất 1.5. Phép nhân các chỉ số: 1.6 U2n = Um Vn (∀m, n ∈ Z) . (1.17) V2n = Vn2 − 2Qn (∀m, n ∈ Z) . (1.18)

U3n = Un Vn2 − Qn = Un DUn2 + 3Qn
V3n = Vn Vn2 − 3Qn (∀m, n ∈ Z) . (1.19) (∀m, n ∈ Z) . (1.20) Tính chất chia hết Tính chất 1.6. Nếu Um 6= 1 thì Um |Un khi và chỉ khi m|n. Nếu Vm 6= 1 thì Vm |Vn khi và chỉ khi m|n và n/m là lẻ. Trường hợp đặc biệt. Đối với dãy của số Fibonacci và số Lucas. Định lí 1.1. Fm |Fmn . Chứng minh Ta chứng minh bằng phương pháp quy nạp toán học. Với n = 1 mệnh đề luôn đúng. 10 Giả sử mệnh đề đúng với mọi số nguyên n = k với k ≥ 1. Nghĩa là ta có Fm |Fmi với mọi i với 1 ≤ i ≤ k. Để chứng minh rằng Fm |Fm(k+1) , ta áp dụng mệnh đề Fr+s = Fr−1 Fs + Fr Fs+1 . Khi đó Fm(k+1) = Fmk+m = Fmk−1 Fm + Fmk Fm+1 . Vì Fm |Fmk , do giả thiết quy nạp ta suy ra rằng Fm |Fm(k+1) . Bằng phương pháp quy nạp kết quả đúng với mọi số nguyên n ≥ 1. Định lý được chứng minh. Ví dụ F6 = 8 và F24 = 46368. Vì 6|24 nên 8|46368. Bổ đề 1.2. Fn = Fn−m+1 Fm + Fn−m Fm−1 , với 1 ≤ m ≤ n. Định lí 1.2. Nếu Fm |Fn thì m|n. Chứng minh Bằng thuật toán phân chia n = qm + r với 0 ≤ r < m. Giả sử Fm |Fn . Theo định lý 1.1 và bổ đề 1.2 ta có Fm |Fn−m Fm−1 . Nhưng (Fm , Fm−1 ) = 1, vì vậy Fm |Fn−m . Tương tự Fm |Fn−2m , tiếp tục như vậy Fm |Fn−qm . Có nghĩa là Fm |Fr . Đây là điều không thể trừ khi r = 0, n = qm. Do đó Fm |Fn thì m|n. Định lý được chứng minh. Định lí 1.3. Fm |Fn khi và chỉ khi m|n. Hệ quả 1.1. Nếu (m, n) = 1 thì Fm Fn |Fmn . Chứng minh Áp dụng định lý 1.1 Fm |Fmn và Fn |Fmn do đó [Fm , Fn ] |Fmn . Nhưng (Fm , Fn ) = F(m,n) = F1 = 1, suy ra [Fm , Fn ] = Fm Fn . Vậy Fm Fn |Fmn . Ví dụ (4, 7) = 1, F4 = 3, F7 = 13, F28 = 317811. Chúng ta có thể thấy rằng 3.13|317811, nghĩa là F4 F7 |F28 . 11 Bổ đề 1.3. (Fqn−1 , Fn ) = 1. Chứng minh Giả sử d = (Fqn−1 , Fn ) thì d|Fqn−1 và d|Fn . Vì Fn |Fqn theo định lý 1.1 thì d|Fqn . Do đó Fn |Fqn−1 và d|Fqn . Nhưng (Fqn−1 , Fqn ) = 1 theo hệ quả 1.3 thì d|1, do đó d = 1. Vậy (Fqn−1 , Fn ) = 1. Bổ đề 1.4. Giả sử m = qn + r thì (Fm , Fn ) = (Fn , Fr ). Chứng minh (Fm , Fn ) = (Fqn+r , Fn ) = (Fqn−1 Fr + Fqn Fr+1 Fn , Fn ) = (Fqn−1 Fr , Fn ) = (Fr , Fn ) = (Fn , Fr ) . Định lí 1.4. (Fm , Fn ) = F(m,n) . Chứng minh Giả sử m ≥ n. Áp dụng thuật toán Euclid đối với m, n ta có các phương trình như sau: m = q0 n + r1 0 ≤ r1 < n n = q1 r1 + r2 0 ≤ r2 < r1 r1 = q2 r2 + r3 0 ≤ r3 < r2 ... rn−2 = qn−1 rn−1 + rn 0 ≤ rn < rn−1 rn−1 = qn rn + 0. Theo bổ đề 1.4 (Fm , Fn ) = (Fn , Fr1 ) = (Fr1 , Fr2 ) = ... = Frn−1 , Frn
12 Nhưng rn |rn−1 , vì vậy Frn |Frn−1 theo định lý 1.1. Do đó
Frn−1 , Frn = Frn . Suy ra (Fm , Fn ) = Frn . Bằng thuật toán Euclid rn = (m, n). Do vậy (Fm , Fn ) = F(m,n) . Định lý được chứng minh. Ví dụ (F12 , F18 ) = F(12,18) = F6 = 8. Có nghĩa là (144, 2584) = 8. Định lí 1.5. Lm |Fn khi và chỉ khi 2m|n với m ≥ 2. Ví dụ 10|20, vì L5 |F20 . Có nghĩa là 11|6765. Đối với các tính chất tiếp theo ta luôn giả sử (P, Q) = 1. Tính chất 1.7. (Um , Un ) = Ud khi d = (m, n). Tính chất 1.8. ( n m và là lẻ, d d 1 hoặc 2 trong các trường hợp còn lại ( n m là chẵn và là lẻ, d d 1 hoặc 2 trong các trường hợp còn lại (Vm , Vn ) = Vd nếu khi d = (m, n). Tính chất 1.9. (Um , Vn ) = Vd nếu khi d = (m, n). Tính chất 1.10. Nếu n ≥ 1 thì (Un , Q) = 1 và (Vn , Q) = 1. 1.7 Một số tính chất của số Fibonacci và số Lucas Định lí 1.6. (Lucas,1876) n X i=1 Fi = Fn+2 − 1. (1.21) 13 Chứng minh Ta có F1 = F3 − F2 F2 = F4 − F3 F3 = F5 − F4 ... Fn−1 = Fn+1 − Fn Fn = Fn+2 − Fn+1 . Cộng các vế ta được n X Fi = Fn+2 − F2 = Fn+2 − 1. i=1 Ngoài ra chúng ta còn có thể dùng phương pháp quy nạp toán học. Ta thấy F1 = F3 − F2 = F3 − 1 = 1, công thức đúng với n = 1. Giả sử công thức đúng với số nguyên dương bất kì k > 1. Khi đó k X Fi = Fk+2 − 1( giả thiết quy nạp) i=1 thì k+1 X i=1 Fi = k X Fi + Fk+1 i=1 = Fk+2 − 1 + Fk+1 = (Fk+2 + Fk+1 ) − 1 = Fk+3 − 1. Theo phương pháp quy nạp toán học công thức đúng với mọi số nguyên dương n. Định lý được chứng minh. 20 P Ví dụ Fi = F22 − 1 = 17711 − 1 = 17710. i=1 Bạn có thể kiểm tra bởi máy tính. 14 Ví dụ 1.1. Chứng minh rằng k X Fi+j + Fi+1 = Fi+k+2 . j=0 Lời giải. k X Fi+j + Fi+1 = j=0 i+k X Fr − i−1 X 1 Fr + Fi+1 1 = (Fi+k+2 − 1) − (Fi+1 − 1) + Fi+1 theo (1.21) = Fi+k+2 . Định lí 1.7. (Lucas,1876) n X F2i−1 = F2n . (1.22) i=1 Chứng minh Ta có F1 = F2 − F0 F3 = F4 − F2 F5 = F6 − F4 ... F2n−3 = F2n−2 − F2n−4 F2n−1 = F2n − F2n−2 . Cộng các vế ta được n X F2i−1 = F2n − F0 = F2n . i=1 Định lý được chứng minh. Ngoài ra chúng ta còn có thể sử dụng phương pháp quy nạp để chứng minh. 10 P Ví dụ F2i−1 = F20 = 6765. i=1 15 Hệ quả 1.2. (Lucas,1876) n X F2i = F2n+1 − 1. (1.23) i=1 Chứng minh Ta có n X F2i = 2n X 1 i=1 Fi − n X F2i−1 1 = (F2n+2 − 1) − F2n = (F2n+2 − F2n ) − 1 = F2n+1 − 1. Định lí 1.8. Công thức Cassini Fn−1 Fn+1 − Fn2 = (−1)n với n ≥ 1. (1.24) Chứng minh Ta chứng minh bằng phương pháp quy nạp toán học. Ta có n = 1 : F0 F2 − F12 = 0.1 − 1 = −1 = (−1)1 . Công thức đúng với n = 1. Giả sử công thức đúng với số nguyên dương bất kì n = k với k > 1, Fk−1 Fk+1 − Fk2 = (−1)k ( giả thiết quy nạp). Khi đó 2 2 Fk Fk+2 − Fk+1 = (Fk+1 − Fk−1 ) (Fk + Fk+1 ) − Fk+1 2 2 = Fk Fk+1 + Fk+1 − Fk Fk−1 − Fk−1 Fk+1 − Fk+1 = Fk Fk+1 − Fk Fk−1 − Fk2 − (−1)k (theo giả thiết quy nạp) = Fk Fk+1 − Fk (Fk−1 + Fk ) + (−1)k+1 = Fk Fk+1 − Fk Fk+1 + (−1)k+1 = (−1)k+1 . Do đó công thức đúng với n = k + 1. Vậy bằng phương pháp quy nạp công thức đúng với ∀n ≥ 1. Định lý được chứng minh. 16 Hệ quả 1.3. Bất kì hai số Fibonacci cạnh nhau nào cũng nguyên tố cùng nhau. Nghĩa là (Fn+1 , Fn ) = 1, ∀n. Chứng minh Giả sử p = (Fn+1 , Fn ). Theo công thức Cassini thì p| ± 1. Điều này là mâu thuẫn. Do đó (Fn+1 , Fn ) = 1, ∀n. Bổ đề 1.5. Ln = Fn+1 + Fn−1 với n ≥ 1. (1.25) Chứng minh Áp dụng công thức Binet ta có: Fn−1 + Fn+1 = 2Fn+1 − Fn  n+1   n  α − β n+1 α − βn √ √ =2 − 5 5 n n α (2α − 1) + β (1 − 2β) √ = √ n √ n5 5α + 5β √ = 5 n n = α + β = Ln . Từ công thức Cassini Fn−1 Fn+1 − Fn2 = (−1)n . Ta được phương trình Diophantine x2 + xy − y 2 = ±1 có vô số nghiệm x = Fn−1 và y = Fn . Năm 1972, Ira Gessel đã có kết quả rất thú vị. Định lí 1.9. Số nguyên dương n là số Fibonacci nếu và chỉ nếu 5n2 ± 4 là số chính phương. Chứng minh 17 Ta có Fr2 + (−1)r = Fr−1 Fr+1 theo (1.24). Lr = Fr+1 + Fr−1 theo (1.25).   L2r − 4 Fr2 + (−1)r = (Fr+1 + Fr−1 )2 − 4Fr−1 Fr+1 . = (Fr+1 − Fr−1 )2 = Fr2 . L2r = 5Fr2 + 4(−1)r . Do đó nếu n là số Fibonacci thì 5n2 ± 4 là số chính phương. Ngược lại, giả sử 5n2 ± 4 = m2 là số chính phương. Khi đó m2 − 5n2 = ±4 √ √ m+n 5 m−n 5 . = ±1. 2 2 Vì m và n có tính chất chẵn lẻ giống nhau ! (cả hai cùng chẵn hoặc cùng lẻ), √ ! √ m+n 5 m−n 5 nên cả hai số và là các số nguyên trong trường 2 2 Q o √  n √ 5 = x + y 5|x, y ∈ Q . Vì vậy tích của chúng là ±1. Chúng có thể là phần tử đơn vị trong trường. √  5 là có dạng Nhưng chỉ có một phần tử đơn vị nguyên trong trường Q ±α±i . Do đó √

 m+n 5 1 i = αi = α + β i + αi − β i 2 2 √ L i + Fi 5 = . 2 Vì vậy n = Fi là một số Fibonacci. Định lý được chứng minh. Ví dụ 1.2. Chứng minh rằng n P 1 Fi2 = Fn Fn+1 với mọi n nguyên dương. 18 Chứng minh Bằng phương pháp quy nạp toán học. 1 P Fi2 = F12 = 1 = 1.1 = F1 F2 = V P . Công thức đúng với Khi n = 1, V T = i n = 1. Giả sử công thức đúng với số nguyên dương bất kì n = k với k > 1: k X Fi2 = Fk Fk+1 . 1 Khi đó k+1 X 1 Fi2 = k X 2 Fi2 + Fk+1 1 2 = Fk Fk+1 + Fk+1 = Fk+1 (Fk + Fk+1 ) = Fk+1 Fk+2 . Do đó công thức đúng khi n = k + 1. Vậy công thức đúng với mọi số nguyên dương n. Ví dụ 25 X Fi2 = F25 F26 = 75025.121393 = 9107509825. 1 Ngoài ra chúng ta còn mở rộng các kết quả cho số Lucas. n X 1 n X Li = Ln+2 − 3. (1.26) L2i−1 = L2n − 2. (1.27) L2i = L2n+1 − 1. (1.28) 1 n X 1 Ln−1 Ln+1 − L2n = 5(−1)n−1 . n X L2i = Ln Ln+1 − 2. 1 (1.29) (1.30)