Một số tính chất cơ sở
Định nghĩa 1.1.1 Dãy Fibonacci là dãy số xác định bởiF 1 =1,F 2 =1và
F n =F n−2 +F n−1 , vớin≥3. Định nghĩa 1.1.2 Dãy Lucas là dãy số xác định bởiL 1 =1,L 2 =3và
Dãy Fibonacci tổng quát được xác định bởiG 1 =α,G 2 =β, và
Nếuα =β =1, thì dãy Fibonacci tổng quátG n là dãy FibonacciF n
Nếuα =1vàβ =3, thì dãy Fibonacci tổng quátGn là dãy LucasLn.
Dãy nâng Fibonacci, được định nghĩa bởi F(n) + a với a là một số nguyên, có những đặc điểm khác biệt so với dãy Fibonacci truyền thống Trong khi các phần tử liên tiếp của dãy Fibonacci là những số nguyên tố cùng nhau, điều này không áp dụng cho dãy nâng Fibonacci Năm 1971, Hoggatt đã chỉ ra rằng gcd(F(4n+1) + 1, F(4n+2) + 1) = L(2n), gcd(F(4n+1) - 1, F(4n+2) - 1) = F(2n), và gcd(F(4n+3) - 1, F(4n+4) - 1) = L(2n+1).
Các phần tử liên tiếp của dãy Fibonacci khi cộng hoặc trừ 1 không phải lúc nào cũng là các số nguyên tố cùng nhau Nếu định nghĩa fn(a) = gcd(Fn + a, Fn+1 + a), thì dãy fn(0) sẽ là một dãy không đổi với các giá trị 1, 1, 1, Trong khi đó, dãy fn(±1) lại không bị giới hạn và có thể có giá trị lớn hơn.
Năm2003Hernández và Lucas đã chứng minh rằng có một số không đổicmà gcd(F m +a,Fn+a)>e cm , đúng đối với vô hạn các cặp số nguyên dươngm>n.
Trong luận văn này, chúng ta sẽ chứng minh rằng hàm số \( f_n(a) \) bị chặn khi \( a \neq \pm 1 \) Cụ thể, chúng ta sẽ chứng minh hai định lý quan trọng Định lý 1.1.3 khẳng định rằng với mọi số nguyên \( \alpha \) và \( \beta \), nếu \( \alpha^2 + (\alpha \cdot \beta) - \beta^2 - a^2 \neq 0 \), thì có thể xác định rằng \( \text{gcd}(G_{2n-1} + a, G_{2n} + a) \leq \alpha^2 + (\alpha \cdot \beta) - \beta^2 - a^2 \).
(1.1) Định lí 1.1.4 Với mọi số nguyên (α),(β), nvàavớiα 2 + (α.β)−β 2 +a 2 6=0, chúng ta có gcd(G 2n +a,G 2n+1 +a)≤ α 2 + (α.β)−β 2 +a 2
Giả sửα =β =1trong Định lí 1.1.3 và Định lí 1.1.4 Chúng ta rút ra được hệ quả sau:
Hệ quả 1.1.5 Với mọi số nguyênnvàa gcd(F 2n−1 +a,F 2n +a)≤ a 2 −1
Do đó, chúng ta kết luận rằng(fn(a))bị chặn nếua6=±1 Và một hệ quả khác ln(a) =gcd(Ln+a,L n+1 +a) chỉ nhận hữu hạn giá trị.
Hệ quả 1.1.6 Với số nguyênnvàa, ta có gcd(L 2n−1 +a,L 2n +a)≤a 2 +5, gcd(L 2n +a,L 2n+1 +a)≤ a 2 −5
Giả sửα =1vàβ =3trong Định lí 1.1.3 và Định lí 1.1.4 Chúng ta kết luận rằngln(a)bị chặn đối với số nguyên atuỳ ý.
Trong phần tiếp theo, chúng ta sẽ suy ra hai bổ đề cơ bản, từ đó xác định các giá trị fn(1), fn(2), fn(−1), fn(−2) và ln(1) trong các phần 3, 4 và 5.
Trong phần cuối, chúng ta sẽ chứng minh Định lí 1.1.3 và Định lí 1.1.4.
Bổ đề 1.1.7 Với số nguyênn,kvàa gcd(G n +aF k ,G n−1 −aF k+1 ) =gcd(G n−2 +aF k+2 ,G n−3 −aF k+3 ) (1.3)
Chứng minh Do gcd(a,b) =gcd(a+bc,b) đối với bất kì số nguyên a,b và c, chúng ta có gcd(G n +aFk,G n−1 −aF k+1 ) =gcd(G n +aFk−(G n−1 −aF k+1 ),(G n−1 −aF k+1 ))
Bổ đề được chứng minh.
Bổ đề 1.1.8 Với số nguyênm,kvàa, gcd(G m +a,G m+1 +a) =gcd(G m−(2k) +aF 2k−1 ,G m−(2k+1) −aF 2k ) (1.4)
Chứng minh Chúng ta rút gọngcd(G m +a,Gm+1+a), gcd(G m +a,G m+1 +a) =gcd(G m +a,G m+1 +a−(G m +a))
VìF −1 =1, vàF 0 =0,chúng ta có thể viết
=gcd(Gm+a,G m+1 +a) =gcd(Gm+aF −1 ,G m−1 −aF 0 ), và áp dụng (1.3)klần để rút ra kết quả.
Lưu ý rằng, ta gọi dãy số{F n +k}là dãy số f n (k).
Dãy số f n (1)
Định lí 1.2.1 Với mọi số nguyênn, chúng ta có gcd(F 4n−1 +1,F 4n +1) =F 2n−1 , (1.5) gcd(F 4n +1,F 4n+1 +1)
Chứng minh Giả sử m=4n−1,k=n, vàa=1trong (1.4): gcd(F 4n−1 +1,F 4n +1) =gcd(F 2n−1 +F 2n−1 ,F 2n−2 −F 2n )
Giả sửm=4n+1,k=n, vàa=1trong (1.4): gcd(F 4n+1 ,F 4n+2 +1) =gcd(F 2n+1 +F 2n−1 ,F 2n +F 2n )
Giả sửm=4n,k=n, vàa=1trong (1.4): gcd(F 4n +1,F 4n+1 +1) =gcd(F 2n +F 2n−1 ,F 2n−1 +F 2n )
Vìgcd(F qn+r ,Fn) =gcd(F n ,Fr)cho các số nguyênq,rvàn Điều này cho ta gcd(F 4n+1 ,F4n+1+1) =gcd(F 2n−2 ,F 3 ).
Vìgcd(F k ,Fr) =gcd(F gcd(k,r) )cho các số nguyênkvàr, gcd(F 4n +1,F 4n+1 +1) =gcd(F 2n−2 ,F 3 )
Giả sửm=4n+2,k=n+1vàa=1trong (1.4) gcd(F 4n+2 +1,F 4n+3 +1) =gcd(F 2n +F 2n+1 ,F 2n−1 −F 2n+2 )
F 1 =1, nếu ngược lại, đó là (1.8).
Dãy số ( f n (2))
Định lí 1.3.1 Với bất kì số nguyênn, chúng ta có gcd(F 4n−1 +2,F 4n +2) =1, (1.9) gcd(F 4n +2,F 4n+1 +2) =1, (1.10) gcd(F 4n+1 +2,F 4n+2 +2)
Chứng minh Giả sử m=4n−1,k=nvàa=2trong (1.4): gcd(F 4n−1 +2,F 4n +2) =gcd(F 2n−1 +2F 2n−1 ,F 2n−2 −2F 2n )
Vì gcd(a,bc) =gcd(a,gcd(a,b)c) và gcd(F 2n−1 +F 2 ) =1, ta có gcd(F 4n−1 +2,F 4n +2) =gcd(3gcd(F 2n−1 ,F 2n+1 ),F 2n+1 )
Giả sửm=4n,k=n, vàa=2trong (1.4): gcd(F 4n+2 ,F 4n+1 +2) =gcd(F 2n +2F 2n−1 ,F 2n−1 −2F 2n )
Giả sửm=4n+1,k=n, vàa=2trong (1.4): gcd(F 4n+1 +2,F 4n+2 +2) =gcd(F 2n+1 +2F 2n−1 ,F 2n −2F 2n )
Giả sửm=4n+2,k=n, vàa=2trong (1.4): gcd(F 4n+2 +2,F 4n+3 +2) =gcd(F 2n+2 +2F 2n−1 ,F 2n+1 −2F 2n )
F 1 =1, nếu ngược lại, đó là (1.12).
Dãy số ( f n (−1)) , ( f n (−2)) và (l n (1))
Áp dụng các phương pháp tương tự, chúng ta có Định lí 1.4.1 Với bất kì số nguyênn, chúng ta có gcd(F 4n−1 −1,F 4n −1) =L 2n−1 , gcd(F 4n −1,F 4n+1 −1)
1, nếu ngược lại, gcd(F 4n+1 −1,F 4n+2 −1) =F 2n , gcd(F 4n+2 −1,F 4n+3 −1)
1, nếu ngược lại. Định lí 1.4.2 Với bất kì số nguyênn, chúng ta có gcd(F 4n−1 −2,F 4n −2) =1, gcd(F 4n −2,F 4n+1 −2)
3, nếun≡1 mod 2,gcd(F 4n+2 −2,F 4n+3 −2) =1. Định lí 1.4.3 Với bất kì số nguyênn, chúng ta có gcd(L 4n−1 +1,L 4n +1)
Chứng minh Định lí 1.1.3 và Định lí 1.1.4
Trước tiên, chúng ta chứng minh Định lí 1.1.3.
Chứng minh Định lí 1.1.3 Giả sử m=4n−1vàk=ntrong (1.4): gcd(G 4n−1 +a,G 4n +a)
Sử dụng quan hệ truy hồi choFn, giả sử an=αF 2n−3 +βF 2n−1 +aF 2n−1 = (a+α)F 2n−3 + (a+β)F 2n−2 và b n =αF 2n−4 +βF 2n−3 −aF 2n = (−a−α+β)F 2n−3 + (α−2a)F 2n−2
Vìgcd(a n ,bn)chia hếtγan+θbn, với bất kì số nguyênγ vàθ, và
Chúng ta thấy rằng, nếuα 2 +α β−β 2 −a 2 6=0thì ước chung lớn nhất của hai số là α 2 +α β−β 2 −a 2
Vì vậygcd(a n ,b n )chia hếtα 2 +α β−β 2 −a 2 Nghĩa là gcd(G 4n−1 +a,G 4n +a)≤ α 2 +α β−β 2 −a 2
Nếu chúng ta giả sử,m=4n+1vàk=ntrong (1.4) bằng cách tương tự, chúng ta có gcd(G 4n+1 +a,G 4n+2 +a)≤ α 2 +α β−β 2 −a 2
Ta có điều cần chứng minh.
Tiếp theo, chúng ta sẽ chứng minh Định lí 1.1.4.
Chứng minh Định lí 1.1.4 Giả sử m=4nvàk=ntrong (1.4): gcd(G 4n +a,G 4n+1 +a) =gcd(G 2n +aF 2n−1 ,G 2n−1 −aF 2n )
Sử dụng quan hệ truy hồi choFn, giả sử an=αF 2n−2 +βF 2n−1 +aF 2n−1 =αF 2n−2 + (β+α)F 2n−1 và b n =αF 2n−3 +βF 2n−2 +aF 2n = (−α+β−a)F 2n−2 + (α−a)F 2n−1
Vìgcd(a n ,bn)chia hếtγan+θbn, với bất kì số nguyênγ và θ,và
Chúng ta thấy rằng, nếuα 2 +α β−β 2 −a 2 6=0,thì ước chung lớn nhất của hai số là α 2 +α β−β 2 +a 2
.Vì vậygcd(an,bn)chia hếtα 2 +α β−β 2 +a 2 Nghĩa là gcd(G 4n +a,G 4n+1 +a)≤ α 2 +α β−β 2 +a 2
. Nếu chúng ta giả sửm=4n+2vàk=ntrong (1.4) bằng cách tương tự, ta có gcd(G 4n+2 +a,G 4n+3 +a)≤ α 2 +α β−β 2 +a 2
Ta có điều phải chứng minh.
Hợp thành của các số Fibonacci
Monoit tự do
Định nghĩa 2.1.1 Một tập hợp khác rỗngGđược trang bị một phép toán hai ngôi
∗là một monoid nếu và chỉ nếu
(ii) a∗e=e∗a=a,∀a∈G,∃e∈G. Định nghĩa 2.1.2 Một monoid con của một monoid(M,∗)là một tập conN của
M mà nó đóng trong phép toán monoid và chứa phần tử đơn vị ecủa M.Ký hiệu,
N là một monoid con của M nếu N chứa trong M, và với mọi x, y thuộc N, tích x∗y cũng thuộc N, cùng với phần tử đơn vị e cũng thuộc N Monoid tự do trên một tập hợp được định nghĩa là monoid mà các phần tử của nó là tất cả các dãy hữu hạn, bao gồm dãy rỗng hoặc nhiều phần tử của tập hợp, với phép toán monoid là phép ghép dãy và phần tử đơn vị duy nhất là dãy rỗng.
Chúng ta nghiên cứu công thức số Fibonacci, trong đó số Fibonacci F(n+1) được xác định là số cách biểu diễn số n thành tổng của các số.
Các tổng có thành phần 1 và 2 tạo thành một monoit tự do thông qua phép toán ghép, từ đó phát sinh các công thức liên quan Một hợp thành của số nguyên n là dãy các số nguyên dương a1, a2, , ak, được gọi là các phần của hợp thành, với tổng bằng n.
Người ta đã biết nhiều công thức biểu diễn các số Fibonacci trong thuật ngữ của tổng các hợp thành:
(i) F n+1 là số các hợp thành củanvới các phần bằng1hoặc2.
(ii) F n−1 là số các hợp thành củanvới các phần lớn hơn1.
(iii) F n là số các hợp thành củanvới các thành các phần lẻ.
Từ nay về sau, ta gọiC(n)là tập hợp các hợp thànha 1 a k củan.
Bổ đề 2.1.4 Giả sửu 1 ,u 2 ,u 3 , là dãy số tuỳ ý Khi đó tổng
∑ a∈C(n) u a1 u a2 uak là hệ số của x n trong
Chứng minh Để chứng minh Bổ đề 2.1.4, ta chỉ cần khai triển Công thức (2.1) thành tổng chuỗi lũy thừa, rồi nhân chuỗi ta được.
Khi đó công thức(i)−(vi)suy ra từ Bổ đề 2.1.4, các đồng nhất thức dễ kiểm tra
(vi’) 1−3x+x 1−x 2 = (1−2x−x 2 −x 3 −x 4 −x 5 − .) −1 và các công thức
Công thức (2.2) suy ra dễ dàng từ quan hệ truy hồi Fibonacci Fn =F n−1 +F n−2 Với (2.3) và (2.4), chúng ta có
1−3x 2 +x 4 (2.5) Khi đó (2.3) và (2.4) được suy ra bằng cách loại lũy thừa lẻ củaxtừ (2.5).
Giả sử A là một tập hợp, được gọi là Bảng chữ cái, và A∗ là tập hợp các từ tạo thành từ các phần tử của A Với phép toán ghép, A trở thành một monoit (nửa nhóm có đơn vị) với đơn vị là từ rỗng, và A∗ được gọi là monoit tự do trên A Độ dài l(x) của phần tử x = a₁a₂ aₖ, với mỗi aᵢ thuộc A, là k Tổng quát, một monoit tự do M là monoit đẳng cấu với A∗ Nếu M là nửa nhóm tự do, tồn tại tập hợp con P của M, sao cho mỗi phần tử của M có sự phân tích duy nhất thành tích các phần tử của P, và P được gọi là tập hợp nguyên tố của M Hàm trọng số trên nửa nhóm tự do M, ký hiệu là ω: M → N, với N là tập hợp các số nguyên không âm, thỏa mãn ω(m₁m₂) = ω(m₁) + ω(m₂) cho mọi m₁, m₂ ∈ M và ω(m) = 0 khi và chỉ khi m là phần tử đơn vị của M Hàm trọng số trên M được xác định bởi giá trị của nó trên tập hợp nguyên tố của M.
Nếu \( L \) là một monoit tự do, phần tử \( p \) của \( L \) được gọi là bất khả quy nếu \( p \) không phải là phần tử đơn vị của \( M \) và không thể biểu diễn như tích của hai phần tử khác trong \( L \) Tính bất khả quy của \( p \) phụ thuộc vào cả \( p \) và \( L \) Mọi phần tử của \( L \) có thể phân tích thành tích các phần tử bất khả quy, nhưng phân tích này không phải là duy nhất Trong trường hợp \( L \) là một monoit tự do, phân tích này luôn luôn duy nhất và các phần tử bất khả quy được coi là các nguyên tố của \( L \).
Giả sử M là một monoit tự do với hàm trọng ω Nếu x là ẩn, ánh xạ m7→x ω(m) trở thành phép đồng cấu từ M vào monoit các luỹ thừa của x với phép toán nhân Việc phân tích duy nhất trong M dẫn đến một đồng nhất thức quen thuộc cho các chuỗi luỹ thừa hình thức m∈M, đó là ∑ x ω(m) = (1− ∑ p∈P x ω(m)) −1, trong đó P là tập hợp các nguyên tố của M.
M có trọng số được định nghĩa là tổng của các yếu tố a thuộc tập C(n), trong đó mỗi yếu tố được tính bằng tích của các số nguyên tố u i, với i là chỉ số của các nguyên tố trong M Các công thức từ (i) đến (vi) có thể được lý giải theo cách này.
Chúng ta chú trọng đến monoit tự do là các monoit con của A ∗ đối với bảng chữ cái nào đó Ví dụ, tập hợp các từ trong {a} ∗ có độ dài chẵn là một monoit con tự do Tương tự, tập hợp các từ trong {a} ∗ có độ dài không bằng 1 cũng là monoit con, nhưng không tự do, vì với a 5, ta có hai phân tích khác nhau Cuối cùng, tập hợp các từ trong {a,b} ∗ bắt đầu với a, cùng với từ rỗng, tạo thành một monoit con tự do, trong đó các từ nguyên tố có dạng ab i, với i ∈ N.
Bổ đề 2.1.5 khẳng định rằng nếu M là một monoit con của monoit tự do A ∗, và mọi từ không rỗng trong M có thể được phân tích duy nhất thành xy, với x là phần không khả quy trong M và y thuộc M, thì M là một monoit tự do.
Chúng ta chứng minh rằng mọi từ trong M độ dài n đều có phân tích bất khả quy duy nhất trong M bằng quy nạp Đối với trường hợp n=0, khẳng định này đúng Giả sử w là một từ trong M có độ dài n>0 và tất cả các từ trong M có độ dài nhỏ hơn n đều có phân tích bất khả quy duy nhất Nếu w có phân tích bất khả quy dạng w = x1 x2 xk, với x là phân tích bất khả quy trong M và y ∈ M, ta có x1 = x và x2 xk = y Theo giả thiết quy nạp, y cũng có phân tích bất khả quy duy nhất, do đó x2, , xk được xác định duy nhất.
Chúng ta nói rằng monoit con M của monoit tự do A ∗ thỏa mãn tiêu chuẩn Schutzenberger nếu nó có tính chất rằng với mọi p,q,vàrtrongA ∗ ,nếu p, pq,qr, vàrthuộcM thìqthuộcM.
Bổ đề 2.1.6 Giả sửMlà một monoit con của monoit tự doA ∗ Khi đóM tự do khi và chỉ khiM thỏa mãn tiêu chuẩn của Schutzenberger.
Giả sử M thỏa mãn tiêu chuẩn của Schutzenberger Cần chứng minh rằng giả thiết của Bổ đề 2.1.4 được thỏa mãn Cho w là từ không rỗng trong M, với w = xy, trong đó x không khả quy trong M và y ∈ M Thêm vào đó, giả thiết rằng w có thể phân tích thành xy.z, với y không rỗng, xy và z thuộc M Chỉ cần chứng minh rằng xy không bất khả quy.
Vì x,yz = v,xy và z thuộc M, theo tiêu chuẩn Schutzenberger, chúng ta có y∈M và điều này có nghĩa làxykhông phải là bất khả quy.
Tiếp theo, chúng ta giả sử rằng M tự do và giả sử rằng p, pq,qr và r thuộc
Giả sử \( w = pqr \), ta có thể phân tích duy nhất \( w = u_1 u_2 \ldots u_k \) thành tích các nguyên tố của \( M \) Các phân tích \( w = p.qr = pq.r \) cho thấy các phần tử của \( M \) Từ đó, với \( i \leq j \leq n \), ta có \( p = u_1 \ldots u_i \), \( q = u_{i+1} \ldots u_j \), và \( r = u_{j+1} \ldots u_k \) Do \( q \in M \), tiêu chuẩn Schutzenberger được thỏa mãn.
Giả sử u, v là các từ, ta nói rằng u chồng chéo với v nếu tồn tại các từ x và y sao cho chuỗi xuy = v và l(y) < l(u) (và l(x) < l(v)) Ví dụ, ab chồng chéo với bc vì ab.c = a.bc Từ a được gọi là không chồng chéo nếu nó không chồng chéo với chính nó; do đó, ab không chồng chéo nhưng aa chồng chéo với chính nó Giả sử w là từ trong monoit tự do A∗, ta ký hiệu Aw là tập hợp các từ trong A∗ bắt đầu với w, bao gồm cả từ rỗng Khi đó, Aw là một monoit con của A∗ Nếu A = {a} và w = a², thì Aw không tự do vì Aw là tập hợp các từ trong {a}∗ có độ dài không bằng 1 Ngược lại, nếu A = {a, b} thì A_w dễ thấy là tự do.
Bổ đề 2.1.7 Monoit conA w của monoit tự do A ∗ là tự do khi và chỉ khi wkhông chồng chéo.
Để chứng minh điều kiện đủ, chúng ta giả sử rằng không có sự chồng chéo Theo tiêu chuẩn của Schutzenberger, nếu p, pq, qr và r trong Aw và r không rỗng, thì do qr và r đều bắt đầu với w, và w không chồng chéo, nên l(q) ≥ l(w), điều này dẫn đến q ∈ Aw Để chứng minh điều kiện cần, nếu w chồng chéo, thì Aw không tự do Giả sử w chồng chéo với tồn tại t, u và v mà t = wu = vw và v (và do đó u) ngắn hơn w Chúng ta có thể chỉ ra rằng wt có hai phân tích bất khả quy khác nhau trong Aw Bất kỳ từ nào trong Aw không phải là bất khả quy đều có độ dài ít nhất bằng hai lần độ dài của w, vì vậy wuv và wvl là bất khả quy Do đó, w.uv và w.vl là hai phân tích bất khả quy của Aw, dẫn đến việc Aw không tự do Tương tự, nếu u không chồng chéo với v, thì monoit con của A* gồm các từ bắt đầu với uv và kết thúc với v là tự do.
Các đồng nhất thức Fibonacci
Hợp thành của một số là cách biểu diễn số đó dưới dạng tổng của các số nguyên dương Mỗi số nguyên dương trong tổng này được gọi là thành phần của hợp thành.
Hợp thành Fibonacci được định nghĩa là một hợp thành với các thành phần 1 và 2, do đó tập hợp của tất cả các hợp thành Fibonacci là monoit tự do {1,2}∗ Hầu hết các kết quả trình bày dưới đây là hệ quả từ sự kiện rằng số có Fn+1 hợp thành Fibonacci Áp dụng hàm trọng số ω(1) = 1 và ω(2) = 2 cho monoit tự do này, cùng với sự tồn tại của Fn+1 hợp thành, chúng ta có thể xác định hàm sinh.
1−x−x 2 , điều này tương đương với (2.2).
Chứng minh (i)-(vi) và các công thức tương tự khác được dựa trên monoit con của monoit tự do của các hợp thành Fibonacci.
Chúng ta sẽ xem xét monoit {1,2} 1 của các hợp thành Fibonacci bắt đầu với 1, bao gồm cả hợp thành Fibonacci Theo Bổ đề 2.1.7, monoit này là tự do, và các nguyên tố trong monoit này có dạng 1 2^i với i ≥ 0 Do đó, hàm sinh của các số nguyên tố trong monoit tự do này được biểu diễn bởi ∑ ∞ i=0 x^(2i+1).
Từ đó suy ra rằng, nếusn là số các hợp thành Fibonacci củan bắt đầu với 1, vớis 0 =1thì
Số các hợp thành Fibonacci của n bắt đầu với 1 tương đương với số hợp thành Fibonacci của n−1 Do đó, với n > 0, số các hợp thành của n với thành phần lẻ bằng số hợp thành của n−1, tức là Fn Kết quả này đã được Hoggatt và Hoggatt cùng Lind đưa ra lần đầu tiên.
Mục tiêu của chúng ta là chứng minh một cách đơn giản về sự kiện này Giả sử rằng clà hợp thành Fibonacci của n−1, khi đó 1clà hợp thành Fibonacci củan, có thể được biểu diễn duy nhất dưới dạng 1 2 i 1 1 2 i 2 1 2 i k Hợp thành tương ứng của n với thành phần lẻ là 1 + 2i 1, 1 + 2i 2, , 1 + 2i k Chúng ta có thể áp dụng phân tích tương tự khi hoán đổi vai trò của 1 và 2, từ đó thấy rằng số hợp thành Fibonacci củan bắt đầu với 2 bằng với số hợp thành của n với tất cả các thành phần lớn hơn 1 Kết quả tương tự cũng đúng cho hợp thành với tập hợp tùy ý gồm hai thành phần.
Giả sử p và q là hai số nguyên phân biệt Khi đó, số hợp thành của n - p với thành phần p sẽ bằng số hợp thành của n với các thành phần dạng p + qi, trong đó i thuộc tập số tự nhiên N.
Chúng ta nhận thấy rằng việc thêm một thành phần p vào một hợp thành n−p với các thành phần p và q sẽ tạo ra một hợp thành mới bắt đầu bằng p Trong monoit tự do {p,q} ∗ p, các hợp thành có dạng p q i với các thành phần p và q bắt đầu bằng p Do đó, một song ánh từ các hợp thành có n > 0 bắt đầu bằng p đến các hợp thành có n với các thành phần dạng p + q i được thực hiện thông qua ánh xạ chuyển đổi p q i 1 p q i 2 p q i k thành hợp thành p + q i 1 p + q i 2 p + q i k Đồng nhất thức hàm sinh tương ứng với Mệnh đề 2.2.1 được xác định rõ ràng.
. Một cách tổng quát, chúng ta có thể chỉ ra với bất kìk≥1
1−x−x 2 là hàm sinh đối với monoit tự do.
Mệnh đề 2.2.2 Cố định một số nguyên k≥2 Monoit M của các hợp thành Fi- bonacci bắt đầu với 2 1 k−2 là một monoit tự do, các nguyên tố của nó có dạng
Hàm sinh cho các nguyên tố của M được biểu diễn dưới dạng x^k / (1 - x - x^2 + x^k) Trong đó, i là một số nguyên không âm và q có thể là rỗng hoặc là một chuỗi Fibonacci bắt đầu từ 2 mà không chứa 2^(1-k)-2 Điều này cung cấp một minh họa tổ hợp cho đồng nhất thức liên quan.
Theo Bổ đề 2.1.7, M là một monoit tự do, và các nguyên tố của M được mô tả chính xác trong mệnh đề Giả sử Q là một monoit của các hợp thành Fibonacci bắt đầu với 2 và không chứa 2^(1 k−2) Khi đó, Q cũng là một monoit tự do, với tập hợp các nguyên tố bao gồm các hợp thành 2^(1 i) với 0≤i≤k - 3 Do đó, hàm sinh cho Q là
1−x−x 2 +x k và hàm sinh cho các nguyên tố củaM là x k
Ta có điều cần chứng minh.
Vớik=2,Mlà monoit tự do của các hợp thành bắt đầu với2, và các số nguyên tố, như chúng ta đã biết trước đó, là có dạng2 1 i , vớii≥0.
Vớik=3, hàm sinh cho các nguyên tố củaM là x 3
∑ n=3 n−1 2 x n Điều này cho ta công thức
C(n) là tập hợp các hợp thành 1 ak của n Công thức này có thể được giải thích theo cách tổ hợp bằng cách chỉ ra có b(n−1)/2c nguyên tố của M với trọng số n Các nguyên tố có dạng 2^(i+1) * 2^j với i, j ∈ N Nếu một từ là hợp thành của n, thì i + 1 + 2(j + 1) = n, từ đó suy ra i = n − 2j − 3 Điều này cho thấy i là số nguyên không âm với j = 0, 1, , b(n/2)c − 1.
Có một cách giải thích đơn giản hơn cho (2.9) Thay vì sử dụng chuỗi Fibonacci bắt đầu từ 2 và 1, chúng ta sẽ xem xét chuỗi Fibonacci bắt đầu từ 1 và kết thúc với.
2 Chúng lập nên một monoit tự do mà các nguyên tố có dạng1 i 2 j , i, j ≥1, và trong số đó cób(n−1)/2ccó trọng sốn.
Trường hợp khik=2,3,4,5trong (2.8) là sự đặc biệt hóa của các đồng nhất thức:
, (2.12) mà chúng cũng có thể giải thích trong các thuật ngữ của monoit tự do.
Có một áp dụng thú vị khác của công thức này Lấya=b=xtrong (2.10), ta thấy rằng tổng các hợp thành của n, đối với n>0, là 2 n−1 Lấy a=b=x trong (2.11) ta được
Lấya=b=xtrong (2.12), và sử dụng sự kiện rằng x 3
Công thức (2.13) giải thích lý do tại sao ba giá trị khác không đầu tiên của Fn−1 tương ứng với ba lũy thừa đầu tiên của 2 Cụ thể, F3−1=1, F4−1=2, và F5−1=4 Điều này cho thấy rằng các số hạng này không được sinh ra từ những hợp thành với các thành phần lớn hơn 2.
3≤n