Tài liệu Về dãy k fibonacci

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ THU HÀ VỀ DÃY K-FIBONACCI Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NÔNG QUỐC CHINH THÁI NGUYÊN - 2019 i Mục lục Lời cảm ơn 1 Mở đầu 2 1 Một số kiến thức chuẩn bị 1.1 Ước chung lớn nhất . . . . . . . . . . . . . . . . . . . . . . . 1.2 Dãy Fibonacci, hàm sinh, công thức Binet . . . . . . . . . . . 4 4 5 2 Dãy 2.1 2.2 2.3 k-Fibonacci Hàm sinh và công thức Binet của dãy k-Fibonacci . . . . . . . Một số tính chất của dãy k-Fibonacci . . . . . . . . . . . . . Một số đồng nhất thức của dãy k-Fibonacci . . . . . . . . . . 10 10 12 19 3 Một số ứng dụng của dãy k-Fibonacci 3.1 Tam giác chuẩn hóa và các hàm phức . . . . . . . . . . . . . . 3.2 Một số ứng dụng của ma trận (Rk−1 .L)n . . . . . . . . . . . . 21 21 25 Kết luận 29 Tài liệu tham khảo 30 1 Lời cảm ơn Trước hết, tôi xin gửi lời biết ơn chân thành đến PGS. TS. Nông Quốc Chinh đã hướng dẫn tôi hoàn thành bản luận văn này. Khi bắt đầu nhận đề tài thực sự tôi cảm nhận đề tài mang nhiều nội dung mới mẻ. Hơn nữa với vốn kiến thức ít ỏi cùng với kinh nghiệm làm đề tài không nhiều nên tôi chưa thực sự tự tin để tiếp cận đề tài. Mặc dù rất bận rộn trong công việc nhưng Thầy vẫn dành nhiều thời gian và tâm huyết trong việc hướng dẫn, động viên khuyến khích tôi trong suốt thời gian tôi thực hiện đề tài. Trong quá trình tiếp cận đề tài đến quá trình hoàn thiện luận văn Thầy luôn tận tình chỉ bảo và tạo điều kiện tốt nhất nhất cho tôi hoàn thành luận văn. Cho đến bây giờ luận văn thạc sĩ của tôi đã được hoàn thành, xin cảm ơn Thầy đã đôn đốc nhắc nhở tôi. Tôi xin trân trọng cảm ơn Ban Giám hiệu, Khoa Toán - Tin và Phòng Đào tạo của trường Đại học Khoa học - Đại học Thái Nguyên. Tôi xin trân trọng cảm ơn các Thầy, Cô đã tận tình truyền đạt những kiến thức quý báu cũng như tạo mọi điều kiện thuận lợi nhất để tôi hoàn thành luận văn này. Tôi xin trân trọng cảm ơn Ban giám hiệu, các thầy cô giáo trường THPT Ngô Thì Nhậm - Ninh Bình nơi tôi công tác đã tạo điều kiện giúp đỡ tôi hoàn thành công việc chuyên môn tại nhà trường để tôi hoàn thành chương trình học tập cao học. Cuối cùng, tôi xin chân thành bày tỏ lòng biết ơn đến gia đình, bạn bè, những người không ngừng động viên, hỗ trợ tạo mọi điều kiện tốt nhất cho tôi trong suốt quá trình học tập và thực hiện luận văn. Thái Nguyên, tháng 10 năm 2019 Tác giả Nguyễn Thị Thu Hà 2 Mở đầu Dãy Fibonacci được đưa ra và nghiên cứu từ những năm 1202. Nó đóng vai trò quan trong trong những vấn đề khác nhau của Toán học và thu hút sự quan tâm của rất nhiều nhà Toán học. Mặc dù đã được biết đến từ rất lâu đời nhưng còn khá nhiều các vấn đề liên quan đến dãy Fibonacci và các mở rộng của nó còn chưa được nghiên cứu. Vì thế người ta luôn tìm cách mở rộng dãy Fibonacci để ứng dụng vào nghiên cứu các bài toán cụ thể. Một trong các hướng mà rất nhiều nhà toán học quan tâm đó là cách xây dựng các dãy số có tính chất đẹp tương tự như dãy Fibonacci hoặc là xây dựng các dãy số mở rộng của dãy Fibonacci. Năm 2007, Falcon và Plaza đã đưa ra định nghĩa về dãy k-Fibonacci để ứng dụng vào nghiên cứu bài toán phân vùng 4 tam giác có cạnh lớn nhất. Bài toán phân vùng 4 tam giác cạnh dài nhất (viết ngắn gọn là 4TLE) được xây dựng bằng cách nối trung điểm của cạnh dài nhất với đỉnh đối diện và đến điểm giữa của hai cạnh còn lại. Bài toán này được đưa ra và nghiên cứu bởi tác giả M.C. Rivara vào năm 1996. Gần đây có rất nhiều kết quả liên quan đến dãy k-Fibonacci. Khi k = 1 thì dãy k-Fibonacci chính là dãy Fibonacci. Hơn nữa khi k = 2 thì dãy k-Fibonacci chính là dãy Pell. Do đó với những kết quả đã biết về dãy Fibonacci và dãy Pell chúng ta có thể mở rộng cho dãy k-Fibonacci. Ngược lại, từ các kết quả cho dãy k-Fibonacci chúng ta sẽ có ngay các kết quả tương ứng cho các dãy Fibonacci và dãy Pell. Mục tiêu của luận văn là trình bày các kết quả về dãy k-Fibonacci và ứng dụng của nó. Các kết quả chính trong luận văn được viết dựa theo các tài liệu [1], [2], và [3]. Nội dung chính của luận văn được trình bày trong ba chương. Chương 1 dành để trình bày một số tính chất của ước chung lớn nhất và các tính chất quan trọng của dãy Fibonacci. Đặc biệt là công thức Binet, nó được dùng trong rất nhiều các chứng minh sau này. 3 Chương 2 dành để trình bày về dãy k-Fibonacci. Trong chương này chúng tôi trình bày về hàm sinh, công thức Binet và các tính chất của dãy kFibonacci. Đặc biệt là các công thức đồng nhất của dãy k-Fibonacci. Các kết quả trong chương này được viết theo tài liệu [2] và [3]. Chương 3 trình bày về một số ứng dụng cụ thể của dãy k-Fibonacci. Đặc biệt là mối liên hệ với bài toán phân vùng 4 tam giác có cạnh lớn nhất. Hơn nữa từ mối quan hệ với dạng ma trận của các ánh xạ phức Rk−1 .L chúng ta thu được một số kết quả quen biết về dãy k-Fibonacci. 4 Chương 1 Một số kiến thức chuẩn bị 1.1 Ước chung lớn nhất Mục đích của tiết này là trình bày một số tính chất quan trọng về ước chung lớn nhất của một dãy các số nguyên dương, được dùng cho các chứng minh ở các phần sau. Các kết quả trong tiết này được viết theo tài liệu [1]. Để thuận tiện cho trình bày ta ký hiệu ước chung lớn nhất của một dãy các số nguyên dương a1 , . . . , at , t ≥ 2 là gcd(a1 , . . . , at ). Bổ đề 1.1.1. Cho m, n, q là các số nguyên dương. Giả sử n|q. Khi đó, ta có gcd (m + q, n) = gcd (m, n) . Chứng minh. Theo giả thiết n|q nên q = rn, với r là số nguyên dương nào đó. Đặt g = gcd (m + rn, n) thì ta có g |(m + rn) và g |n. Do đó tồn tại các số nguyên dương r1 , r2 sao cho n = r1 g và m + rn = r2 g. Do đó m = r2 g − rn = (r2 − r1 r) g, nghĩa là g |m. Lấy tùy ý số tự nhiên d ∈ N sao cho d |m và d |n. Suy ra d |(m + rn) . Kết hợp với g = gcd (m + rn, n) ta suy ra d |g. Vậy g |gcd (m, n) . Vì thế gcd (m + q, n) = gcd (m, n) . Bổ đề 1.1.2. Cho m, n là các số nguyên dương. Khi đó n|m khi và chỉ khi gcd(m, n) = n. Chứng minh. Giả sử n|m ta cần chứng minh gcd (m, n) = n. Vì n|m nên tồn tại số nguyên dương q sao cho m = qn. Suy ra gcd (m, n) = gcd (qn, n) . Ta sẽ chứng minh khẳng định trên bằng quy nạp theo q . Với q = 1, ta có gcd (n, n) = n. 5 Giả sử đẳng thức đúng với q > 1, ta chứng minh đẳng thức đúng với q + 1. Thật vậy theo Bổ đề 1.1.1 và giả thiết quy nạp, ta có gcd (qn + n, n) = gcd (qn, n) = n. Vậy điều kiện cần được chứng minh. Ngược lại, giả sử gcd (m, n) = n ta cần chứng minh n|m. Thật vậy, vì gcd (m, n) = n nên tồn tại số nguyên dương q sao cho m = qn, nghĩa là n |m . Vậy điều kiện đủ được chứng minh. Bổ đề 1.1.3. Cho m, n, q là các số nguyên dương. Khi đó, nếu gcd (m, n) = 1 thì gcd (m, nq) = gcd (m, q) . Chứng minh. Giả sử g = gcd(m, q) và g 0 = gcd(m, nq). Suy ra g 0 |m và  0 g 0 |nq ; g|m và g|q. Vì g|q nên g|nq . Suy ra g g . Từ các điều kiện 0 gcd(m, n) = 1, g |m và g 0 |nq, 0 ta suy ra g 0 |q. Mặt khác g = gcd(m, q), do đó g 0 |g. Vậy g = g . 1.2 Dãy Fibonacci, hàm sinh, công thức Binet Định nghĩa 1.2.1. Dãy số Fibonacci, ký hiệu (Fn )n∈N được định nghĩa bởi công thức truy hồi ( F0 = 0, F1 = 1, Fn+1 = Fn + Fn−1 (n ≥ 1), ở đây Fn là số hạng thứ n của dãy số Fibonacci. Từ hệ thức truy hồi của dãy Fibonacci ta có Fn+2 − Fn+1 − Fn = 0, với mọi n ≥ 0. Do đó ta có phương trình x2 − x − 1 = 0 hay x2 = x + 1. Nhân hai vế của phương trình với xn−1 ta được xn+1 = xn + xn−1 . (1.1) 6 Rõ ràng nếu ϕ là một nghiệm của phương trình (1.1) thì 1 − ϕ cũng là một nghiệm của phương trình (1.1). Do đó ϕn+1 = ϕn + ϕn−1 và (1 − ϕ)n+1 = (1 − ϕ)n + (1 − ϕ)n−1 . Với mỗi cặp số thực a, b, ta đặt Fa,b (n) = aϕn + b(1 − ϕ)n . Khi đó tất cả các hàm này thỏa mãn hệ thức truy hồi Fibonacci. Định nghĩa 1.2.2. Các hàm Fa,b (n) = aϕn + b(1 − ϕ)n được gọi là hàm sinh. Trong Định nghĩa dãy Fibonacci, các số hạng của dãy được cho dưới dạng truy hồi nên khi sử dụng dãy đôi khi gặp khó khăn. Mệnh đề sau đây cho ta công thức tường minh của dãy Fibonacci và được gọi là công thức Binet. Công thức Binet được sử dụng hữu hiệu trong các chứng minh sau này. Mệnh đề 1.2.3. Dãy số Fibonacci được cho bởi công thức  √ n  √ n 1+ 5 1+ 5 − 1− 2 2 √ Fn = . 5 Mệnh đề 1.2.4. Cho n là một số nguyên dương. Khi đó, ta có gcd(Fn , Fn+1 ) = 1. Chứng minh. Giả sử g = gcd(Fn , Fn+1 ) 6= 1. Khi đó, ta có g |Fn và g |Fn+1 . Theo công thức truy hồi của dãy Fibonacci Fn+1 − Fn = Fn−1 , (n ≥ 1). Suy ra g|Fn−1 . Lăp lại quá trình ta có g|1, điều này mâu thuẫn với giả thiết. Vậy gcd(Fn , Fn+1 ) = 1. Mệnh đề 1.2.5. Cho m, n là các số nguyên dương. Khi đó, ta có Fm+n = Fm−1 .Fn + Fm .Fn+1 . (1.2) 7 Chứng minh. Ta sẽ chứng minh khẳng định trong bổ đề bằng quy nạp theo n. Với n = 1 đẳng thức (1.2) trở thành Fm+1 = Fm−1 .F1 + Fm .F2 . Ta có F1 = F2 = 1 nên đẳng thức cần chứng minh thành Fm+1 = Fm−1 +Fm . Đẳng thức này luôn đúng theo định nghĩa của dãy Fibonacci. Giả sử đẳng thức (1.2) đúng với n = k, nghĩa là Fm+k = Fm−1 .Fk + Fm .Fk+1 . Ta cần chứng minh đẳng thức đúng với n = k + 1, nghĩa là Fm+k+1 = Fm−1 .Fk+1 + Fm .Fk+2 . Ta có Fm+k+1 = Fm+k−1 + Fm+k = Fm−1 .Fk−1 + Fm .Fk + Fm−1 .Fk + Fm .Fk+1 = Fm−1 (Fk + Fk−1 ) + Fm (Fk + Fk+1 ) = Fm−1 .Fk+1 + Fm .Fk+2 . Vậy theo quy nạp ta có điều phải chứng minh. Kết quả sau là hệ quả trực tiếp của Mệnh đề 1.2.5. Hệ quả 1.2.6. Cho n là số nguyên dương thỏa mãn n ≥ 1. Khi đó F2n = Fn (Fn−1 + Fn+1 ). Chứng minh. Áp dụng Bổ đề 1.2.5 ta có Fn+m = Fn−1 .Fm + Fn .Fm+1 . Thay m = n ta được F2n = Fn−1 .Fn + Fn .Fn+1 = Fn (Fn−1 + Fn+1 ). Bổ đề 1.2.7. Cho m, n là hai số nguyên dương sao cho m|n. Khi đó, ta có Fm |Fn . 8 Chứng minh. Vì m |n nên tồn tại số nguyên dương q sao cho n = qm. Ta sẽ chứng minh khẳng định trong bổ đề bằng quy nạp theo q . Với q = 1, ta có n = m, do đó Fm |Fm . Giả sử khẳng định trong bổ đề là đúng với q > 1. Ta chứng minh đẳng thức đúng với q + 1. Theo Mệnh đề 1.2.5, ta có Fqm+m = Fqm−1 Fm + Fqm Fm+1 . Rõ ràng Fm |Fqm−1 Fm . Theo giả thiết quy nạp Fm |Fqm . Do đó Fm |Fqm Fm+1 . Vậy Fm |(Fqm−1 Fm + Fqm Fm+1 ) = Fqm+m . Bổ đề 1.2.7 cho ta một hệ quả trực tiếp sau. Hệ quả 1.2.8. Nếu n là một hợp số khác 4 thì Fn là một hợp số. Chứng minh. Vì n là hợp số khác 4 nên tồn tại số nguyên dương m ≥ 2 sao cho m|n. Theo Bổ đề 1.2.7 ta có Fm |Fn , nghĩa là Fn là hợp số. Mệnh đề 1.2.9. Cho hai số nguyên dương m, n. Khi đó gcd(Fm , Fn ) = Fgcd(m,n) . Chứng minh. Sử dụng phép chia với dư, tồn tại các số nguyên dương q0 , r1 sao cho m = nq0 + r1 , 0 ≤ r1 ≤ n. Kết hợp với Bổ đề 1.2.5, ta có gcd (Fm , Fn ) = gcd (Fnq0 −1 Fr1 + Fnq0 Fr1 +1 , Fn ) . Theo Bổ đề 1.2.7 ta có Fn |Fnq0 . Do đó theo Bổ đề 1.1.1 ta có gcd(Fm , Fn ) = gcd(Fnq0 −1 Fr1 , Fn ). Mặt khác gcd (Fm , Fn ) = gcd (Fr1 , Fn ) . Tiếp tục quá trình cho đến n cùng với thuật toán Euclide, ta nhận được gcd(Fm , Fn ) = gcd(Frk−1 , Frk ), 9 với rk |rk−1 và rk = gcd(m, n). Vì rk |rk−1 nên theo Bổ đề 1.2.7 ta có Frk |Frk−1 . Theo Bổ đề 1.1.2 suy ra
gcd Frk−1 , Frk = Frk . Vậy gcd(Fm , Fn ) = Fgcd(m,n) . Kết quả sau là hệ quả trực tiếp của Mệnh đề 1.2.9. Hệ quả 1.2.10. Nếu Fm |Fn thì m|n với mọi n, m ≥ 1. Chứng minh. Vì Fm |Fn nên gcd(Fm , Fn ) = Fm . Theo Mệnh đề 1.2.9 ta có gcd(Fm , Fn ) = Fgcd(m,n) . Do đó gcd(m, n) = m, nghĩa là m|n. Mệnh đề 1.2.11. Cho n là số nguyên không âm. Khi đó 2 F2n+1 = Fn2 + Fn+1 . Chứng minh. Mệnh đề được chứng minh bằng quy nạp theo n. Với n = 0, ta có F1 = 1 = 0 + 1 = F02 + F12 . Giả sử khẳng định trong mệnh đề đúng với n > 0, tức là 2 F2n+1 = Fn2 + Fn+1 . Ta cần chứng minh 2 2 F2n+3 = Fn+1 + Fn+2 . Theo định nghĩa dãy Fibonacci, Hệ quả 1.2.6 và giả thiết quy nạp, ta có 2 2 Fn+1 + Fn+2 = (Fn−1 + Fn )2 + (Fn + Fn+1 )2 2 2 = Fn−1 + 2Fn−1 Fn + Fn2 + Fn2 + 2Fn Fn+1 + Fn+1 2 2 = Fn−1 + Fn2 + 2Fn (Fn−1 + Fn+1 ) + Fn2 + Fn+1 = F2n−1 + 2F2n + F2n+1 = F2n+1 + F2n+2 = F2n+3 . 10 Chương 2 Dãy k-Fibonacci 2.1 Hàm sinh và công thức Binet của dãy k-Fibonacci Mục đích của tiết này là trình bày định nghĩa, hàm sinh và công thức Binet của dãy k-Fibonacci. Các định nghĩa và tính chất của tiết này được viết theo tài liệu [2]. Trong suốt tiết này ta luôn xét k là một số thực dương. Định nghĩa 2.1.1. Dãy k-Fibonacci được định nghĩa bởi công thức truy hồi  F = 0,   k,0 Fk,1 = 1,   Fk,n+1 = kFk,n + Fk,n−1 , (n ≥ 1). Từ định nghĩa của dãy k-Fibonacci ta có phương trình đặc trưng r2 = kr + 1. Các nghiệm của phương trình đặc trưng là √ k ± k2 + 4 r1,2 = . 2 Rõ ràng với k > 0 thì r2 < 0 < r1 , |r2 | < r1 . Hơn nữa r1 +r2 = k, r1 .r2 = −1 và √ r1 − r2 = k 2 + 4. Trong toàn bộ luận văn ta sẽ ký hiệu Fk,n là số k-Fibonacci thứ n và r1 , r2 là các nghiệm của phương trình đặc trưng. Từ định nghĩa của dãy k-Fibonacci, với k = 1 thì dãy này chính là dãy Fibonacci. Do đó có thể nói khái niệm dãy k-Fibonacci là một mở rộng của 11 khái niệm dãy Fibonacci. Vì thế nhiều tác giả đã tìm cách nghiên cứu các tính chất tương tự cho dãy k-Fibonacci. Một trong những tính chất này là công thức Binet. Mệnh đề 2.1.2 (Công thức Binet). Số k-Fibonacci thứ n, ký hiệu là Fk,n được xác định bởi công thức r1n − r2n . Fk,n = r1 − r2 Chứng minh. Ta sẽ chứng minh khẳng định trong mệnh đề bằng quy nạp theo n. Với n = 0, ta có r10 − r20 = = 0. r1 − r2 Fk,0 Giả sử khẳng định trong mệnh đề đúng với mọi số nguyên i thỏa mãn 0 ≤ i ≤ l + 1. Khi đó 1 Fk,i = (r1i − r2i ). r1 − r2 r1l+1 − r2l+1 . Theo định nghĩa của dãy k-Fibonacci, Ta cần chứng minh Fk,l+1 = r1 − r2 ta có Fk,l+1 = kFk,l + Fk,l−1 . Từ giả thiết quy nạp kFk,l + Fk,l−1 r1l − r2l r1l−1 − r2l−1 =k + . r1 − r2 r1 − r2 Do r1 + r2 = k, nên suy ra kFk,l + Fk,l−1
(r1 + r2 ) r1l − r2l r1l−1 − r2l−1 = + r1 − r2 r1 − r2 l+1 l+1 l r1 − r2 − r1 r2 + r2 r1l + r1l−1 − r2l−1 = . r1 − r2 Mặt khác r1 r2 = −1, nên suy ra kFk,l + Fk,l−1 r1l+1 − r2l+1 = = Fk,l+1 . r1 − r2 Theo Định nghĩa dãy k-Fibonacci và tính chất của r1 , r2 ta có Fk,l+1 = kFk,l+1 + Fk,l r1l+1 − r2l+1 = . r1 − r2 12 2.2 Một số tính chất của dãy k-Fibonacci Mục đích của tiết này là trình bày lại các tính chất của dãy k-Fibonacci. Các kết quả trong tiết này được viết dựa theo tài liệu [2]. Bổ đề 2.2.1. Cho n là một số nguyên thỏa mãn n ≥ 1. Khi đó r1n+2 = k.r1n+1 + r1n . r2n+2 = k.r2n+1 + r2n . Chứng minh. Vì r1 , r2 là nghiệm của phương trình đặc trưng nên r12 = kr1 + 1. r22 = kr2 + 1. Nhân cả 2 vế của các đẳng thức này với r1n và r2n ta được điều cần chứng minh. Mệnh đề 2.2.2. Cho n là một số nguyên dương. Khi đó, ta có n   X n i k Fk,i = Fk,2n . i i=0 Chứng minh. Theo công thức Binet cho dãy k-Fibonacci ta có  n   n    i X X n i n i r1 − r2i k Fk,i = k r1 − r2 i i i=0 i=0 " n   # n   X n X n 1 = (kr1 )i − (kr2 )i . r1 − r2 i=0 i i i=0 Bằng cách tính tổng riêng n P i=0 rji , với j=1;2 ta thu được n   X n i=0 i i k Fk,i r12n − r22n = r1 − r2 = Fk,2n . Vậy mệnh đề được chứng minh. Mệnh đề 2.2.3. Cho n, m ≥ 1 là các số nguyên dương. Khi đó, ta có n X i=1 Fk,mi Fk,mn+m − (−1)m Fk,mn − Fk,m = . r1m + r2m − (−1)m − 1 13 Chứng minh. Sử dụng công thức Binet và tính chất r1 −r2 = k, r1 .r2 = −1, ta thu được n X Fk,mi = i=1 n X rmi − rmi 1 i=1 2 r1 − r2 r1nm − r2nm r1m − r2m r12m − r22m + + ··· + = r1 − r2 r1 − r2 r1 − r2

 1  m = r1 + r12m + · · · + r1nm − r2m + r22m + · · · + r2nm r1 − r2   nm nm 1 m r1 − 1 m r2 − 1 r . − r2 . m = r1 − r2 1 r1m − 1 r2 − 1  mn+m  r1 − r1m r2mn+m − r2m 1 − = r1 − r2 r1m − 1 r2m − 1  mn+m m  r1 .r2 − r1m .r2m − r1mn+m + r1m 1 = r1 − r2 (r1m − 1) (r2m − 1) "
# r2mn+m .r1m − r2m .r1m − r2mn+m + r2m 1 − r1 − r2 (r1m − 1) (r2m − 1) # "
m m mn+m mn+m m m mn mn − r2 + (r1 − r2 ) r1 (r1 r2 ) − r2 (r1 r2 ) − r1 1 = m r1 − r2 (r1 r2 ) − r1m − r2m + 1
(−1)m (r1mn − r2mn ) − r1mn+m − r2mn+m + (r1m − r2m ) 1 = . (−1)m − r1m − r2m + 1 r1 − r2 1 = [(−1)m Fk,mn − Fk,mn+m + Fk,m ], m m m (−1) − r1 − r2 + 1 nghĩa là n X Fk,mi i=1 Fk,mn+m − (−1)m Fk,mn − Fk,m = . r1m + r2m − (−1)m − 1 Vậy mệnh đề được chứng minh. Với k = 1, ta thu được một công thức cho dãy Fibonacci, cho bởi n X i=1 Fmi Fmn+m − (−1)m Fmn − Fm = . r1m + r2m − (−1)m − 1 Bằng cách chứng minh tương tự ta có hệ quả sau. Hệ quả 2.2.4. Các phát biểu sau là đúng 14 (i) Nếu j > m, thì n X Fk,mi+j i=0 (ii) n P Fk,mn+m+j − (−1)m Fk,mn+j + (−1)m Fk,j−m − Fk,j ; = r1m + r2m − (−1)m − 1 −1 [−Fk,n+j − Fk,n+j+1 + Fk,j−1 + Fk,j ] ; k = (−1)n+1 Fk,n , n ≥ 1. Fk,i+j = i=0 (iii) Fk,−n Mệnh đề 2.2.5. Với mọi số nguyên dương a, b, c các phát biểu sau là đúng. (i) Fk,a+b−1 = Fk,a .Fk,b + Fk,a−1 .Fk,b−1 ; 1 (ii) Fk,a+b−2 = (Fk,a .Fk,b − Fk,a−2 .Fk,b−2 ) ; k (iii) 1 (Fk,a .Fk,b .Fk,c + kFk,a−1 .Fk,b−1 .Fk,c−1 ) k 1 − (Fk,a−2 .Fk,b−2 .Fk,c−2 ) . k Fk,a+b+c−3 = Chứng minh. (i) Theo công thức Binet, ta có Fk,a+b−1 = Fk,a .Fk,b + Fk,a−1 .Fk,b−1 tương đương với r1a+b−1 − r2a+b−1 r1a − r2a r1b − r2b r1a−1 − r2a−1 r1b−1 − r2b−1 = . + . , r1 − r2 r1 − r2 r1 − r2 r1 − r2 r1 − r2 nghĩa là r1a+b r2a+b − r1a+b + r2a+b − r1a r2b − r1b r2a + r1a+b−2 r1 r2 = r1 − r2 (r1 − r2 )2 r2a+b−2 − r1a−1 r2b−1 − r1b−1 r2a−1 . + (r1 − r2 )2 Đẳng thức này tương đương với ! a+b a+b
r1 r − 2 (r1 − r2 ) = r1a+b + r2a+b − r1a r2b − r1b r2a + r1a+b−2 r1 r2
+ r2a+b−2 − r1a−1 r2b−1 − r1b−1 r2a−1 , 15 nghĩa là r1a+b + r2a+b − r1a+b−1 r2 − r2a+b−1 r1 = r1a+b + r2a+b + r1a+b−2 + r2a+b−2 , đẳng thức này luôn đúng vì r1 r2 = −1. (ii) Từ định nghĩa của dãy k-Fibonacci ta có Fk,a+b−2 = Fk,a .Fk,b−1 + Fk,a−1 .Fk,b−2     Fk,a − Fk,a−2 Fk,b − Fk,b−2 + Fk,b−2 = Fk,a k k 1 = (Fk,a .Fk,b − Fk,a−2 .Fk,b−2 ) . k (iii) Sử dụng định nghĩa của dãy k-Fibonacci, ta có Fk,a+b+c−3 = Fk,a−1 .Fk,b+c−3 + Fk,a−1 .Fk,b+c−2 .   Fk,b .Fk,c + Fk,b−2 .Fk,c−2 = Fk,a−1 (Fk,b−2 .Fk,c−2 + Fk,b−1 .Fk,c−1 ) + Fk,a k 1 (kFk,a−1 + Fk,a−2 ) Fk,b−2 Fk,c−2 = Fk,a Fk,b Fk,c − + Fk,a−1 Fk,b−1 Fk,c−1 k k Fk,a−2 Fk,b−2 Fk,c−2 + Fk,a−1 Fk,b−2 Fk,c−2 − k 1 = (Fk,a Fk,b Fk,c + kFk,a−1 Fk,b−1 Fk,c−1 − Fk,a−2 Fk,b−2 Fk,c−2 ) . k Mệnh đề 2.2.6. Với mọi số nguyên n ≥ 1, ta có r1n = r1 .Fk,n + Fk,n−1 . Chứng minh. Vì r1 , r2 là nghiệm của phương trình r2 = kr + 1 nên ta có r1 + r2 = k, r1 .r1 = −1. Mặt khác Fk,0 = 0; Fk,1 = 1; Fk,2 = kFk,1 + Fk,0 = k; Fk,3 = kFk,2 + Fk,1 = k 2 + 1; . . . Do đó r12 = r1 (k − r2 ) = r1 k − r1 r2 = r1 k + 1 = r1 Fk,2 + Fk,1 . r13 = r1 (r1 k + 1) = r12 k + r1 = r1 (k 2 + 1) + k = r1 Fk,3 + Fk,2 . ... 16 Tiếp tục quá trình ta được r1n = r1 .Fk,n + Fk,n−1 . Hoàn toàn tương tự ta có r2n = r2 .Fk,n + Fk,n−1 . Mệnh đề 2.2.7. Hai số k-Fibonacci liền nhau luôn là hai số nguyên tố cùng nhau, nghĩa là với mọi số nguyên dương n, ta đều có gcd (Fk,n , Fk,n−1 ) = 1. Chứng minh. Sử dụng thuật toán Euclide với Fk,n là số bị chia, Fk,n−1 là số chia ta được các phương trình tuyến tính Fk,n = kFk,n−1 + Fk,n−2 Fk,n−1 = kFk,n−2 + Fk,n−3 .. . Fk,3 = kFk,2 + Fk,1 Fk,2 = kFk,1 + 0. Theo thuật toán Euclice ta có gcd (Fk,n , Fk,n−1 ) = Fk,1 = 1. Vậy ta có điều phải chứng minh. Mệnh đề 2.2.8. Cho m, n là các số nguyên dương. Khi đó Fk,m |Fk,mn . Chứng minh. Ta sẽ chứng minh khẳng định trong mệnh đề bằng quy nạp theo n. Khi n = 1 thì rõ ràng Fk,m |Fk,m . Giả sử khẳng định trong mệnh đề đúng với tất cả các số nguyên l, (l ≥ 1) nghĩa là Fk,m |Fk,mi , với mọi i mà 1 ≤ i ≤ l. Ta cần chứng minh  Fk,m Fk,m(l+1) . Theo Mệnh đề 2.2.5 (i), ta có Fk,m(l+1) = Fk,ml+m = Fk,ml−1 .Fk,m + F k,ml .Fk,m+1 .  Thiết quy nạp, Fk,m |Fk,ml . Do đó Fk,m Fk,m(l+1) . 17 Mệnh đề 2.2.9. Cho q, n là các số nguyên dương. Khi đó gcd (Fk,qn−1 , Fk,n ) = 1. Chứng minh. Gọi d = gcd (Fk,qn−1 , Fk,n ) thì d |Fk,qn−1 và d |Fk,n . Theo Mệnh đề 2.2.8 thì Fk,n |Fk,qn . Suy ra d |Fk,qn . Do đó d|Fk,qn−1 và d|Fk,qn . Theo Mệnh đề 2.2.7, ta suy ra gcd (Fk,qn−1 , Fk,qn ) = 1. Vậy gcd (Fk,qn−1 , Fk,n ) = 1. Mệnh đề 2.2.10. Giả sử m = qn + r với m, n, q, r là các số nguyên dương. Khi đó gcd (Fk,m , Fk,n ) = gcd (Fk,n , Fk,r ) . Chứng minh. Ta có gcd (Fk,m , Fk,n ) = gcd (Fk,qn+r , Fk,n ) = gcd (Fk,qn−1 Fk,r + Fk,qn Fk,r+1 , Fk,n ) = gcd (Fk,qn−1 Fk,r , Fk,n ) = gcd (Fk,r , Fk,n ) . Mệnh đề tiếp theo cho thấy ước số chung lớn nhất của hai số k-Fibonacci luôn là một số k-Fibonacci. Mệnh đề 2.2.11. Cho m và n là các số nguyên dương. Khi đó gcd (Fk,m , Fk,n ) = Fk,gcd(m,n) . 18 Chứng minh. Không mất tổng quát ta có thể giả sử m ≥ n. Áp dụng thuật toán Euclide với số bị chia m số chia n ta được m = q0 n + r1 ; n = q1 r1 + r2 ; r1 = q2 r2 + r3 ; .. . rn−2 = qn−1 rn−1 + rn ; rn−1 = qn rn + 0. Từ Mệnh đề 2.2.10, ta có gcd (Fk,m , Fk,n ) = gcd (Fk,n , Fk,r1 )
= gcd (Fk,r1 , Fk,r2 ) = · · · = gcd Fk,rn−1 , Fk,rn .  Vì rn |rn−1 nên Fk,rn Fk,rn−1 . Do đó
gcd Fk,rn−1 , Fk,rn = Fk,rn . Suy ra gcd (Fk,m , Fk,n ) = Fk,rn . Theo thuật toán Euclide rn = gcd (m, n) , do đó gcd (Fk,m , Fk,n ) = Fk,gcd(m,n) . Với hai số nguyên dương a, b ta ký hiệu bội chung nhỏ nhất của a và b là [a, b]. Mệnh đề 2.2.12. Cho m, n là các số nguyên dương sao cho gcd(m, n) = 1. Khi đó Fk,m Fk,n |Fk,mn . Chứng minh. Theo Mệnh đề 2.2.10 ta có Fk,m |Fk,mn và Fk,n |Fk,mn . Do đó [Fk,m , Fk,n ] |Fk,mn . Mặt khác gcd (Fk,m , F k,n ) = Fk,gcd(m,n) = Fk,1 = 1.