ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ TRĂNG
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
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ TRĂNG
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
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngà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 - 2017
i
Mục lục
Danh sách kí hiệu
ii
Mở đầu
1
Chương 1. Về dãy số Fibonacci
3
1.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2 Các tính chất của dãy số Fibonacci
. . . . . . . . . . . . . . . . . . . . .
5
1.3 Về Định lí Zeckendorf
. . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.4 Một số bài toán sơ cấp ứng dụng về dãy số Fibonacci
. . . . . . . . . . .
9
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 13
2.1 Biểu diễn các số nguyên thành tổng của các số Fibonacci phân biệt . . . . 13
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
. . . 23
Kết luận
34
Tài liệu tham khảo
35
ii
Danh sách kí hiệu
{. . .} 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 (cid:62) 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).
tổ hợp chập k của n
(tổng hữu hạn) bi bi = b1 + b2 + · · · + bm
(chuỗi vô hạn) bn bn = b1 + b2 + · · · + bn + · · · (cid:1) (cid:0)n k M m ∑ i=1 ∞ ∑ n=1 là ma trận [uµ, ν]. m ∑ i=1 ∞ ∑ n=1
1
Mở đầu
Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0
và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần
tử luôn bằng tổng hai phần tử trước nó. Dãy số Fibonacci tuy rất đơn giản
về quy tắc thiết lập nhưng là một trong những vẻ đẹp đặc biệt trong kho
tàng Toán học. Dãy số Fibonacci vô cùng biến hóa với nhiều tính chất lí
thú và ứng dụng quan trọng. Người ta đã tìm thấy rất nhiều vấn đề thú vị
liên quan đến dãy số Fibonacci, cả ở toán học thuần túy đến những vấn đề
khác trong tự nhiên.
Dãy Fibonacci được đưa ra bởi nhà toán học Ý tên là Leonardo Pisano
Bogollo (tên thường gọi là Fibonacci) vào thời gian khoảng năm 1170 đến
năm 1250. Dãy số Fibonacci bí ẩn và lí thú đến mức, đã có một tạp chí
toán học hoàn toàn chỉ đăng các kết quả nghiên cứu có liên quan nó, đó là
tạp chí The Fibonacci Quarterly.
Mục tiêu của luận văn là nghiên cứu một sự kiện thú vị về dãy Fi-
bonacci, đó là việc biểu diễn một số tự nhiên thành tổng của các số Fi-
bonacci tổng quát.
Nội dung của luận văn được trình bày trong hai chương:
• Chương 1. Số Fibonacci. Trong chương này trình bày các định nghĩa
và các tính chất cơ bản của các dãy số Fibonacci. Một số bài toán sơ
cấp ứng dụng về dãy số Fibonacci
2
• Chương 2. Việc biểu diễn một số tự nhiên thành tổng của các số Fi-
bonacci tổng quát. Mở rộng định lí Zeckendorf và biểu diễn số tự
nhiên bằng các số Fibinacci phân biệt.
Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học
Thái Nguyên và hoàn thành với sự hướng dẫn của PGS.TS. Nông Quốc
Chinh. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới
người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu,
dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của
tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn
Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban
Chủ nhiệm Khoa Toán-Tin, cùng các giảng viên đã tham gia giảng dạy, đã
tạo mọi điều kiện tốt nhất để tác giả học tập và hoàn thành khóa học.
Thái Nguyên, ngày 10 tháng 11 năm 2017
Tác giả
Nguyễn Thị Trăng
3
Chương 1
Về dãy số Fibonacci
1.1 Định nghĩa và ví dụ
Định nghĩa 1.1.1. Dãy số Fibonacci là dãy số vô hạn các số tự nhiên bắt
đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó được thiết lập
theo quy tắc mỗi phần tử luôn bằng tổng của hai phần tử trước nó,
un+1 = un + un−1
Ví dụ 1.1.2. Fibonacci lần đầu tiên để ý đến dãy số trên khi ông xét một
bài toán về thỏ đẻ con như sau : Bắt đầu với một thỏ đực và thỏ cái, hỏi có
bao nhiêu cặp thỏ có thể được sinh ra trong một năm?
Bài toán giả sử với những điều kiện sau:
1. Bắt đầu với một thỏ đực và thỏ cái vừa chào đời.
2. Thỏ đạt tới tuổi thuần thục sinh sản sau một tháng.
3. Thời gian mang thai thỏ là một tháng.
4. Sau khi thuần thục sinh sản, thỏ cái đẻ đều mỗi tháng.
5. Một thỏ cái sinh ra một thỏ đực và một thỏ cái.
6. Không có thỏ chết.
4
Từ giả thiết suy ra rằng, từ cặp thỏ sơ sinh sau hai tháng sẽ có hai cặp
thỏ. Sau ba tháng, cặp thứ nhất sinh ra một cặp nữa, và ta có ba cặp. Tháng
tiếp theo, cặp thứ hai cũng sinh ra cặp mới, và ta có 5 cặp thỏ.
Kí hiệu qua u(n) số cặp thỏ sau tháng thứ n kể từ đầu năm. Ta thấy sau
tháng (n + 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, (1.1)
u(4) = 3,
. . . ,
u(n + 1) = u(n) + u(n − 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
√ 5 √ 5 , . và r1 = r2 = 1 + 2 1 − 2
5
Nghiệm tổng quát của quan hệ (1.1) có dạng:
(cid:33)n (cid:32) (cid:33)n (cid:32) √ 5 √ 5 . (1.3) u(n) = C1 +C2 1 + 2 1 − 2
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.
.Vậy nghiệm tổng quát có dạng Giải ra ta được C1 = 1√ 5 và C2 = − 1√ 5
√ (cid:16) 1+ 5 2
√ (cid:16) 1− 5 2
(cid:17)n (cid:17)n
u(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
√ (cid:16) 1+ 5 2
(cid:17)n ,
√ 5
và công
. Định lí 1.2.1. Số Fibonacci un là số nguyên gần nhất đối với số 1√ 5 √ (cid:17) (cid:16) 1+ 5 tức là số hạng an của cấp số nhân với từ đầu tiên là 1√ 2 5 bội là 1+ 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ó
1 − rn rn 2√ 5
1 − rn 2 − rn rn 1 √ 5
− . = = |un − an| = (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) rn 1√ 5 |r2|n √ 5
Do
√ 5 < = 1 |r2| = 3 − 1 2 1 − √ 5 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
nên |un − an| < 1 2.
6
Sau đâ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, (1.4)
un+1 = un + un−1.
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,
. . .
7
u2n−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
(1.5) u1 − u2 + u3 − u4 + . . . + u2n−1 − u2n = u2n − u2n−1 + 1.
Cộng thêm vào hai vế u2n+1 ta có
(1.6) u1 − u2 + u3 − u4 + . . . − u2n + u2n+1 = u2n + 1.
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).
8
n = unun+1.
1 + u2
2 + . . . + u2
Mệnh đề 1.2.6. u2
Chứng minh. Ta có
ukuk+1 − uk−1uk = uk(uk+1 − uk−1) = u2 k.
Do đó,
u2 1 = u1u2, u2 2 = u2u3 − u1u2, u2 3 = u3u4 = u2u3,
. . . ,
u2 n = unun+1 − un−1un.
n = unun+1.
1 + u2 u2
2 + . . . + u2
Cộng từng vế các đẳng thức này, ta được
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 (cid:62) 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 (cid:62) 1 và ik+1 > ik + 1 với mọi k = 1, 2, . . . , d − 1 có biểu diễn sau
(1.7) N = ui1 + ui2 + · · · + uid
Đẳng thức (1.7) được gọi là biểu diễn Zeckendorf cho số nguyên dương n.
9
1.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ố
(1.8) Vn = |un+4un−2 − un+2un| = 3.
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
với mọi n ≥ 3. (1.9) Vn = V3,
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à
(1.10) uk < n < uk+1.
Chú ý rằng ta có
(1.11) uk+1 = uk + uk−1.
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:
(1.12) n = uk + m, 0 < m < uk−1.
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ó
(1.13) Sn + 1 = un+2.
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à
(1.14) Sk = u1 + u2 + . . . + uk + 1 = uk+2.
• 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 < uk+10 do 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; (2.1)
với n (cid:62) 3. un = un−1 + un−2
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 (cid:54) ui < ui+1 (cid:54) 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 (cid:54) 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 (cid:54) 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ó (cid:105) . nếu m > Un,m = 0 (cid:104)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 =
m 1 2 3 4
1, 2, 3, . . . , 4.
0 0 0 0
1 0 0 0
1 0 0 0
1 1 0 0
1 2 0 0
1 3 1 0
1 4 3 0
n u1 (cid:54) N < u2 1 u2 (cid:54) N < u3 2 u3 (cid:54) N < u4 3 u4 (cid:54) N < u5 4 u5 (cid:54) N < u6 5 u6 (cid:54) N < u7 6 u7 (cid:54) N < u8 7 u8 (cid:54) N < u9 8
1 5 6 1
Bảng 2.1: Giá trị của Un,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à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 đây
un (cid:54) P < un+1; un−1 (cid:54) Q < un; un−2 (cid:54) R < un−1.
Do đó
(2.2) P = un + p, p = 0, 1, 2, . . . , un−1 − 1,
(2.3) Q = un−1 + q, q = 0, 1, 2, . . . , un−2 − 1,
(2.4) R = un−2 + r, 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:
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
suy ra từ (2.4). = un + R
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 (cid:54) 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 (cid:54) Q < un và un−3 trong các số nguyên trong un−2 (cid:54) Q < un−1.
18
Do đó ta thu được các công thức sau:
(n > 2, m > 1), un,m = un−1,m + un−2,m−1
(2.5) un,1 = 1,
2m > n. với un,m = 0
(cid:1), có các tính chất sau:
(cid:19) + = (cid:18)r − 1 k (cid:18)r − 1 k − 1 (cid:19) = 1,
= 0 với k > r. Từ đó, un,m có thể liên quan đến các hệ số tổ hợp (cid:0)n k (cid:19) (cid:19) (cid:18)r , k (cid:18)r 0 (cid:19) (cid:18)r k
Xét
(cid:19) , Tn,m = (cid:18)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ó
(cid:19) với n > 2 và m > 1. un,m = Tn,m = (cid:18)n − m − 1 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 (cid:54) 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 − 1 (cid:54) N < u8 − 1 thay thế cho u7 − 1 (cid:54) 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 − 1 (cid:54) 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 − 1 (cid:54) N < un+1 − 1 là un+1 − 2 và do đó (2.2)
n−1 ∑ i=2
ui = un+2 − 2
suy ra rằng
(n − 2 chữ số ) un+1 − 2 = (111 . . . 11)
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),
n chẵn, u2 + u4 + u6 + . . . + un = un+1
n lẻ, u3 + u5 + u7 + . . . + un = un+1
suy ra số nguyên nhỏ nhất trong miền xác định bởi
(1010 . . . 10) (1010 . . . 101) hoặc
theo n là lẻ hoặc chẵn.
Từ đó, ta suy ra
hoặc n < m + 2, Vn,m = 0 nếu (cid:3) hoặc n > 2(m + 1); m > n − 2 m < (cid:2) n−1 2
m 1 2 3 4
21
n
9 10 6 7 5 8
0 0 0 0 0 0 0 0 0 0 2
1 0 0 0 0 0 0 0 0 0 3
1 1 0 0 0 0 0 0 0 0 4
0 2 1 0 0 0 0 0 0 0 5
0 1 3 1 0 0 0 0 0 0 6
0 0 3 4 0 0 1 0 0 0 7
0 0 1 6 1 0 5 0 0 0 8
6 1 0 0 0 0 0 0 4 10
7 1 0 0 0 0 0 1 10 15
5 8 1 0 0 0 0 0 20 21
1 1 0 0 0 0 15 35 28 9 u2 − 1 (cid:54) N < u3 − 1 u3 − 1 (cid:54) N < u4 − 1 u4 − 1 (cid:54) N < u5 − 1 u5 − 1 (cid:54) N < u6 − 1 u6 − 1 (cid:54) N < u7 − 1 u7 − 1 (cid:54) N < u8 − 1 u8 − 1 (cid:54) N < u9 − 1 u9 − 1 (cid:54) N < u10 − 1 9 u10 − 1 (cid:54) N < u11 − 1 10 u11 − 1 (cid:54) N < u12 − 1 11 u12 − 1 (cid:54) N < u13 − 1 12
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−1 2 ]
Vn,i = un+1 − un = un−1.
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 sau
(2.6) Vn,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ởi
un − 1 (cid:54) P < un+1 − 1
un−1 − 1 (cid:54) Q < un − 1 un−2 − 1 (cid:54) 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
a b c Q = ( . . . ) 1
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úng
trong khoảng
un−1 + un−1 (cid:54) Q + un−1 < un−1 + un − 1.
Điều này tương đương với
un+1 − un + un−1 − 1 (cid:54) Q + un−1 < un+1 − 1, un+1 − un−1 − un−2 + un−1 − 1 (cid:54) Q + un−1 < un+1 − 1, un+1 − un−2 − 1 (cid:54) Q + un−1 < un+1 − 1, un + un−3 − 1 (cid:54) 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 (cid:54) 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
a b c . . . ). 1 1 Q + un−1 = (
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
d e f R = ( . . . . ) 1
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 − 1 (cid:54) R + un−1 < un−1 + un−1 − 1
23
un−1 (cid:54) R + un−1 < un−1 − un−2 − 1.
Nghĩa là, un−3 số nguyên nằm trong khoảng un − 1 (cid:54) 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
d e f . . . . ) 1 0 1 R + un−1 = (
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
(cid:19) (cid:18) (2.7) Vn,m = m n − m − 2
thỏa mãn quan hệ đệ quy (2.6).
Từ (2.7) ta tìm tổng
2(m+1) ∑ i=m+2
(cid:19) (cid:19) (cid:19) + + + . . . + (cid:19) . Vi,m = (cid:18)m m (cid:18)m 0 (cid:18)m 1 (cid:18)m 2
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 (cid:62) iv + kv, 1 (cid:54) v < d.
Nếu dãy (kn) là dãy (1, 1, . . . thì điều kiện iv+1 (cid:54) iv + kv có thể thay bởi iv (cid:54)= it với 1 (cid:54) v < t (cid:54) d. Mặt khác nếu (kn) (cid:54)= (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 h (cid:54) k (cid:54) h + 1. Ta
định nghĩa dãy dãy số Fibonacci {vn} bậc (h, k) xác định như sau
với 1 (cid:54) n (cid:54) k,
(2.8) với k < n < k + h,
với n (cid:62) k + h. vn = n vn = un−1 + un−h vn = un−1 + un−h + (k − h)
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 đó
và (2.9) i1 ≥ 1 iν+1 − iν ≥ 2 với i ≤ ν < d,
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 (cid:62) i1 +h nếu d > 1 và iv+1 (cid:62) iv +k với 2 (cid:54) v < d.
(2.10)
Ngoài ra, vid (cid:54) 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 (cid:54) N < 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 (cid:62) k. Giả sử bổ đề đúng với t < m. Vậy, từ giả thiết quy nạp, nếu vm (cid:54) 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ì
0 (cid:54) N = vm < vm+1 − vm (cid:54) 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 (cid:62) k nên ta có
0 (cid:54) M < vm+1 − vm = vm+1−h nếu m + 1 < h + k vm+1−k + k − h nếu m + 1 (cid:62) 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ữa M = vM, vì vậy N = vM + vm với m − M > m − (m + 1 − h) = h − 1, nghĩa là m − M (cid:62) h.
(b) nếu m + 1 (cid:62) 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ủa M như dạng (2.10), tức là M = vi1 + vi2 + · · · + vid với id < m + 1 − k. Vì vậy, từ m (cid:62) 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 (cid:54) k2 (cid:54) k1 + 1, kn = k2 vớin (cid:62) 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 (cid:54) 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 (cid:62) 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à,
sao cho {an} = a1, a2, . . . 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 (cid:62) 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à
(2.11) với 1 (cid:54) ν < µ (cid:54) d. iµ − iν (cid:62) mµ−ν,ν
Định nghĩa 2.2.9. Xét dãy {an} và tập hợp w với W ⊆ 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ét W 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 1 (cid:54) d (cid:54) e
và
iν+1 − iν (cid:62) jν+1 − jν
với 1 (cid:54) ν < 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 (cid:62) 1, (2.12)
và (i1, i2, . . . , id−1, id) ∈ W ⇒ (i1, i2, . . . , id−1, id + 1) ∈ W.
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 mãn với
W . Do đó Định nghĩa 2.2.9 với Tiên đề 1 là tổng quát hơn Định nghĩa
2.2.8. Tiếp theo, chúng tôi trình bày kết quả mở rộng thứ 2 về biển diễn số
nguyên bằng các số Fibonacci tổng quát (xem [3]).
Định lí 2.2.11. Cho {an}, W là biểu diễn các số nguyên, W ⊆ V . Khi đó với t = 1, 2, 3, . . ., số nguyên N thỏa mãn at (cid:54) N < at+1 có một biểu diễn N = a(I) với I = (i1, i2, . . . , id) ⊂ W và id = t.
Từ Định lí 2.2.11, ta có: nếu
(i1, i2, . . . , id) ∈ W với i (cid:54) e (cid:54) d.
và
1 (cid:54) ν1 < ν2 < . . . < νe (cid:54) d
30
thì
(iν1, iν2, . . . , iνe) ∈ W.
Giả sử W thỏa mãn Tiên đề 1. Khi đó rõ ràng (1, p) ∈ W , tồn tại ít nhất
một số nguyên p sao cho (1, p) ∈ W , và có số nguyên lớn nhất q sao cho
vector q q thành phân (1, 1, . . . , 1) ⊂ W . Một trong các số p và q là 1 và
một số còn lại lớn hơn 1.
Bổ đề 2.2.12. Nếu N là một số nguyên, N > 1, và các biểu diễn của N và
N + 1 là
N = a(i1, i2, . . . , id)
và
N + 1 = a( ji, j2, . . . , je)
thì
1 (cid:54) a( j1 + 1, j2 + 1, . . . , je + 1) − a(i1 + 1, i2 + 1, . . . , id + 1) (cid:54) q + 1.
Chú ý mối quan hệ giữa (2.12) với kết quả này. Hơn nữa kết quả cho
phép chúng ta đưa ra các cận với tốc độ tăng trưởng của {an}, và những
cận này cần thiết cho phép chứng minh.
Lấy N = at − 1 do đó N + 1 = at = a(t), ta tìm
1 (cid:54) at+1 − a(i1 + 1, i2 + 1, . . . , id + 1) (cid:54) q + 1.
Ta có thể nói nhiều hơn về các điều trên, và ta minh họa bằng cách xây
dựng cặp {an}, W theo con đường quy nạp.
Ta có a1 = 1, và vector (1) thuộc W . Ta có (1, 1) thuộc W hoặc không.
Giả sử ta chọn là không có. Khi đó ta có (1, 2) thuộc W hoặc không. Giả
sử không. Khi đó ta có (1, 3) thuộc W hoặc không. Giả sử là có. Phép xây
dựng ta tiến hành trong hình minh họa sau đây:
31
Hình 2.1: Xây dựng cặp {an}, W khi q = 3
Trong Hình 2.2, một biểu diễn là xoay vòng nếu ở một công đoạn thích
hợp, ta thừa nhận hoặc từ chối. Một biểu diễn là bị gạch chéo nếu và chỉ
nếu nó không được thừa nhận. Một biểu diễn tại đầu một mũi tên phải được
thừa nhận hoặc không phải là trường hợp có thể được, bởi (2.12) hoặc Tiên
đề 1, bởi vì biểu diễn ở đuôi của mũi tên đã được chấp nhận hoặc không.
Chú ý rằng ta không lấy tự do các giá trị của a5 hoặc a8. Cũng như vậy,
biểu diễn 1+3+12 phải được thừa nhận mặc dù nó không bị kiểm soát bởi
(2.12). Nếu 1 + 3 + 12 bị từ chối, thì a7 = 16 và ta có 17 = a(1, 7) = a(4, 6)
mâu thuẫn với tính duy nhất của các biểu diễn. Tổng quát, với p > 1, khi
ta có thể lấy tùy ý giá trị của at nếu ta chọn giá trị ít nhất của at, ta sẽ chọn
tùy ý được giá trị của at+1. Mặt khác, nếu ta chọn giá trị at là lớn, ta sẽ
không được chọn tùy ý được giá trị của at+1, at+2, . . . , at+p−2.
Một kiểu xây dựng điển hình với q > 1 được xây dựng trong Hình 2.2
sau đây:
Dù cặp {an}, W nào phát sinh sẽ có một dãy số {mn} các số nguyên,
32
Hình 2.2: Xây dựng cặp {an}, W khi q = 3
0 < m1 < m2 < m3 < . . ., có thể hữu hạn hoặc vô hạn, sao cho nếu ta đặt
với n (cid:54) 0, (2.13) an = 0
thì ta có đồng nhất thức
với n (cid:62) 0. (2.14) an+1 = 1 + an + an−m1 + an−m2+...
Sau đó bằng cách trừ phương trình (2.14) trong các cặp mà các số hạng
cao trong {an} thỏa mãn một quan hệ truy hồi. Ví dụ, tiếp tục xây dựng sơ
đồ trong Hình 2.2, ta hãy sử dụng cách chọn tùy ý các cột 3, 4, 5 theo mẫu
: chấp nhận, không chọn, từ chối, chấp nhận, không chọn, từ chối, . . . Khi
đó {mn} = 2, 5, 8, 11, 14, . . . là một cấp số cộng số học với công sai là 3,
33
và dãy (an) được cho bởi
(2.15) a1 = 1, a2 = 2, a3 = 3,
an+1 = an + an−2 + an−2 − an−3 với n ≥ 3. an = 0 với n (cid:54) 0,
34
Kết luận
Luận văn “Việc biểu diễn một số tự nhiện thành tổng các số Fibonacci
tổng quát” tập trung trình bày các kết quả trong các tài liệu chính của tác
giả Daykin, Fern và một số tác giả khác (xem [2]-[8]). Cụ thể luận văn đã
trình bày các kết quả sau:
1. Trình bày một số sự kiện sơ cấp nhất của dãy số Fibonacci và một số
bài toán liên quan;
2. 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 phân biệt và tổng quát. Mở rộng kết quả của
Zeckendorf.
35
Tài liệu tham khảo
Tiếng Việt
[1] Hà Huy Khoái (2004), Số học - Chuyên đề bồi dưỡng học sinh giỏi
toán trung học phổ thông, NXB Giáo dục.
Tiếng Anh
[2] D. E. Daykin (1960), “Representation of natural numbers as sums of
generalized Fibonacci numbers”, Journal of the London Mathemati-
cal Society, 35, pp. 143–161.
[3] D. E. Daykin (1969), “Representation of natural numbers as sum of
generalized Fibonacci numbers - II”, The Fibonacci Quarterly, 7, pp.
494–510.
[4] H. H. Ferns (1965), “On the representation of integers as sums of
distinct Fibonacci numbers”, The Fibonacci Quarterly, 3, pp. 21–30.
[5] P. Lafer (1964), “Exploring the Fibonacci representation of integers”,
The Fibonacci Quarterly, p. 114.
[6] Nivolai N. Vorobiev (1992), Fibonacci Numbers, Springer.
[7] J. L. Brown, JR (1961), ”Zeckendorf’s Theorem and Some applica-
tions", New York, pp. 163–168.
36
[8] V. E. Hoggatt, JR (1961), ”Generalized Zeckendorf Theorem", New
York, pp. 89–92.
