Luận văn Việc biểu diễn một số tự nhiên thành tổng của các số fibonacci tổng quát

1) thì sẽ có u(n) cặp ban đầu, cộng thêm số cặp do các cặp đã có sau tháng thứ (n−1) sinh ra. Số này là u(n−1). Vậy u(1) = 1, u(2) = 1, u(3) = 2, u(4) = 3, . . . , u(n+1) = u(n)+u(n−1). (1.1) Theo giả thiết, u(1) = 1, u(2) = 1, nên ta có u(3) = 2, u(4) = 3, . . . ,u(12) = 144,u(13) = 233. Các số u(n) được gọi là các số Fibonacci. Xét dãy Fibonacci xác định bởi u(n+1) = u(n)+u(n−1). (1.2) Phương trình đặc trưng của quan hệ (1.1) là r2− r−1= 0. Phương trình này có các nghiệm r1 = 1+ √ 5 2 , và r2 = 1−√5 2 . 5Nghiệm tổng quát của quan hệ (1.1) có dạng: u(n) =C1 ( 1+ √ 5 2 )n +C2 ( 1−√5 2 )n . (1.3) Các số Fibonacci u(n) được cho bởi (1.3) với điều kiện u(0) = 1, u(1) = 1. Khi đó các hằng sốC1,C2 được tính từ hệ phương trình. C1+C2 = 0√5 2 (C1−C2) = 1. Giải ra ta đượcC1 = 1√5 vàC2 =− 1√ 5 .Vậy nghiệm tổng quát có dạng u(n) = ( 1+ √ 5 2 )n−(1−√52 )n√ 5 . Công thức trên đây được gọi là công thức Binet. Dựa vào công thức Binet, ta có định lí sau đây cho một tính chất thú vị của các số Fibonacci. 1.2 Các tính chất của dãy số Fibonacci Định lí 1.2.1. Số Fibonacci un là số nguyên gần nhất đối với số 1√5 ( 1+ √ 5 2 )n , tức là số hạng an của cấp số nhân với từ đầu tiên là 1√5 ( 1+ √ 5 2 ) và công bội là 1+ √ 5 2 . Chứng minh. Rõ ràng chỉ cần chứng minh rằng trị tuyệt đối của hiệu giữa hai số un và an luôn luôn bé hơn 1/2. Ta có |un−an|= ∣∣∣∣rn1− rn2√5 − r n 1√ 5 ∣∣∣∣= ∣∣∣∣rn1− rn2− rn1√5 ∣∣∣∣= |r2|n√5 . Do |r2|= ∣∣∣∣∣1− √ 5√ 5 ∣∣∣∣∣< 3−12 = 1 nên |un−an|< 12 . 6Sau đây ta sẽ chứng minh một số tính chất cơ bản của dãy số Fibonacci. Trong các mệnh đề sau đây, un dùng để kí hiệu số Fibonacci thứ n xác định bằng u1 = 0, u2 = 1, un+1 = un+un−1. (1.4) Mệnh đề 1.2.2. u1+u2+ . . .+un = un+2−1. Chứng minh. Ta có u1 = u3−u2, u2 = u4−u3, . . . un−1 = un+1−un, un = un+2−un+1. Cộng từng vế đẳng thức này, ta có u1+u2+ . . .+un = un+2−u2, mà u2 = 1 nên ta có điều phải chứng minh. Mệnh đề 1.2.3. u1+u3+u5+ . . .+u2n−1 = u2n. Chứng minh. Ta có u1 = u2, u3 = u4−u2, u5 = u6−u4, . . . 7u2n−3 = u2n−2−u2n−1, u2n−1 = u2n−u2n−2. Cộng từng vế các bất đẳng thức, ta được u1+u3+u5+ . . .+u2n−1 = u2n. Ta có điều phải chứng minh. Mệnh đề 1.2.4. u2+u4+ . . .+u2n = u2n+1−1. Chứng minh. Từ Mệnh đề 1.2.2 ta có u1+u2+u3+ . . .+u2n = u2n+2−1. Từ Mệnh đề 1.2.3 ta có u1+u3+u5+ . . .+u2n−1 = u2n. Trừ từng vế đẳng thức này ta được u2+u4+ . . .+u2n = u2n+2−1−u2n = u2n+1−1. Điều phải chứng minh. Mệnh đề 1.2.5. u1−u2+u3−u4+ . . .+(−1)n+1un = (−1)n+1un−1+1. Chứng minh. Từ các Mệnh đề 1.2.3 và Mệnh đề 1.2.4 ta được u1−u2+u3−u4+ . . .+u2n−1−u2n = u2n−u2n−1+1. (1.5) Cộng thêm vào hai vế u2n+1 ta có u1−u2+u3−u4+ . . .−u2n+u2n+1 = u2n+1. (1.6) Công thức trong Mệnh đề 1.2.5 chính là kết hợp của hai công thức (1.5) và (1.6) (tương ứng với n lẻ và n chẵn). 8Mệnh đề 1.2.6. u21+u 2 2+ . . .+u 2 n = unun+1. Chứng minh. Ta có ukuk+1−uk−1uk = uk(uk+1−uk−1) = u2k. Do đó, u21 = u1u2, u22 = u2u3−u1u2, u23 = u3u4 = u2u3, . . . , u2n = unun+1−un−1un. Cộng từng vế các đẳng thức này, ta được u21+u 2 2+ . . .+u 2 n = unun+1. 1.3 Về Định lí Zeckendorf Bổ đề 1.3.1. Giả sử dãy số (ci)i=0,1,...,k là dãy tăng, thỏa mãn ci > 2 và ci+1 > ci+1 với mọi i= 0,1, . . .. Khi đó ta có k ∑ i=1 uci < uck+1 Định lí 1.3.2 (Zeckendorf). Xét N là số nguyên dương bất kỳ. Khi đó tồn tại duy nhất dãy số (ik)i=1,2,...,d tăng, thỏa mãn ik > 1 và ik+1 > ik+1 với mọi k = 1,2, . . . ,d−1 có biểu diễn sau N = ui1+ui2+ · · ·+uid (1.7) Đẳng thức (1.7) được gọi là biểu diễn Zeckendorf cho số nguyên dương n. 91.4 Một số bài toán sơ cấp ứng dụng về dãy số Fi- bonacci Mục này sẽ trình bày một số bài toán sơ cấp ứng dụng về dãy số Fi- bonacci. Bài toán 1.4.1. Giả sử uk là số hạng thứ k của dãy Fibonacci. Chứng minh rằng với mọi số tự nhiên n ≥ 3, thì số An = 4un−2unun+2un+4+ 9 là một số chính phương. Lời giải. Trước hết ta có nhận xét sau đây: Với mọi số Vn = |un+4un−2−un+2un|= 3. (1.8) Thật vậy Vn = |(un+2+un+3)un−2−un+2| = |un+3+un−2+un+2(un−2un)|= |un+3+un−2+un+2+un−1| = |un+3+un−2+un+2(un−2un)|= |un+3+un−2+un+2+un−1| = |un+3(un−1−un−3)−un+2un−1|= |un+3+un+1(un+2−un+3)| = |un+3un−3−un+1un−1|=Vn−1. Từ Vn =Vn−1, và quá trình ấy cứ lặp lại, ta đi đến Vn =V3, với mọi n≥ 3. (1.9) Ta có V3 = |u7u1−u5u3|= |13 ·1−15 ·2|= 3 như thế nhận xét (1.8) được chứng minh. Từ (1.8) suy ra un+4un−2 = unun+2±3 hay An = 4unun+2(unun+2±3)+9= (2unun+2±3)2. 10 Do un nguyên với mọi n ∈ N suy ra An là số chính phương với mọi n ≥ 3 nguyên. Ta có điều cần chứng minh. Bài toán 1.4.2. Chứng minh rằng mọi số tự nhiên thì hoặc là một số Fi- bonacci, hoặc có thể biểu diễn thành dạng của tổng một vài số Fibonacci phân biệt, ở đây ta hiểu số Fibonacci là một phần tử của dãy Fibonacci. Lời giải. Kí hiệu uk là số Fibonacci thứ k với k ∈ N. Xét dãy Fibonacci 1,1,2,3,4,8,13, . . . Ta chứng minh điều khẳng định của bài toán bằng nguyên lí quy nạp toán học. Với n = 1,2,3,4 (và để ý rằng 4 = 3+1, ta thấy điều khẳng định của bài toán đã đúng với mọi số tự nhiên nhỏ hơn u5 = 5). Giả sử điều khẳng định của bài toán đã đúng với mọi số tự nhiên n nhỏ hơn uk. Khi đó dĩ nhiên khẳng định của bài toán cũng đúng khi n= uk. Xét các số tự nhiên n mà uk < n< uk+1. (1.10) Chú ý rằng ta có uk+1 = uk+uk−1. (1.11) Từ (1.10) và (1.11) sy ra các số n thoả mãn (1.10) có thể biểu diễn dưới dạng: n= uk+m, 0< m< uk−1. (1.12) Từ (1.12) và giả thiết quy nạp suy ra mọi số tự nhiên m nhỏ hơn uk−1 có thể biểu diễn thành tổng của một vài số Fibonacci khác nhau, chỉ số của các số này nhỏ hơn k−1. Vì thế số n= uk+m cũng có thể biểu diễn được thành tổng của các số Fibonacci (trong các số đó, số lớn nhất thì bằng uk còn các sô khác có các chữ số nhỏ hơn k−1). Vậy điều khẳng định của bài toán cũng đúng với mọi số tự nhiên n nhỏ hơn uk+1. 11 Theo nguyên lí quy nạp toán học, ta suy ra điều khẳng định của bài toán cũng đúng với mọi số tự nhiên. Bài toán được chứng minh. Bài toán 1.4.3. Chứng minh rằng không có 8 số Fibonacci liên tiếp có tổng là một số Fibonacci. Lời giải. Xét tổng Sk = uk+1+uk+2+uk+3+ . . .+uk+8 của 8 số Fibonacci liên tiếp. Chú ý rằng với dãy Fibonacci ta có: u1 ≤ u2 < u3 < u4 < .. . < un < .. . Vì dãy Fibonacci là tăng thực sự kể từ u2, nên nếu ta chứng minh được với mọi k tự nhiên mà uk+9 < Sk < uk+10, thì rõ ràng Sk không phải là một số Fibonacci, và từ đó suy ra kết luận của bài toán là đúng. Thật vậy, ta có uk+9+uk+9+uk+7 < uk+8+uk+7+uk+6+ . . .+uk+1 = Sk (vì mọi số hạng của dãy Fibonacci đều dương). Bây giờ ta chỉ còn phải chứng minh rằng Sk < uk+10.. Ta có nhận xét sau đây: “Nếu gọi Sn là tổng của n số Fibonacci đầu tiên, thì với mọi n≥ 2 ta có Sn+1= un+2. (1.13) Công thức (1.13) được chứng minh bằng quy nạp như sau • Với n= 2, ta có S2 = 1+1 nên S2+1= 3= u4. Vậy (1.13) đúng khi n= 2. 12 • Giả sử khẳng định (1.13) đã đúng với k = n, tức là Sk = u1+u2+ . . .+uk+1= uk+2. (1.14) • Xét khi n= k+1. Ta có Sk+1+1= u1+u2+. . .+uk+uk+1+1=(u1+u2+. . .+uk+1)+uk+1. Từ giả thiết quy nạp (1.14) suy ra Sk+1+1= uk+2+uk+1 = uk+3. Vậy (1.13) cũng đúng khi n= k+1. Theo nguyên lí quy nạp toán học suy ra (1.13) đúng với mọi n≥ 2. Trở lại bài toán đang xét, ta có Sk = uk+1+uk+1+ . . .+uk+8 = Sk+8−Sk. Theo nhận xét trên suy ra Sk = (uk+10−1)− (uk+2−1) = uk+10−uk+2 0. Vậy bất đẳng thức uk+9 < Sk < uk+10 đã được chứng minh. Bài toán được giải hoàn toàn. Bài toán 1.4.4. Chứng minh rằng mọi số nguyên dương N có thể được viết thành tổng các số rời rạc không liên tiếp của dãy số Fibonacci. Lời giải. Giả sử (un)n≥1 là dãy số Fibonacci. Khi đó u1 = u2 = 1 và un+2 = un+1+un với mọi n≥ 1. Ta giả sử rằng un ≤ N < un+1. Do vậy, 0≤ N−un < un−1. Khi đó tồn tại s< n−1 sao cho us ≤ N−un < us+1. Do đó 0≤ N−un− us < us−1 và s−1< n−2. Do đó N có thể được viết thành N = un+us+up+ . . .+ur, trong đó các n,s, p, . . . ,r là chỉ số của các số không liên tiếp. 13 Chương 2 Biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát Chương này sẽ trình bày về biểu diễn số tự nhiên bằng các số Fibonacci phân biệt và biểu diễn số tự nhiên bằng các số Fibonacci tổng quát. Như định nghĩa dãy số Fibonacci trong Định nghĩa 1.1.1 trong chương 1. Ta xét dãy số Fibonacci (un) vớiu1 = 1, u2 = 2;un = un−1+un−2 với n> 3. (2.1) 2.1 Biểu diễn các số nguyên thành tổng của các số Fi- bonacci phân biệt Mục này trình bày về việc biểu diễn các số nguyên thành tổng của các số Fibonacci phân biệt. Nội dung của mục này sẽ được trình bày theo bài báo của H.H. Ferns (xem [4]). Trước tiên ta xét ví dụ sau: Ví dụ 2.1.1. Xét số nguyên 29. Nó có thể được khai triển thành tổng của các số Fibonacci theo cách sau đây: 29= u8+u6 = u8+u5+u4 14 = u8+u5+u3+u2 = u7+u6+u5+u4 = u7+u6+u5+u3+u2. Từ Ví dụ 2.1.1 này, ta thấy rằng cần phải áp đặt một số “quy tắc cơ bản” nếu chúng ta phân biệt giữa các loại biểu diễn khác nhau. Ta có một số định nhĩa sau. Định nghĩa 2.1.2. Một biểu diễn được gọi là • tối tiểu nếu nó không chứa hai số Fibonacci liên tiếp; • tối đại nếu không có hai số Fibonacci liên tiếp ui và ui+1 được bỏ qua trong biểu diễn, trong đó u2 6 ui < ui+1 6 un và un là số Fibonacci lớn nhất được chứa trong biểu diễn. Như vậy, u8+u6 là một biểu diễn tối tiểu của số nguyên 29 trong khi đó u7+u6+u5+u3+u2 là một biểu diễn tối đại. Từ đây ta có một biểu diễn tối đại (tương ứng, biểu diễn tối tiểu) có thể được biến đổi vào một biểu diễn tối tiểu (tương ứng, biểu diễn tối đại) bằng cách áp dụng công thức truy hồi của dãy số Fibonacci. Như một ví dụ minh họa của các biểu diễn tối tiểu, ta xét các biểu diễn của tất cả các số nguyên N thỏa mãn u7 6 N < u8. Khi đó N có thể là một trong tám số 13,14,15,16,17,18,19 hoặc 20. Số nguyên nhỏ nhất trong tập hợp này là 13, không thể được biểu diễn bởi các số Fibonacci u2,u3,u4,u5 và u6, do số nguyên lớn nhất dưới quy tắc biểu diễn tối tiểu mà đó là quy tắc biểu diễn, u6+u4+u2 = 12. 15 Do đó để biểu diễn tất cả các số nguyên của tập hợp này đòi hỏi u2,u3,u4,u5,u6 và u7. Bằng các kiểm tra thử, ta có các biểu diễn sau 13= u7; 14= u7+u2; 15= u7+u3; 16= u7+u4; 17= u7+u4+u2; 18= u7+u5; 19= u7+u5+u2; 20= u7+u5+u3. Một trong những số nguyên này là 13, chỉ một số Fibonacci để biểu diễn nó. Bốn số 14,15,16 và 18 đòi hỏi hai số Fibonacci và ba số 17,19, và 20 cần ba số Fibonacci để biểu diễn. Định nghĩa 2.1.3. Số Un,m là ký hiệu số các số nguyên N trong miền un 6 N < un+1 mà cần m số Fibonacci để biểu diễn. Từ định nghĩa ta có U7,1 = 1; U7,2 = 4; U7,3 = 3. Rõ ràng là U7,1+U7,2+U7,3 = u8−u7 = u6 = 8. Từ (2.1) ta có Un,m = 0 nếu m> [n 2 ] . 16 Do đó, ta có n ∑ i=1 Un,i = un+1−un = un−1. Bảng 2.1 xác định các giá trị của Un,m với n = 1,2,3, . . . ,8 và m = 1,2,3, . . . ,4. n m 1 2 3 4 u1 6 N < u2 1 0 0 0 0 u2 6 N < u3 2 1 0 0 0 u3 6 N < u4 3 1 0 0 0 u4 6 N < u5 4 1 1 0 0 u5 6 N < u6 5 1 2 0 0 u6 6 N < u7 6 1 3 1 0 u7 6 N < u8 7 1 4 3 0 u8 6 N < u9 8 1 5 6 1 Bảng 2.1: Giá trị củaUn,m n= 1,2, . . . ,8 với m= 1,2, . . . ,4. Bây giờ ta xét một số tính chất của hàmUn,m. Xét các số nguyên P, Q và R được xác định bởi các quan hệ sau đây un 6 P< un+1; un−1 6 Q< un; un−2 6 R< un−1. Do đó P= un+ p, p= 0,1,2, . . . ,un−1−1, (2.2) Q= un−1+q, q= 0,1,2, . . . ,un−2−1, (2.3) R= un−2+ r, r = 0,1,2, . . . ,un−3−1. (2.4) Sắp xếp các số nguyên P trong hai tập hợp (A) và (B) như sau: 17 (A) P= un+ p1, p1 = 0,1,2, . . . ,un−2−1 (B) P= un+ p2,, p2= un−2,un−2+1,un−2+2, . . . ,un−1+(un−2−un−2−1)= un−2+ r, r = 0,1,2, . . . ,un−3−1 Nếu k là một số nguyên dương, thì từ (2.1.1) suy ra un+ k = un−1+ k+un−2. Do đó với tập hợp (A) un+ p1 = un−1+ p1+un−2 P= un−1+q+un−2 P= un+q. So sánh phương trình cuối với (2.2) và (2.3) ta có thể thấy biểu diễn của một số nguyên Q có thể được chuyển thành một biểu diễn của số nguyên P của tập (A) bằng cách thay un−1 bởi un. Bằng quy tắc này, chúng ta có thể lấy được các biểu diễn của un−2 của các số nguyên P từ các biểu diễn của các số nguyên Q. Tiếp theo, ta xét các số nguyên P trong tập hợp (B). Ta có P= un+ p2, p2 = un−2,un−2+1,un−2+2, . . . ,un−2+(un−1−un−2−1) = un+un−2+ r, r = 0,1,2, . . . ,un−3−1 = un+R suy ra từ (2.4). Kết quả này suy ra các biểu diễn của các số nguyên P trong tập hợp (B) có thể chuyển từ các biểu diễn của các số nguyên R bằng cách bổ sung un. Bằng hai phép toán biểu diễn của un−1 trong các số nguyên trong un 6 P < un+1 có thể thu được từ các biểu diễn của un−2 trong các số nguyên trong un−1 6Q< un và un−3 trong các số nguyên trong un−2 6Q< un−1. 18 Do đó ta thu được các công thức sau: un,m = un−1,m+un−2,m−1 (n> 2,m> 1), un,1 = 1, un,m = 0 với 2m> n. (2.5) Từ đó, un,m có thể liên quan đến các hệ số tổ hợp (n k ) , có các tính chất sau:( r k ) = ( r−1 k ) + ( r−1 k−1 ) ,( r 0 ) = 1,( r k ) = 0 với k > r. Xét Tn,m = ( n−m−1 m−1 ) , từ (2.5), Tn,m được thay bởi un,m, ta có thể tính toán un,m bất kỳ với n > 2 và m> 1, ta có un,m = Tn,m = ( n−m−1 m−1 ) với n> 2 và m> 1. Tiếp theo, ta quay về xét các biểu diễn tối đại của các số nguyên thành các tổng của các số Fibonacci. Ta sẽ sử dụng một kỹ thuật khác, và một số kỹ thuật như trong biểu diễn tối tiểu. Như ví dụ, ta xét các số nguyên N sao cho u7− 1 6 N < u8− 1. Đó là các số 13,14,15,16,17,18,19 và 20. lí do để ta sử dụng miền u7−16 N < u8−1 thay thế cho u7−1 6 N < u8−1 sẽ được trình bày rõ ở phần dưới đây. Như trong định nghĩa của biểu diễn tối đại, ta bắt đầu với các biểu diễn sau đây 12= u6+u4+u2;13= u6+u4+u3;14= u6+u4+u3+u2; 19 15= u6+u5+u3;16= u6+u5+u3+u2;17= u6+u5+u4+u2; 18= u6+u5+u4+u3;19= u6+u5+u4+u3+u2; Tám biểu diễn đó có thể được viết lại ngắn gọn hơn dưới dạng sau: u6 u5 u4 u3 u2 12= ( 1 0 1 0 1 ) 13= ( 1 0 1 1 0 ) 14= ( 1 0 1 1 1 ) 15= ( 1 1 0 1 0 ) 16= ( 1 1 0 1 1 ) 17= ( 1 1 1 0 1 ) 18= ( 1 1 1 1 0 ) 19= ( 1 1 1 1 1 ) Trong cách viết này, có thể được sử dụng như các số nhị phân kết hợp với số Fibonacci. Chú ý rằng với sơ đồ này, hai số không ở các vị trí liền kề trong biểu thức tối đại. Chẳng hạn như (. . .100 . . .) phải được thay thế bởi (. . .011 . . .) do ui = ui−1+ui−2. Các số Fibonacci cũng biểu thị giá trị vị trí được sắp xếp theo thứ tự tăng dần từ phải sang trái bắt đầu với u2. Tiếp theo, ta xét trường hợp tổng quát hơn. Giả sử N là một số nguyên được định nghĩa bởi un−16 N < un+1−1 Giả sử Vn,m ký hiệu số các số nguyên N trong khoảng này, mà cần dùng m số Fibonacci để biểu diễn chúng trong biểu diễn tối đại. Khi đó với ví dụ minh họa được cho ở trên, V7,3 = 3; V7,4 = 4; V7,5 = 1. 20 Như vậy V7,3+V7,4+V7,5 = u8−u7 = u6 = 8. Số nguyên lớn nhất trong khoảng un−16 N < un+1−1 là un+1−2 và do đó (2.2) n−1 ∑ i=2 ui = un+2−2 suy ra rằng un+1−2= (111 . . .11) (n−2 chữ số ) mà trong đó không có số không xuất hiện và trong đó giá trị ở bên trái là un−1. Điều này giải thích lí do để lấy chặn trên của N được un+1−1 được thay thế cho un+1. Số nguyên nhỏ nhất trong miền là un−1 và từ n−2 ∑ i=2 ui = un−2< un−1 suy ra phải có một số (vị trí tay trái) được xác định bởi un−1. Ngoài ra, lại từ (2.2), u2+u4+u6+ . . .+un = un+1 n chẵn, u3+u5+u7+ . . .+un = un+1 n lẻ, suy ra số nguyên nhỏ nhất trong miền xác định bởi (1010 . . .10) hoặc (1010 . . .101) theo n là lẻ hoặc chẵn. Từ đó, ta suy ra Vn,m = 0 nếu m> n−2 hoặc n 2(m+1); 21 n m 1 2 3 4 5 6 7 8 9 10 u2−16 N < u3−1 2 0 0 0 0 0 0 0 0 0 0 u3−16 N < u4−1 3 1 0 0 0 0 0 0 0 0 0 u4−16 N < u5−1 4 1 1 0 0 0 0 0 0 0 0 u5−16 N < u6−1 5 0 2 1 0 0 0 0 0 0 0 u6−16 N < u7−1 6 0 1 3 1 0 0 0 0 0 0 u7−16 N < u8−1 7 0 0 3 4 1 0 0 0 0 0 u8−16 N < u9−1 8 0 0 1 6 5 1 0 0 0 0 u9−16 N < u10−1 9 0 0 0 4 10 6 1 0 0 0 u10−16 N < u11−1 10 0 0 0 1 10 15 7 1 0 0 u11−16 N < u12−1 11 0 0 0 0 5 20 21 8 1 0 u12−16 N < u13−1 12 0 0 0 0 1 15 35 28 9 1 Bảng 2.2: Các giá trị của Vn,m với n= 2,3,4, . . . ,12 và m= 1,2,3, . . . ,10. n−2 ∑ i=[n−12 ] Vn,i = un+1−un = un−1. Bảng 2.2 xác định các giá trị củaVn,m với n= 2,3, . . .12, vàm= 1,2, . . . ,10. Ta thiết lập quan hệ truy hồi sau Vn,m =Vn−1,m−1+Vn−2,m−1. (2.6) Xét các số nguyên P, Q và R được xác định bởi un−16 P< un+1−1 un−1−16 Q< un−1 un−2−16 R< un−1−1 22 Biểu diễn Fibonacci của số nguyên Q có dạng un−2 un−3 un−4 . . . u2 Q= ( 1 a b . . . c ) Cộng un−1 vào mỗi số nguyênQ sẽ sinh ra un−2 số nguyên mà tất cả chúng trong khoảng un−1+un−1 6 Q+un−1 < un−1+un−1. Điều này tương đương với un+1−un+un−1−16 Q+un−1 < un+1−1, un+1−un−1−un−2+un−1−16 Q+un−1 < un+1−1, un+1−un−2−16 Q+un−1 < un+1−1, un+un−3−16 Q+un−1 < un+1−1. Có un−2 số nguyên Q+ un−1, tất cả nằm trong khoảng un−1 6 P < Q+ un+1−1. Vị trí biểu diễn vị trí của chúng có dạng un−1 un−2 un−3 un−4 . . . u2 Q+un−1 = ( 1 1 a b . . . c ). Do đó các biểu diễn của un−2 của các số nguyên P có thể lấy được từ có số nguyên Q bởi việc tạo ra một vị trí bổ sung xác định như là un−1. un−3 các số nguyên R có các biểu diễn vị trí có dạng un−3 un−4 un−5 . . . u2 R= ( 1 d e . . . f ) . Bổ sung un−1 vào mỗi un−3 các số nguyên sẽ được kết quả là các số nguyên trong khoảng un−1+un−2−16 R+un−1 < un−1+un−1−1 23 un−1 6 R+un−1 < un−1−un−2−1. Nghĩa là, un−3 số nguyên nằm trong khoảng un− 1 6 P < un+1− 1. Mỗi phần tử trong số đó sẽ có biểu diễn dưới dạng un−1 un−2 un−3 un−4 un−5 . . . u2 R+un−1 = ( 1 0 1 d e . . . f ) . Do đó các biểu diễn của un−3 các số nguyên P có thể nhận được từ các biểu diễn của R bằng việc bổ sung vào bên trái hai giá trị là un−1 và un−2. Như vậy không có sự trùng nhau và tất cả các nguyên tố P được tính bởi hai kỹ thuật tính toán. Như vậy ta chứng minh được (2.6). Dễ dàng kiểm chứng rằng Vn,m = ( m n−m−2 ) (2.7) thỏa mãn quan hệ đệ quy (2.6). Từ (2.7) ta tìm tổng 2(m+1) ∑ i=m+2 Vi,m = ( m 0 ) + ( m 1 ) + ( m 2 ) + . . .+ ( m m ) . Từ(2.5) và (2.7) ta suy ra Vn,m =Un,n−m−1. 2.2 Biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát Phần này sẽ trình bày các kết quả về việc biểu diễn một số tự nhiên thành tổng của các số Fibonacci tổng quát. Đây là nội dung chính của luận văn và được trình bày dựa vào các kết quả của D. E. Daykin (xem [2], [3]). 24 Cặp dãy các số tự nhiên (an),(kn) được gọi là thỏa mãn tính chất P nếu thỏa mãn điều kiện sau: Mỗi số tự nhiên N tồn tại duy nhất các số tự nhiên i1, i2, . . . , id sao cho N = ai1+ai2+ · · ·+aidvà iv+1 > iv+ kv, 16 v< d. Nếu dãy (kn) là dãy (1,1, . . . thì điều kiện iv+1 6 iv+ kv có thể thay bởi iv 6= it với 1 6 v < t 6 d. Mặt khác nếu (kn) 6= (1,1, . . .) thì phải có giả thiết a1 < a2 < .. .. Trong Định lí 2.2.3 chỉ ra giả thiết dãy (an) phải tăng thực sự mới tồn tại dãy (kn) để cặp dãy (an),(kn) thỏa mãn tính chất P là dãy Fibonacci (vn) bậc (h,k): Định nghĩa 2.2.1. Giả sử h, k là các số tự nhiên sao cho h6 k 6 h+1. Ta định nghĩa dãy dãy số Fibonacci {vn} bậc (h,k) xác định như sau vn = n với 16 n6 k, vn = un−1+un−h với k < n< k+h, vn = un−1+un−h+(k−h) với n> k+h. (2.8) Nhận xét 2.2.2. Dãy số Fibonacci (un)n trong Định nghĩa 1.1.1 ở Chương 1, là dãy Fibonacci bậc (2,2). Zeckendorf (xem 1.7) đã chứng minh được mọi số nguyên dương N có duy nhất biểu diễn dưới dạng N = ui1+ui2+ · · ·+uid , trong đó i1 ≥ 1 và iν+1− iν ≥ 2 với i≤ ν < d, (2.9) Chúng tôi sẽ trình bày kết quả mở rộng của Định lí Zeckendorf như sau: 25 Định lí 2.2.3. Giả sử (vn)n là dãy Fibonacci bậc (h,k)). Khi đó với mỗi số tự nhiên N, tồn tại duy nhất bộ số i1, i2, . . . , id thỏa mãn N= vi1+vi2+· · ·+vid với i2> i1+h nếu d> 1 và iv+1> iv+k với 26 v< d. (2.10) Ngoài ra, vid 6 N < vid+1. Để chứng minh Định lí 2.2.3 ta xét bổ đề sau: Bổ đề 2.2.4. Giả sử t là số nguyên dương bất kỳ. Với mọi số tự nhiên N thỏa mãn vt 6N < vt+1, thì N có biểu diễn dạng (2.10) với id = t; hơn nữa biểu diễn này là duy nhất. Chứng minh Bổ đề:Ta sẽ chứng minh quy nạp theo t. Vì k số hạng đầu tiên của dãy (vn) là 1,2, . . . ,k và k < vk+1 < vk+2 < · · · , nên bổ đề đúng với mọi t < k. Xét m là số nguyên bất kỳ, m> k. Giả sử bổ đề đúng với t <m. Vậy, từ giả thiết quy nạp, nếu vm 6 N < vm+1 thì N không thể biểu diễn như dạng (2.10) với id < t. Hơn nữa, vì vm+1 < vm+2 < · · · , nên N không thể biểu diễn như dạng (2.10) với id > t. Vì vậy đề N có biểu diễn dạng (2.10) cần phải có id = t. Vì 06 N = vm < vm+1− vm 6 vm, nên tồn tại ít nhất một biểu diễn của N−vm. Do đó tồn tại ít nhật một biểu diễn của N. Đặt M = N− vm. Do m> k nên ta có 06M < vm+1− vm =  vm+1−h nếu m+1 h+ k Ta có các trường hợp sau 1. Nếu M = 0 thì N = vm. 26 2. Nếu M > 0 thì (a) nếu m+1< h+k thì 0<M < vm+1−h và vì m+1−h< k, nên ta có vm+1−h =m+1−h. Hơn nữaM = vM, vì vậy N = vM+vm với m−M > m− (m+1−h) = h−1, nghĩa là m−M > h. (b) nếu m+ 1 > h+ k thì 0 < M < vm+1−k+ k− h và ta có k− h = 0 hoặc = 1. i. M = vm+1−k, khi đó k− h = 1, và N = vm+1−k+ vm với m− (m+1− k) = k−1= h. ii. M < vm+1−k. Khi đó theo giả thiết quy nạp tồn tại biểu diễn củaM như dạng (2.10), tức làM = vi1+ vi2+ · · ·+ vid với id < m+1− k. Vì vậy, từ m> id+ k ta có N = vi1+ vi2+ · · ·+ vid + vm. Như vậy, vì 1= v1 < v2 < .. . nên với mọi số tự nhiên N, tồn tại t ∈ N sao cho vt ≤ N ≤ vt+1 và N = vi1 + vi2 + . . .+ vid và biểu diễn này là duy nhất, nên định lý được chứng minh. Định lí 2.2.5. Nếu (an),(kn) là cặp dãy số tự nhiên với tính chất P, và (an) là dãy tăng, thì k1 6 k2 6 k1+1, kn = k2 vớin> 3 và dãy (an) là dãy Fibonacci bậc (h,k) với h= k1,k = k2. Xét (an),(kn) là cặp dãy số tự nhiên với tính chất P. Giả sử dãy (an) sau khi được sắp xếp theo thự tự tăng dần ta được dãy số (bn). Trong chứng minh Định lí 2.2.5 sử dụng các kết quả sau: 27 Bổ đề 2.2.6. Với r 6 2 ta có br = r. Nếu r > 2 thì br là số nhỏ nhất không có biểu diễn (2.10) với các số hạng b1,b2, . . . ,br−1. Chứng minh. Rõ ràng b1 = 1 và b2 = 2 suy ra từ tình biễu diễn duy nhất của 1 và 2. Giả sử r > 2. Khi đó nếu br có biểu diễn dạng (2.10) chỉ sử dụng các số hạng b1, . . . ,br−1 thì từ tính duy nhất của biểu diễn của br ta suy ra điều mâu thuẫn. Hơn nữa, nếu tồn tại số tự nhiên N < br biểu diễn bằng các số hạng b1, . . . ,br−1 thì N không thể biểu diễn qua tất cả a1, . . . ,ar. Giả sử a1 < a2 < · · · . Khi đó từ Bổ đề 2.2.6 ta có ngay kết quả sau Bổ đề 2.2.7. Giả sử (kn) là dãy số tự nhiên, khi đó tồn tại nhiều nhất một dãy tăng (an) sao cho cặp dãy số tự nhiên (an),(kn) có tính chất P. Tiếp theo, để trình bày về biểu diễn số tự nhiên bằng các số Fibonacci tổng quát thứ 2 (xem Định lí 2.2.11) ta sẽ dùng các ký hiệu sau đây: • {. . .} là dãy số nguyên. • (. . .) là một vector có các tọa độ nguyên. • [. . .] là các ma trận mà phần tử là các số nguyên. • V là tập hợp bao gồm các vector có dạng (i1, i2, . . . , id) với d > 1, các thành phần iν là các số nguyên với 1≤ i1 ≤ i2 ≤ . . . id. Thông thường ta sẽ viết I thay cho (i1, i2, . . . , id). • M là ma trận thay cho [uµν ]. Dãy {an} là dãy số tự nhiên, tăng thực sự với số hạng đầu tiên là 1, tức là, {an}= a1,a2, . . . sao cho a1 = 1, 28 a1 < a2 < .. . < an < .. . . Ký hiệu a(I) hoặc a(i1, i2, . . . , id) thay cho số a(I) = a(i1, i2, . . . , id) = ai1+ai2+ . . .+aid . Chú ý: dãy số Fibonacci {un} được định nghĩa bằng nhiều cách, chẳng hạn như . . . ,0,0,0,0,0,0,0,0,1,2,3,5,8,13, . . . . . . ,0,0,0,0,0,0,0,1,1,2,3,5,8,13, . . . , và . . . ,−8,5,−3,2,−1,1,0,1,1,2,3,5,8,13, . . . . Trong Định lí 1.7 là kết quả mở rộng của Định lí Zeckendorf khi thay hằng số 2 trong Định lí 2.10 bằng dãy (kn). Kết quả mở rộng tiếp theo bằng cách thay dãy (kn) bằng ma trận vô hạn M = [mµv] với m,v > 1 và mµv là các số tự nhiên, được mô tả trong định nghĩa dưới đây. Định nghĩa 2.2.8. Dãy {an} và ma trận M được gọi là biểu diễn các số nguyên, nếu với mỗi số nguyên dương N tồn tại một và chỉ một vector I ∈V sao cho N = a(I) và iµ − iν > mµ−ν ,ν với 16 ν < µ 6 d. (2.11) Định nghĩa 2.2.9. Xét dãy {an} và tập hợp w vớiW ⊆V . Ta nói {an},W là biểu diễn nguyên nếu với mỗi số nguyên dương N tồn tại duy nhất một vector I ∈W sao cho N = a(I). Trong định nghĩa trên ta xétW thỏa mãn Tiên đề 1 sau đây: 29 Tiên đề 1. Nếu (i1, i2, . . . , id) ∈V, ( ji, j2, . . . , je) ∈W với 16 d 6 e và iν+1− iν > jν+1− jν với 16 ν < d thì (i1, i2, . . . , id) ∈W. Từ Tiên đề 1 ta có nhận xét quan trọng sau: Nhận xét 2.2.10. (i1, i2, . . . , id) ∈W ⇔ (i1+1, i2+1, . . . , id+1) ∈W và i1 > 1, và (i1, i2, . . . , id−1, id) ∈W ⇒ (i1, i2, . . . , id−1, id+1) ∈W. (2.12) Nếu M = [mµ,ν ] là một ma trận bất kỳ, và W là tập tất cả các vector I = (i1, i2, . . . , id) thỏa mãn (2.11), khi đó rõ ràng Tiên đề 1 thỏa