1 Biểu Diễn Các Số Nguyên Thành Tổng Của Các Số Fibonacci Phân Biệt

1. Trang chủ >
2. Thể loại khác >
3. Tài liệu khác >

1 Biểu diễn các số nguyên thành tổng của các số Fibonacci phân biệt

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (681.94 KB, 40 trang )

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ộtsố đị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ỏ quatrong biểu diễn, trong đó u2ui < ui+1un và un là số Fibonaccilớ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ễncủa tất cả các số nguyên N thỏa mãnu7N < 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ácsố Fibonacci u2 , u3 , u4 , u5 và u6 , do số nguyên lớn nhất dưới quy tắc biểudiễn tối tiểu mà đó là quy tắc biểu diễn,u6 + u4 + u2 = 12.15Do đó để 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 , u6và u7 .Bằng các kiểm tra thử, ta có các biểu diễn sau13 = 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ễnnó. Bốn số 14, 15, 16 và 18 đòi hỏi hai số Fibonacci và ba số 17, 19, và 20cầ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ềnunN < 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 = 0nếum>n.216Do đó, ta cón∑ Un,i = un+1 − un = un−1.i=1Bả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.mn1 2 3 4u1N < u2 10 0 0 0u2N < u3 21 0 0 0u3N < u4 31 0 0 0u4N < u5 41 1 0 0u5N < u6 51 2 0 0u6N < u7 61 3 1 0u7N < u8 71 4 3 0u8N < u9 81 5 6 1Bảng 2.1: Giá trị của Un,mn = 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àm Un,m .Xét các số nguyên P, Q và R được xác định bởi các quan hệ sau đâyunP < un+1 ;un−1Q < un ;un−2R < un−1 .Do đóP = un + p,Q = un−1 + q,R = un−2 + r,p = 0, 1, 2, . . . , un−1 − 1,q = 0, 1, 2, . . . , un−2 − 1,r = 0, 1, 2, . . . , un−3 − 1.Sắp xếp các số nguyên P trong hai tập hợp (A) và (B) như sau:(2.2)(2.3)(2.4)17p1 = 0, 1, 2, . . . , un−2 − 1(A) P = un + p1 ,(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 − 1Nếu k là một số nguyên dương, thì từ (2.1.1) suy raun + k = un−1 + k + un−2 .Do đó với tập hợp (A)un + p1 = un−1 + p1 + un−2P = un−1 + q + un−2P = 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ủamột số nguyên Q có thể được chuyển thành một biểu diễn của số nguyênP 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ủacá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,= un + Rr = 0, 1, 2, . . . , un−3 − 1suy 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 unP < un+1 có thể thu được từ các biểu diễn của un−2 trong các số nguyêntrong un−1Q < un và un−3 trong các số nguyên trong un−2Q < un−1 .18Do đó ta thu được các công thức sau:un,m = un−1,m + un−2,m−1(n > 2, m > 1),(2.5)un,1 = 1,un,m = 0với2m > n.Từ đó, un,m có thể liên quan đến các hệ số tổ hợpnk, có các tính chất sau:rr−1r−1=+,kkk−1r= 1,0r= 0 với k > r.kXétTn,m =n−m−1,m−1từ (2.5), Tn,m được thay bởi un,m , ta có thể tính tốn un,m bất kỳ với n > 2và m > 1, ta cóun,m = Tn,m =n−m−1m−1vớ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ànhcá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 − 1N < u8 − 1. Đólà các số 13, 14, 15, 16, 17, 18, 19 và 20. lí do để ta sử dụng miền u7 − 1N < u8 − 1 thay thế cho u7 − 1N < u8 − 1 sẽ được trình bày rõ ở phầndướ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ễnsau đây12 = u6 + u4 + u2 ; 13 = u6 + u4 + u3 ; 14 = u6 + u4 + u3 + u2 ;1915 = 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 u212 = ( 10101 )13 = ( 10110 )14 = ( 10111 )15 = ( 11010 )16 = ( 11011 )17 = ( 11101 )18 = ( 11110 )19 = ( 11111 )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ớisố 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ởiun − 1N < un+1 − 1Giả sử Vn,m ký hiệu số các số nguyên N trong khoảng này, mà cần dùng msố 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.20Như vậyV7,3 +V7,4 +V7,5 = u8 − u7 = u6 = 8.Số nguyên lớn nhất trong khoảng un − 1N < un+1 − 1 là un+1 − 2 và dođó (2.2)n−1∑ ui = un+2 − 2i=2suy ra rằngun+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 đượcthay thế cho un+1 .Số nguyên nhỏ nhất trong miền là un − 1 và từn−2∑ ui = un − 2 < un − 1i=2suy ra phải có một số (vị trí tay trái) được xác định bởi un−1 . Ngoài ra, lạitừ (2.2),u2 + u4 + u6 + . . . + un = un+1n chẵn,u3 + u5 + u7 + . . . + un = un+1n 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 raVn,m = 0 nếum > n − 2m 2(m + 1);21mn1 2 3 456789 10u2 − 1N < u3 − 120 0 0 0000000u3 − 1N < u4 − 131 0 0 0000000u4 − 1N < u5 − 141 1 0 0000000u5 − 1N < u6 − 150 2 1 0000000u6 − 1N < u7 − 160 1 3 1000000u7 − 1N < u8 − 170 0 3 4100000u8 − 1N < u9 − 180 0 1 6510000u9 − 1N < u10 − 190 0 0 4 1061000u10 − 1N < u11 − 1 100 0 0 1 10 157100u11 − 1N < u12 − 1 110 0 0 0520 21810u12 − 1N < u13 − 1 120 0 0 0115 35 28 91Bả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∑Vn,i = un+1 − un = un−1 .i=[ n−12 ]Bảng 2.2 xác định các giá trị của Vn,m với n = 2, 3, . . . 12, và m = 1, 2, . . . , 10.Ta thiết lập quan hệ truy hồi sauVn,m = Vn−1,m−1 +Vn−2,m−1 .Xét các số nguyên P, Q và R được xác định bởiun − 1P < un+1 − 1un−1 − 1Q < un − 1un−2 − 1R < un−1 − 1(2.6)22Biểu diễn Fibonacci của số nguyên Q có dạngun−2 un−3 un−4 . . . u2Q=(1ab... c )Cộng un−1 vào mỗi số nguyên Q sẽ sinh ra un−2 số nguyên mà tất cả chúngtrong khoảngQ + un−1 < un−1 + un − 1.un−1 + un−1Điều này tương đương vớiun+1 − un + un−1 − 1Q + un−1 < un+1 − 1,un+1 − un−1 − un−2 + un−1 − 1un+1 − un−2 − 1un + un−3 − 1Q + un−1 < un+1 − 1,Q + un−1 < un+1 − 1,Q + un−1 < un+1 − 1.Có un−2 số nguyên Q + un−1 , tất cả nằm trong khoảng un−1P < Q+un+1 − 1. Vị trí biểu diễn vị trí của chúng có dạngun−1 un−2 un−3 un−4 . . . u2Q + un−1 = (11a. . . c ).bDo đó 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ố ngun 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ố ngun R có các biểu diễn vị trí có dạngun−3 un−4 un−5 . . . u2R=(1de...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êntrong khoảngun−1 + un−2 − 1R + un−1 < un−1 + un−1 − 123un−1R + un−1 < un−1 − un−2 − 1.Nghĩa là, un−3 số nguyên nằm trong khoảng un − 1P < un+1 − 1. Mỗiphần tử trong số đó sẽ có biểu diễn dưới dạngun−1 un−2 un−3 un−4 un−5 . . . u2R + un−1 = (101de...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ácbiể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ínhbởi hai kỹ thuật tính tốn. Như vậy ta chứng minh được (2.6).Dễ dàng kiểm chứng rằngVn,m =mn−m−2(2.7)thỏa mãn quan hệ đệ quy (2.6).Từ (2.7) ta tìm tổng2(m+1)∑Vi,m =i=m+2mmmm+++...+.012mTừ(2.5) và (2.7) ta suy raVn,m = Un,n−m−1 .2.2Biểu diễn một số tự nhiên thành tổng của các sốFibonacci tổng quátPhầ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ênthành tổng của các số Fibonacci tổng quát. Đây là nội dung chính của luậnvăn và được trình bày dựa vào các kết quả của D. E. Daykin (xem [2], [3]).24Cặp dãy các số tự nhiên (an ), (kn ) được gọi là thỏa mãn tính chất Pnế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 choN = ai1 + ai2 + · · · + aid và iv+1iv + kv , 1Nếu dãy (kn ) là dãy (1, 1, . . . thì điều kiện iv+1iv = it với 1v