Luận văn Thạc sĩ Toán học: Dãy Fibonacci: Ước chung lớn nhất, hợp thành và đồng nhất thức

i

Mục lục

Mở đầu

1

1 Ước chung lớn nhất trong dãy nâng của dãy Fibonacci

3

1.1 Một số tính chất cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

6

1.2 Dãy số fn(1) .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

8

1.3 Dãy số ( fn(2)) .

. . . . . . . . . . . . . . . . . .

10

1.4 Dãy số ( fn(−1)), ( fn(−2)) và (ln(1))

1.5 Chứng minh Định lí 1.1.3 và Định lí 1.1.4 . . . . . . . . . . . . . . . .

11

2 Hợp thành của các số Fibonacci

14

2.1 Monoit tự do .

. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2 Các đồng nhất thức Fibonacci . . . . . . . . . . . . . . . . . . . . . . .

20

Tài liệu tham khảo

34

ii

Lời cảm ơn

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 GS.TSKH. Hà Huy Khoái (Trường Đại học

Thăng Long). 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à nghiên cứu.

Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể Lớp B, cao học

Toán khóa 8 (2014 - 2016) đã động viên và giúp đỡ tác giả rất nhiều trong suốt

quá trình học tập.

Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải

Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Nguyễn Đức Cảnh,

Huyện Kiến Thụy, Thành phố Hải Phòng đã tạo điều kiện cho tác giả hoàn thành

tốt nhiệm vụ học tập và công tác của mình.

Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến bố mẹ và

đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả hoàn thành

tốt luận văn này.

1

Mở đầu

Số học là một trong những lĩnh vực cổ xưa nhất của Toán học, và cũng là lĩnh

vực tồn tại nhiều nhất những bài toán, những giả thuyết chưa có câu trả lời. Trên

con đường tìm kiếm lời giải cho những giả thuyết đó, nhiều tư tưởng lớn, nhiều lí

thuyết lớn của toán học đã nẩy sinh. Hơn nữa, trong những năm gần đây, Số học

không chỉ là một lĩnh vực của toán học lí thuyết, mà còn là có rất nhiều ứng dụng,

đặc biệt trong lĩnh vực bảo mật thông tin.

Dãy 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 hai phần tử trước nó.

Chúng ta cũng đã biết rằng, các số Fibonacci tham gia vào nhiều vấn đề của

toán học đến nỗi từ nhiều năm nay, có một tạp chí toán học chỉ chuyên dành nghiên

cứu các số Fibonacci.

Từ thực tiễn đó, tôi chọn nghiên cứu đề tài “Dãy Fibonacci: Ước chung lớn

nhất, hợp thành và đồng nhất thức” làm luận văn thạc sĩ của mình.

Chúng tôi bỏ qua việc trình bày những tính chất cơ bản của dãy Fibonacci, vì

đã có nhiều tài liệu đề cập đến. Ở đây chỉ chú trọng giới thiệu hai kết quả nghiên

cứu gần đây về ước chung lớn nhất của các số hạng trong dãy nâng Fibonacci, và

về hợp thành của các số Fibonacci, tức là việc biểu diễn số Fibonacci dưới dạng

tổng các số nguyên dương. Đây là những vấn đề được quan tâm nghiên cứu trong

lý thuyết số.

• Chương 1. Ước chung lớn nhất trong dãy nâng của dãy Fibonacci được dành

2

để trình bày về dãy nâng Fibonacci, là một mở rộng của dãy Fibonacci cổ

điển. Nếu như đối với dãy Fibonacci cổ điển, ước chung lớn nhất của hai số

hạng liên tiếp luôn bằng 1, thì với dãy nâng Fibonacci, điều này không còn

đúng nữa. Các kết quả trình bày trong chương này chỉ ra những lớp dãy nâng

Fibonacci mà ước chung lớn nhất nói trên là bị chặn.

• Chương 2. Hợp thành của các số Fibonacci trình bày về hợp thành của các

số Fibonacci. Một số công thức cho hợp thành của số Fibonacci sẽ được

chứng minh trong chương này. Phương pháp tiếp cận ở đây là sử dụng các

monoit tự do, lập nên bởi các hợp thành với phép toán ghép.

Thái Nguyên, ngày 27 tháng 5 năm 2016

Tác giả

Đỗ Đại Thanh

3

Chương 1

Ước chung lớn nhất trong dãy nâng

của dãy Fibonacci

1.1 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ởi F1 = 1, F2 = 1 và

với n ≥ 3. Fn = Fn−2 + Fn−1,

Định nghĩa 1.1.2. Dãy Lucas là dãy số xác định bởi L1 = 1, L2 = 3 và

với n ≥ 3. Ln = Fn−2 + 3Fn−1,

Dãy Fibonacci tổng quát được xác định bởi G1 = α, G2 = β , và

với n ≥ 3. Gn = αFn−2 + β Fn−1,

Nếu α = β = 1, thì dãy Fibonacci tổng quát Gn là dãy Fibonacci Fn.

Nếu α = 1 và β = 3, thì dãy Fibonacci tổng quát Gn là dãy Lucas Ln.

Xét dãy (Fn + a), với a là số nguyên nào đó. Ta gọi đó là dãy nâng Fibonacci.

Các phần tử liên tiếp của dãy Fibonacci là những số nguyên tố cùng nhau, nhưng

với dãy nâng Fibonacci thì điều này không còn đúng nữa. Năm 1971, Hoggatt đã

lưu ý rằng

gcd(F4n+1 + 1, F4n+2 + 1) = L2n,

gcd(F4n+1 − 1, F4n+2 − 1) = F2n,

4

gcd(F4n+3 − 1, F4n+4 − 1) = L2n+1.

Nghĩa là, các phần tử liên tiếp của dãy nâng Fibonacci bởi ±1 không phải luôn

luôn là những số nguyên tố cùng nhau. Nếu đặt

fn(a) = gcd(Fn + a, Fn+1 + a)

thì ( fn(0)) là dãy không đổi 1, 1, 1, . . . , nhưng ( fn(±1)) là không bị chặn.

Năm 2003 Hernández và Lucas đã chứng minh rằng có một số không đổi c mà

gcd(Fm + a, Fn + a) > ecm,

đúng đối với vô hạn các cặp số nguyên dương m > n.

Trong luận văn này, chúng ta sẽ thấy rằng ( fn(a)) bị chặn nếu a (cid:54)= ±1. Cụ thể,

chúng ta sẽ chứng minh hai định lý sau.

Định lí 1.1.3. Với mọi số nguyên (α), (β ), n và a với α 2 + (α.β ) − β 2 − a2 (cid:54)= 0,

chúng ta có

(1.1) gcd(G2n−1 + a, G2n + a) ≤ (cid:12) (cid:12)α 2 + (α.β ) − β 2 − a2(cid:12) (cid:12) .

Định lí 1.1.4. Với mọi số nguyên (α), (β ), n và a với α 2 + (α.β ) − β 2 + a2 (cid:54)= 0,

chúng ta có

(1.2) gcd(G2n + a, G2n+1 + a) ≤ (cid:12) (cid:12)α 2 + (α.β ) − β 2 + a2(cid:12) (cid:12) .

Giả sử α = β = 1 trong Đị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ên n và a

nếu a (cid:54)= ±1,

(cid:12)a2 − 1(cid:12) gcd(F2n−1 + a, F2n + a) ≤ (cid:12) (cid:12) , gcd(F2n + a, F2n+1 + a) ≤ a2 + 1.

5

Do đó, chúng ta kết luận rằng ( fn(a)) bị chặn nếu a (cid:54)= ±1. Và một hệ quả khác

ln(a) = gcd(Ln + a, Ln+1 + a)

chỉ nhận hữu hạn giá trị.

Hệ quả 1.1.6. Với số nguyên n và a, ta có

gcd(L2n−1 + a, L2n + a) ≤ a2 + 5, (cid:12)a2 − 5(cid:12) gcd(L2n + a, L2n+1 + a) ≤ (cid:12) (cid:12) .

Giả sử α = 1 và β = 3 trong Định lí 1.1.3 và Định lí 1.1.4. Chúng ta kết luận

rằng ln(a) bị chặn đối với số nguyên a tuỳ ý.

Trong phần tiếp theo, chúng ta sẽ suy ra được hai bổ đề cơ bản. Từ đó, chúng

ta xác định được fn(1), fn(2), fn(−1), fn(−2) và ln(1), trong 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ên n, k và a

(1.3) gcd(Gn + aFk, Gn−1 − aFk+1) = gcd(Gn−2 + aFk+2, Gn−3 − aFk+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(Gn + aFk, Gn−1 − aFk+1) = gcd(Gn + aFk − (Gn−1 − aFk+1), (Gn−1 − aFk+1))

= gcd(Gn−2 + aFk+2, Gn−1 − aFk+1)

= gcd(Gn−2 + aFk+2, Gn−1 − aFk+1 − (Gn−2 + aFk+2))

= gcd(Gn−2 + aFk+2, Gn−3 − aFk+3).

Bổ đề được chứng minh.

Bổ đề 1.1.8. Với số nguyên m, k và a,

(1.4) gcd(Gm + a, Gm+1 + a) = gcd(Gm−(2k) + aF2k−1, Gm−(2k+1) − aF2k)

6

Chứng minh. Chúng ta rút gọn gcd(Gm + a, Gm+1 + a),

gcd(Gm + a, Gm+1 + a) = gcd(Gm + a, Gm+1 + a − (Gm + a))

= gcd(Gm + a, Gm−1).

Vì F−1 = 1, và F0 = 0, chúng ta có thể viết

= gcd(Gm + a, Gm+1 + a) = gcd(Gm + aF−1, Gm−1 − aF0),

và áp dụng (1.3) k lần để rút ra kết quả.

Lưu ý rằng, ta gọi dãy số {Fn + k} là dãy số fn(k).

1.2 Dãy số fn(1)

Định lí 1.2.1. Với mọi số nguyên n, chúng ta có

(1.5) gcd(F4n−1 + 1, F4n + 1) = F2n−1,

2, nếu n ≡ 1 mod 3,   (1.6) gcd(F4n + 1, F4n+1 + 1) =

nếu ngược lại, 1, 

(1.7) gcd(F4n+1 + 1, F4n+2 + 1) = L2n,

2, nếu n ≡ 2 mod 3,   (1.8) gcd(F4n+2 + 1, F4n+3 + 1) =

nếu ngược lại. 1, 

Chứng minh. Giả sử m = 4n − 1, k = n, và a = 1 trong (1.4) :

gcd(F4n−1 + 1, F4n + 1) = gcd(F2n−1 + F2n−1, F2n−2 − F2n)

= gcd(2F2n−1, −F2n−1)

= F2n−1,

cho ta (1.5).

Giả sử m = 4n + 1, k = n, và a = 1 trong (1.4) :

gcd(F4n+1, F4n+2 + 1) = gcd(F2n+1 + F2n−1, F2n + F2n)

7

= F2n+1 + F2n−1

= L2n,

cho ta (1.7).

Giả sử m = 4n, k = n, và a = 1 trong (1.4) :

gcd(F4n + 1, F4n+1 + 1) = gcd(F2n + F2n−1, F2n−1 + F2n)

= gcd(F2n+1, −F2n−2).

Vì gcd(Fqn+r, Fn) = gcd(Fn, Fr) cho các số nguyên q, r và n. Điều này cho ta

gcd(F4n+1, F4n+1 + 1) = gcd(F2n−2, F3).

Vì gcd(Fk, Fr) = gcd(Fgcd(k,r)) cho các số nguyên k và r,

gcd(F4n + 1, F4n+1 + 1) = gcd(F2n−2, F3)

= Fgcd(2n−2,3)

nếu n ≡ 1 mod 3, F3 = 2,   =

 nếu ngược lại, F1 = 1,

là (1.6).

Giả sử m = 4n + 2, k = n + 1 và a = 1 trong (1.4)

gcd(F4n+2 + 1, F4n+3 + 1) = gcd(F2n + F2n+1, F2n−1 − F2n+2)

= gcd(F2n+2, F2n−1 − F2n+2)

= gcd(F2n+2, F2n−1)

= gcd(F3, F2n−1)

= Fgcd(3,2n−1)

nếu n ≡ 1 mod 3, F3 = 2,   =

 nếu ngược lại, F1 = 1,

đó là (1.8).

8

1.3 Dãy số (fn(2))

Định lí 1.3.1. Với bất kì số nguyên n, chúng ta có

(1.9) gcd(F4n−1 + 2, F4n + 2) = 1,

(1.10) gcd(F4n + 2, F4n+1 + 2) = 1,

3, nếu n ≡ 0 mod 2,   (1.11) gcd(F4n+1 + 2, F4n+2 + 2) =

1, nếu n ≡ 1 mod 2,

5, nếu n ≡ 2 mod 5,    (1.12) gcd(F4n+2 + 2, F4n+3 + 2) =

nếu ngược lại. 1, 

Chứng minh. Giả sử m = 4n − 1, k = n và a = 2 trong (1.4):

gcd(F4n−1 + 2, F4n + 2) = gcd(F2n−1 + 2F2n−1, F2n−2 − 2F2n)

= gcd(3F2n−1, F2n−1 + F2n)

= gcd(3F2n−1, F2n+1).

Vì

gcd(a, bc) = gcd(a, gcd(a, b)c) và gcd(F2n−1 + F2) = 1,

ta có

gcd(F4n−1 + 2, F4n + 2) = gcd(3gcd(F2n−1, F2n+1), F2n+1)

= gcd(3, F2n+1) = gcd(F4, F2n+1)

= Fgcd(4,2n+1) = F1 = 1,

là (1.9).

Giả sử m = 4n, k = n, và a = 2 trong (1.4) :

gcd(F4n+2, F4n+1 + 2) = gcd(F2n + 2F2n−1, F2n−1 − 2F2n)

= gcd(F2n−1 + F2n+1, F2n − F2n−2)

= gcd(L2n, L2n−1) = 1,

9

là (1.10).

Giả sử m = 4n + 1, k = n, và a = 2 trong (1.4) :

gcd(F4n+1 + 2, F4n+2 + 2) = gcd(F2n+1 + 2F2n−1, F2n − 2F2n)

= gcd(F2n+1 + 2F2n−1 + F2n, F2n)

= gcd(3F2n+1, F2n)

= gcd(3, F2n) = gcd(F4), F2n)

= Fgcd(4,2n)

nếu n ≡ 0 mod 2, F4 = 3,   =

 nếu n ≡ 1 mod 2, F1 = 1,

là (1.11).

Giả sử m = 4n + 2, k = n, và a = 2 trong (1.4) :

gcd(F4n+2 + 2, F4n+3 + 2) = gcd(F2n+2 + 2F2n−1, F2n+1 − 2F2n)

= gcd(F2n+2 + 2F2n−1, −F2n + F2n−1)

= gcd(F2n+2 + 2F2n−1, −F2n−2)

= gcd(F2n−2, F2n+2 + 2F2n).

Từ

F2n+2 + 2F2n = F2n+1 + 3F2n = 4F2n + F2n−1,

ta có

gcd(F4n+2 + 2, F4n+3 + 2) = gcd(F2n−2, 4F2n + F2n−1)

= gcd(F2n−2, 5F2n)

= gcd(F2n−2, 5 gcd(F2n−2, F2n)

= gcd(F2n−2, 5) = gcd(F2n−2, F5)

= Fgcd(2n−2,5)

nếu n ≡ 1 mod 5, F5 = 2,   =

 nếu ngược lại, F1 = 1,

10

đó là (1.12).

1.4 Dãy số (fn(−1)), (fn(−2)) và (ln(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ên n, chúng ta có

gcd(F4n−1 − 1, F4n − 1) = L2n−1,

2, nếu n ≡ 1 mod 3,   gcd(F4n − 1, F4n+1 − 1) =

nếu ngược lại, 1, 

gcd(F4n+1 − 1, F4n+2 − 1) = F2n,

2, nếu n ≡ 2 mod 3,   gcd(F4n+2 − 1, F4n+3 − 1) =

nếu ngược lại. 1, 

Định lí 1.4.2. Với bất kì số nguyên n, chúng ta có

5, nếu n ≡ 4 mod 5, gcd(F4n−1 − 2, F4n − 2) = 1,   gcd(F4n − 2, F4n+1 − 2) =

nếu ngược lại, 

1, nếu n ≡ 0 mod 2, 1,   gcd(F4n+1 − 2, F4n+2 − 2) =

3, nếu n ≡ 1 mod 2, 

gcd(F4n+2 − 2, F4n+3 − 2) = 1.

11

Định lí 1.4.3. Với bất kì số nguyên n, chúng ta có



3, nếu n ≡ 0 mod 6,

1, nếu n ≡ 1 mod 6,

6, nếu n ≡ 2 mod 6, gcd(L4n−1 + 1, L4n + 1) =

1, nếu n ≡ 3 mod 6,

3, nếu n ≡ 4 mod 6,

2, nếu n ≡ 5 mod 6,  

4, nếu n ≡ 1 mod 3,   gcd(L4n + 1, L4n+1 + 1) =

nếu ngược lại, 

2, nếu n ≡ 0 mod 3, 1,   gcd(L4n+1 + 1, L4n+2 + 1) =

nếu ngược lại, 1,

4, nếu n ≡ 2 mod 3,    gcd(L4n+2 + 1, L4n+3 + 1) =

nếu ngược lại. 1, 

1.5 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 − 1 và k = n trong (1.4) :

gcd(G4n−1 + a, G4n + a)

= gcd(G2n−1 + aF2n−1, G2n−2 + aF2n)

= gcd(αF2n−3 + β F2n−2 + aF2n−1, αF2n−4 + β F2n−3 − aF2n).

Sử dụng quan hệ truy hồi cho Fn, giả sử

an = αF2n−3 + β F2n−1 + aF2n−1 = (a + α)F2n−3 + (a + β )F2n−2

12

và

bn = αF2n−4 + β F2n−3 − aF2n = (−a − α + β )F2n−3 + (α − 2a)F2n−2.

Vì gcd(an, bn) chia hết γan + θ bn, với bất kì số nguyên γ và θ , và

(α + a)bn − (−α + β − a)an = (α 2 + αβ − β 2 − a2)F2n−2,

(α − 2a)an − (β + a)bn = (α 2 + αβ − β 2 − a2)F2n−3.

Chúng ta thấy rằng, nếu α 2 + αβ − β 2 − a2 (cid:54)= 0 thì ước chung lớn nhất của hai số

là

(cid:12)α 2 + αβ − β 2 − a2(cid:12) (cid:12) (cid:12) .

Vì vậy gcd(an, bn) chia hết α 2 + αβ − β 2 − a2. Nghĩa là

gcd(G4n−1 + a, G4n + a) ≤ (cid:12) (cid:12)α 2 + αβ − β 2 − a2(cid:12) (cid:12) .

Nếu chúng ta giả sử, m = 4n + 1 và k = n trong (1.4) bằng cách tương tự, chúng ta

có

gcd(G4n+1 + a, G4n+2 + a) ≤ (cid:12) (cid:12)α 2 + αβ − β 2 − a2(cid:12) (cid:12) .

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 = 4n và k = n trong (1.4):

gcd(G4n + a, G4n+1 + a) = gcd(G2n + aF2n−1, G2n−1 − aF2n)

= gcd(αF2n−2 + β F2n−1 + aF2n−1, αF2n−3 + β F2n−2 + aF2n).

Sử dụng quan hệ truy hồi cho Fn, giả sử

an = αF2n−2 + β F2n−1 + aF2n−1 = αF2n−2 + (β + α)F2n−1

và

bn = αF2n−3 + β F2n−2 + aF2n = (−α + β − a)F2n−2 + (α − a)F2n−1.

13

Vì gcd(an, bn) chia hết γan + θ bn, với bất kì số nguyên γ và θ , và

(α − a)an − (a + β )bn = (α 2 + αβ − β 2 + a2)F2n−2,

αbn − (β − α − a)an = (α 2 + αβ − β 2 − a2)F2n−1.

số là Chúng ta thấy rằng, nếu α 2 + αβ − β 2 − a2 (cid:54)= 0, thì ước chung lớn nhất của hai (cid:12)α 2 + αβ − β 2 + a2(cid:12) (cid:12) (cid:12) . Vì vậy gcd(an, bn) chia hết α 2 + αβ − β 2 + a2. Nghĩa

là

gcd(G4n + a, G4n+1 + a) ≤ (cid:12) (cid:12)α 2 + αβ − β 2 + a2(cid:12) (cid:12) .

Nếu chúng ta giả sử m = 4n + 2 và k = n trong (1.4) bằng cách tương tự, ta có

gcd(G4n+2 + a, G4n+3 + a) ≤ (cid:12) (cid:12)α 2 + αβ − β 2 + a2(cid:12) (cid:12) .

Ta có điều phải chứng minh.

14

Chương 2

Hợp thành của các số Fibonacci

2.1 Monoit tự do

Định nghĩa 2.1.1. Một tập hợp khác rỗng G được trang bị một phép toán hai ngôi

∗ là một monoid nếu và chỉ nếu

(i) (a ∗ b) ∗ c = a ∗ (b ∗ c), ∀a, b, c ∈ G,

(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 con N của

M mà nó đóng trong phép toán monoid và chứa phần tử đơn vị e của M. Ký hiệu,

N là monoid con của M nếu N ⊆ M, x ∗ y ∈ N, ∀x, y ∈ N và e ∈ N.

Định nghĩa 2.1.3. Monoid tự do trên một tập hợp là một monoid mà các phần tử

của nó là tất cả các dãy hữu hạn gồm không (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à với phần tử đơn vị duy nhất là

dãy rỗng.

Chúng ta nghiên cứu công thức cho số Fibonacci như một tổng của các thành

phần. Số Fibonacci Fn+1 như là số các cách biểu diễn số n thành tổng của các số

1 và 2. Các tổng với thành phần là 1 và 2 lập nên một monoit tự do với phép toán

ghép và các công thức của chúng ta phát sinh từ monoit con của monoit tự do này.

Một hợp thành của số nguyên n là dãy a1 a2 . . . ak số nguyên dương, được gọi

là các phần của hợp thành, với tổng bằng n.

15

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) Fn+1 là số các hợp thành của n với các phần bằng 1 hoặc 2.

(ii) Fn−1 là số các hợp thành của n với các phần lớn hơn 1.

(iii) Fn là số các hợp thành của n với các thành các phần lẻ.

(iv) F2n = ∑ a1a2 . . . ak.

(v) F2n−2 = ∑(2a1−1 − 1) . . . (2ak−1 − 1).

(vi) F2n = ∑ 2#{i:ai=1}.

Từ nay về sau, ta gọi C(n) là tập hợp các hợp thành a1 . . . ak của n.

Bổ đề 2.1.4. Giả sử u1, u2, u3, . . . là dãy số tuỳ ý. Khi đó tổng

ua1 ua2 . . . uak

∑ a∈C(n)

là hệ số của xn trong (cid:32) (cid:33)−1

∞ ∑ i=1

, 1 − (2.1) uixi

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.

1

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

1−x−x2 = (1 − x − x2)−1

(i’)

1−x−x2 = (1 − x2 − x3 − x4 − . . .)−1

(ii’) 1 + x2

1−x−x2 = (1 − x − x3 − x5 − . . .)−1

(iii’) 1 + x

1−3x+x2 = (1 − x − 2x2 − 3x3 − . . .)−1

(iv’) 1 + x

16

1−3x+x2 = (1 − x2 − 3x3 − 7x4 − 15x5 − . . .)−1

1−x

(v’) 1 + x2

1−3x+x2 = (1 − 2x − x2 − x3 − x4 − x5 − . . .)−1

(vi’)

và các công thức

(2.2) Fnxn =

(2.3) F2nxn =

∞ ∑ n=0 ∞ ∑ n=0 ∞ ∑ n=0

(2.4) F2n+1xn = x 1 − x − x2 , x 1 − 3x + x2 , 1 − x 1 − 3x + x2 .

Công thức (2.2) suy ra dễ dàng từ quan hệ truy hồi Fibonacci Fn = Fn−1 + Fn−2.

Với (2.3) và (2.4), chúng ta có

∞ ∑ n=0

Fnxn = 1 + x − x2 1 + x − x2

=

= x (2.5) x 1 − x − x2 · x + x2 − x3 1 − 3x2 + x4 1 − x2 1 − 3x2 + x4 + x2 1 − 3x2 + x4 .

Khi đó (2.3) và (2.4) được suy ra bằng cách loại lũy thừa lẻ của x từ (2.5).

Giả sử A là một tập hợp, chúng ta có thể gọi là Bảng chữ cái. Giả sử A∗ là tập

hợp các từ (dãy hữu hạn các phần tử của A). Khi đó với phép toán ghép, A là một monoit (nửa nhóm có đơn vị), mà đơn vị là từ rỗng. Chúng ta gọi A∗ là một monoit

tự do trên A. Độ dài l(x) của một phần tử x = a1 a2 . . . ak, mà mỗi ai trong A, là k.

Tổng quát hơn, một monoit tự do M là một monoit đẳng cấu với monoit tự do có dạng A∗. Vì vậy nếu M là một nửa nhóm tự do, thì tồn tại tập hợp con P của M

mà mỗi phần tử của M có một sự phân tích duy nhất thành tích các phần tử của P.

Chúng ta gọi P là tập hợp nguyên tố của M ( dễ thấy P là tập hợp duy nhất).

Hàm trọng số trên nửa nhóm tự do M là một hàm ω : M −→ N , mà N là tập

hợp các số nguyên không âm, với tính chất ω(m1m2) = ω(m1) + ω(m2) đối với

17

mọi m1, m2 ∈ M và ω(m) = 0 khi và chỉ khi m là phần tử đơn vị của M. Rất dễ

để nhận ra rằng 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à monoit con tuỳ ý của một monoit tự do, chúng ta có thể gọi phần tử

p của L là bất khả quy (trong L) nếu p không phải là phần tử đơn vị của M và p

không thể biểu diễn được như tích của hai phần tử khác đơn vị của L. ( Lưu ý rằng

tính bất khả quy của p phụ thuộc vào cả p và L) Rõ ràng rằng 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. Nếu L là một monoit tự do, thì phân tích này luôn luôn là duy nhất và

các phần tử bất khả quy 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, thì khi đó ánh xạ m (cid:55)→ xω(m) là một 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, và việc phân tích duy nhất trong M cho ta một đồng nhất thức quen biết đối

với các chuỗi luỹ thừa hình thức

xω(m))−1 (2.6) xω(m) = (1 − ∑

∑ m∈M

p∈P

trong đó P là tập hợp các nguyên tố của M. Một cách tương đương, số các từ trong

M có trọng số n là tổng

ua1 ua2 . . . uak,

∑ a∈C(n)

trong đó ui là số các nguyên tố của M có trọng số i. Chúng ta sẽ thấy rằng các công

thức (i) − (vi) có thể được giải thích theo cách này.

Chúng ta đặc biệt quan tâm đến monoit tự do là các monoit con của A∗ đối với bảng chữ cái A nào đó. Ví dụ, tập hợp các từ trong {a}∗ có độ dài chẵn là monoit con của {a}∗ . Tập hợp các từ trong {a}∗ có độ dài không bằng 1 cũng là monoit con, nhưng nó không tự do, vì đối với a5 ta có hai phân tích, a5 = a2.a3 = a3.a2 thành những từ mà không thể phân tích thêm. Tập hợp các từ trong {a, b}∗ mà bắt

đầu với a, cùng với từ rỗng, là một monoit con tự do trong đó các từ nguyên tố có dạng abi, với i ∈ N.

18

Bổ đề 2.1.5. Giả sử M là một monoit con của monoit tự do A∗ với tính chất mọi

từ không rỗng trong M đều có phân tích duy nhất thành xy, trong đó mà x bất khả

quy trong M và y ∈ M. Khi đó M tự do.

Chứng minh. Chúng ta chứng minh bằng quy nạp theo n rằng mọi từ trong M độ

dài n có phân tích bất khả quy duy nhất trong M. Sự khẳng định đúng cho n = 0.

Bây giờ giả sử rằng w là một từ trong M độ dài n > 0 và tất cả các từ trong M độ

dài nhỏ hơn n có phân tích bất khả quy duy nhất. Giả sử w = x1x2 . . . xk là phân

tích bất khả quy của w. Vì w có phân tích duy nhất dạng w = xy, trong đó x bất khả

quy trong M và y ∈ M, chúng ta có x1 = x và x2 . . . xk = y. Theo giả thiết quy nạp

y có phân tích bất khả quy duy nhất, vì vậy 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à r trong A∗, nếu p, pq, qr,

và r thuộc M thì q thuộc M.

Bổ đề 2.1.6. Giả sử M là một monoit con của monoit tự do A∗. Khi đó M tự do khi

và chỉ khi M thỏa mãn tiêu chuẩn của Schutzenberger.

Chứng minh. Trước tiên ta giả sử rằng, M thỏa mãn tiêu chuẩn của Schutzen-

berger. Chỉ cần chứng tỏ rằng giả thiết của Bổ đề 2.1.4 thoả mãn. Giả sử w là từ

không rỗng của M, và giả sử rằng w = xy trong đó x bất khả quy trong M và y ∈ M.

Giả thiết thêm rằng w có thể phân tích thành xy.z, trong đó 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à xy khô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

M. Giả sử w = pqr. Khi đó w có phân tích duy nhất w = u1u2 . . . uk thành tích các

nguyên tố của M. Các phân tích w = p.qr = pq.r thành tích các phần tử của M, suy

19

ra rằng với i ≤ j, nào đó, chúng ta có p = u1 . . . ui, q = ui+1 . . . u j, và r = u j+1 . . . uk,

và q ∈ M, vì vậy tiêu chuẩn Schutzenberger thoả mãn.

Giả sử u và v là các từ. Chúng ta nói rằng u chồng chéo v nếu tồn tại các từ x và

y sao cho ux = yv và l(y) < l(u)(và l(x) < l(v)). Ví dụ ab chồng chéo với bc bởi vì

ab.c = a.bc. Chúng ta gọi từ a của w không chồng chéo nếu nó không chồng chéo

với chính nó. Như vậy, 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∗. Chúng ta ký hiệu Aw là tập hợp các từ trong A∗ mà bắt đầu với w, cùng với từ rỗng. Khi đó Aw là một monoit con của A∗. Nếu A = {a} và w = a2, thì Aw là không tự do, vì Aw là tập hợp các từ trong {a}∗

có độ dài không bằng 1. Mặt khác, nếu A = {a, b} và w = ab thì Aw dễ thấy là tự

do.

Bổ đề 2.1.7. Monoit con Aw của monoit tự do A∗ là tự do khi và chỉ khi w không

chồng chéo.

Chứng minh. Trước tiên, chúng ta hãy chỉ ra rằng điều kiện là đủ. Giả sử w không

chồng chéo. Chúng ta sẽ chỉ ra rằng tiêu chuẩn của Schutzenberger thỏa mãn. Giả

sử rằng p, pq, qr, và r trong Aw và r là không rỗng. Khi đó vì 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 có nghĩa rằng, do qr bắt

đầu với w, nên q cũng vậy, và q ∈ Aw.

Để chứng minh điều kiện cần, chúng ta chỉ ra rằng nếu w chồng chéo thì Aw

không tự do. Giả sử rằng, w chồng chéo, vì vậy tồn tại t, u và v mà t = wu = vw

mà 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 mà không phải là bất khả quy

phải có độ dài ít nhất bằng hai lần độ dài của w, vì vậy wu và wv là bất khả quy. Do

đó w.wu và wv.w là hai phân tích bất khả quy của Aw, vì vậy Aw không tự do.

Tương tự, chúng ta có thể chỉ ra rằng 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 u và kết thúc với v là tự do.

20

2.2 Các đồng nhất thức Fibonacci

Ta nhắc lại rằng hợp thành của một số là một biểu diễn số đó dưới dạng tổng

những số nguyên dương. Mỗi số nguyên dương trong tổng gọi là thành phần của

hợp thành.

Chúng ta định nghĩa hợp thành Fibonacci của n là một hợp thành của n với các

thành phần 1 và 2. Do vậy 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ả của sự kiện nói rằng

số n có Fn+1 hợp thành Fibonacci.

Áp dụng (1.3) cho monoit tự do này với hàm trọng số ω(1) = 1, ω(2) = 2,

cùng với sự kiện tồn tại Fn+1 hợp thành của n, ta có hàm sinh

∞ ∑ n=0

Fn+1xn = 1 1 − x − x2 ,

đ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.

Bây giờ chúng ta hãy xem xét monoit {1, 2}1 của các hợp thành Fibonacci mà bắt đầu với 1 (bao gồm cả hợp thành Fibonacci ). Bằng Bổ đề 2.1.7, monoit này là tự do, và các nguyên tố là các hợp thành có 1 2i, với i ≥ 0. Vì vậy hàm sinh của

∞ ∑ i=0

x2i+1. các số nguyên tố trong monoit tự do này là

Từ đó suy ra rằng, nếu sn là số các hợp thành Fibonacci của n bắt đầu với 1,

với s0 = 1 thì

∞ ∑ n=0

∞ ∑ i=0

x2i+1)−1, (2.7) snxn = (1 −

và vế phải của (2.7) là hàm sinh cho hợp thành với thành phần lẻ. Nhưng số các

hợp thành Fibonacci của n bắt đầu với 1 là số hợp thành Fibonacci của n − 1, vì

vậy chúng ta thấy rằng với n > 0, số các hợp thành của n với thành phần lẻ bằng

với số các hợp thành của n − 1, tức là bằng Fn. Vì vậy (iii) đúng (Kết quả này được

đưa ra đầu tiên bởi Hoggatt và Hoggatt và Lind).

21

Mục tiêu của chúng ta là đưa ra chứng minh song ánh đơn giản của sự kiện

này. Giả sử rằng c là một hợp thành Fibonacci của n − 1, khi đó 1 c là hợp thành Fibonacci của n, bắt đầu với 1, nó có thể được biểu diễn duy nhất 1 2i11 2i2 . . . 1 2ik.

Khi đó hợp thành tương ứng của n với thành phần lẻ là 1 + 2i1 1 + 2i2 . . . 1 + 2ik.

Chúng ta có thể áp dụng phân tích tương tự với việc hoán đổi vai trò 1 và 2, và

chúng ta có thể thấy rằng số các hợp thành Fibonacci của n bắt đầu với 2 bằng với

số các hợp thành của n với tất cả các thành phần tử lớn hơn 1, và đó chính là (ii).

Một kết quả tương tự cũng đúng cho hợp thành với tập hợp tuỳ ý gồm hai thành

phần.

Mệnh đề 2.2.1. Giả sử p và q là hai số nguyên phân biệt. Khi đó với n ≥ p số các

hợp thành của n − p với thành phần p và q bằng số các hợp thành của n với các

thành phần dạng p + qi, với i ∈ N.

Chứng minh. Trước tiên, chúng ta lưu ý rằng thêm vào phía trước một thành phần

p của hợp thành n − p với các thành phần p và q sẽ cho một hợp thành của n bắt đầu với p. Trong monoit tự do {p, q}∗ p của các hợp thành với thành phần p và q bắt đầu với p, các số nguyên tố là hợp thành có dạng p qi. Vì vậy một song ánh từ

các hợp thành của n > 0 bắt đầu với p đến các hợp thành của n với các thành phần của dạng p + qi được cho bởi ánh xạ chuyển p qi1 p qi2 . . . p qik thành hợp thành

p + qi1 p + qi2 . . . p + qik.

Đồng nhất thức hàm sinh tương ứng với Mệnh đề 2.2.1 là

(cid:18) (cid:19)−1 . 1 + 1 − xp 1 − xp − xq = xp 1 − xq

Một cách tổng quát, chúng ta có thể chỉ ra với bất kì k ≥ 1

∞ ∑ n=0

1 + xk Fn+1xn = 1 + xk 1 − x − x2

là hàm sinh đối với monoit tự do.

22

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 1k−2 là một monoit tự do, các nguyên tố của nó có dạng

2 1k−21i q, trong đó i là một số nguyên không âm và q là rỗng hoặc là một hợp

thành Fibonacci bắt đầu với 2 và không chứa 2 1k−2. Hàm sinh cho các nguyên tố

của M là xk/(1 − x − x2 + xk), vì vậy ta có một minh hoạ tổ hợp cho đồng nhất thức

sau xk 1 + (2.8) 1 − x − x2 = (1 − xk 1 − x − x2 + xk )−1.

Chứng minh. Do Bổ đề 2.1.7, M là một monoit tự do, và dễ thấy các nguyên tố

của M đúng như đã mô tả 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 1k−2. Khi đó Q là một monoit tự do mà tập hợp các nguyên tố bao gồm các hợp thành 2 1i, với 0 ≤ i ≤ k - 3. Vì vậy

hàm sinh cho Q là

k−1 ∑ j=2

x j)−1 = (1 − 1 − x 1 − x − x2 + xk

và hàm sinh cho các nguyên tố của M là

. xk 1 − x 1 − x 1 − x − x2 + xk = xk 1 − x − x2 + xk .

Ta có điều cần chứng minh.

Với k = 2, M là monoit tự do của các hợp thành bắt đầu với 2, và các số nguyên

tố, như chúng ta đã biết trước đó, là có dạng 2 1i, với i ≥ 0.

Với k = 3, hàm sinh cho các nguyên tố của M là

x3 1 − x − x2 + x3 =

=

(cid:23) xn. = x3 (1 − x)2(1 + x) x3 + x4 (1 − x2)2 (cid:22)n − 1 ∞ ∑ 2 n=3

Điều này cho ta công thức

(cid:23) . . . (cid:23) , với n ≥ 2. (2.9) (cid:22)a1 − 1 2 (cid:22)ak − 1 2 Fn−2 = ∑ a∈C(n)

23

(Nhắc lại rằng C(n) là tập hợp các hợp thành a1 . . . ak của n.) Chúng ta có thể giải

thích công thức này một cách tổ hợp bằng cách chỉ ra có (cid:98)(n − 1)/2(cid:99) nguyên tố của M của trọng số n. Trong trường hợp này, các nguyên tố có dạng 2 1i+1 2 j với i, j ∈ N. Nếu một từ là hợp thành của n, thì khi đó i + 1 + 2( j + 1) = n. Vì vậy

i = n − 2 j − 3, và đây là số nguyên không âm với j = 0, 1, . . . , (cid:98)n/2(cid:99) − 1.

Có một diễn giải đơn giản hơn của (2.9). Thay cho các hợp thành Fibonacci

bắt đầu với 2 1, chúng ta xem xét hợp thành Fibonacci bắt đầu với 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ạng 1i 2 j, i, j ≥ 1, và

trong số đó có (cid:98)(n − 1)/2(cid:99) có trọng số n.

Trường hợp khi k = 2, 3, 4, 5 trong (2.8) là sự đặc biệt hóa của các đồng nhất

thức:

(cid:18) (cid:19)−1 , = 1 − 1 + (2.10) a 1 − a − b a 1 − b

(cid:19)−1 (cid:18) = , 1 + 1 − (2.11) ab (1 − a)(1 − b)

(cid:18) (cid:19)−1 = , 1 + 1 − (2.12) ab 1 − a − b a2b 1 − a − b a2b (1 − a)(1 − b − ab)

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ấy a = b = x trong (2.10), ta thấy rằng tổng các hợp thành của n, đối với n > 0, là 2n−1. Lấy a = b = x trong

(2.11) ta được

a∈C(n)

(a − 1) . . . (ak − 1), n ≥ 2. 2n−2 = ∑

Lấy a = b = x trong (2.12), và sử dụng sự kiện rằng

= x3 (1 − x)(1 − x − x2) x 1 − x

∞ ∑ n=1

= x 1 − x − x2 − (Fn − 1)xn

ta được

a∈C(n)

n ≥ 3 (2.13) (Fa1 − 1) . . . (Fak − 1), 2n−3 = ∑

24

(số hạng khác không sinh ra từ những hợp thành với các thành phần lớn hơn 2).

Công thức (2.13) "giải thích" tại sao ba giá trị khác không đầu tiên của Fn − 1 là

ba luỹ thừa đầu tiên của 2, ví dụ F3 − 1 = 1, F4 − 1 = 2, F5 − 1 = 4), bởi vì với 3 ≤ n < 6 chỉ có một số hạng khác không trong tổng (2.13). Điều Fn − 1 = 2n−3

đối với 3 ≤ n < 6 cũng có thể dễ dàng nhận thấy từ công thức

= x 1 − x − x2 − x 1 − x x3 1 − 2x + x3 .

Lấy a = x, b = xm trong (2.11) ta được một tổng quát hóa của (2.9).

Mệnh đề 2.2.3. Cố định m ≥ 1 và định nghĩa số rn bởi

∞ ∑ n=0

rnxn = 1 1 − x − xm .

Khi đó với n ≥ m + 1, ta có

(cid:23) (cid:23) . . . , (cid:22)a1 − 1 m (cid:22)ak − 1 m rn−m−1 = ∑ a∈C(n)

trong đó các số hạng khác không chỉ xuất phát từ các hợp thành có thành phần ít

nhất là m + 1.

Chứng minh. Bởi (2.11) với a = x, b = xm, ta có

∞ ∑ n=m+1

1 + rn−m−1xn = 1 + xm+1 1 − x − xm

(cid:19)−1 (cid:18) . = 1 − xm+1 (1 − x)(1 − xm)

Chúng ta có

= (xm+1) xm+1 (1 − x)(1 − xm) 1 + x + . . . + xm−1 (1 − xm)2

= x(xm + xm+1 + . . . + x2m−1)(1 + 2xm + 3x2m + . . .)

∞ ∑ n=1

= (cid:23) xn, (cid:22)n − 1 m

suy ra điều phải chứng minh.

25

Không khó để đưa ra cách giải thích tổ hợp cho Mệnh đề 2.2.3. Số rn đếm số

hợp thành của n với thành phần 1 và m, vì vậy đối với n ≥ m+1 , rn−m−1 là số

các hợp thành của n bắt đầu với 1 và kết thúc với m. Các hợp thành này lập nên một monoit tự do mà trong đó các nguyên tố có dạng 1i m j, khi i, j ≥ 1, và có

(cid:98)(n − 1)/m(cid:99) số trong chúng có trọng số n.

Để giải thích kết quả (iv) - (vi) của Mục 1, chúng ta cần xem xét các hợp thành

Fibonacci của không chỉ của các số chẵn, hoặc không chỉ các số lẻ. Tổng quát hơn,

cho m và i, chúng ta có thể xem xét hợp thành Fibonacci của các số đồng dư i

modulo m.

Bổ đề 2.2.4. Giả sử M là một monoit tự do với hàm trọng và giả sử m là một số

nguyên dương, khi đó monoit con của M gồm các phần tử có trọng số chia hết cho

m là tự do.

Chúng ta sẽ áp dụng Bổ đề 2.2.4 cho monoit tự do của các từ Fibonacci. Giả

sử

∞ ∑ n=0

fm,i = Fmn+i+1xn,

tức là hệ số của xn trong fm,i là số các hợp thành Fibonacci của mn + i.

Từ Bổ đề 2.2.4 suy ra rằng monoit của các hợp thành Fibonacci của các bội

của m là tự do. Ta định nghĩa hàm trọng số trên monoit này bằng cách lấy trọng số

của một hợp thành của mn là n. Khi đó hàm sinh của monoit này là fm,0.

Bây giờ, giả sử w là hợp thành Fibonacci không chồng chéo của số nguyên

r = mk − i, trong đó k ≥ 1 và 0 ≤ i < m . Khi đó bởi Bổ đề 2.1.7 và Bổ đề 2.2.4,

monoit tự do của các hợp thành Fibonacci của bội số m, bắt đầu với w, là monoit tự do, và hàm sinh cho monoit tự do này là 1 + xk fm,i.

Trong mục này, chúng ta xem xét một vài trường hợp của hàm sinh đối với số

m tuỳ ý.

(2.14) Fmn+ jxn = Fj + (−1) j Fm− jx 1 − Lmx + (−1)mx2 , Người ta đã chỉ ra rằng ∞ ∑ n=0

26

trong đó Ln là số Lucas thứ n (L0 = 2 và Ln = Fn−1 + Fn+1). Chúng ta có thể tìm

một giải thích đơn giản dựa vào monoit tự do cho hàm sinh cho Fmn+1 và Fmn−1.

Đối với Fmn+1, chúng ta có công thức dưới đây, theo Hoggatt.

Mệnh đề 2.2.5. Ta có

∞ ∑ n=0

Fmn+ jxn fm,0 =

=

(cid:19)−1 = . (2.15) 1 − Fm+1x − 1 − Fm−1x 1 − Lmx + (−1)mx2 (cid:18) mx2 F 2 1 − Fm−1x

Chứng minh. Công thức nhận được bằng phép tính toán trực tiếp, sử dụng các

trường hợp j = 1 của (2.14), công thức Lm = Fm−1 + Fm+1, và đồng nhất thức Cassini Fm+1 + Fm−1 − (−1)m = F 2 m.

Chúng ta có thể giải thích Mệnh đề 2.2.5 một cách tổ hợp, bằng cách mô tả các

nguyên tố của monoit tự do của các hợp thành Fibonacci của các bội của m. Các

nguyên tố có trọng số 1 là hợp thành Fibonacci của m, gồm Fm+1 số. Các nguyên

tố có trọng số n > 1 là có dạng u 2 v1 2 v2 2 . . . 2 vk 2 w trong đó u và w là các hợp

thành Fibonacci của m − 1 và mỗi vi là hợp thành Fibonacci của m − 2.

Có một công thức tương tự đối với Fmn−1, tương ứng với các hợp thành của các

bội của m bắt đầu với 2, chúng có hàm sinh 1 + x fm,m−2. Một tính toán đơn giản

cho kết quả sau đây, cũng của Hoggatt.

Mệnh đề 2.2.6. Ta có

∞ ∑ n=1

(cid:18) (cid:19)−1 . (2.16) 1 + x fm,m−2 = 1 + Fmn−1xn = 1 − Fm−1x − F 2 mx2 1 − Fm+1x

Có một giải thích tổ hợp đơn giản cho Mệnh đề 2.2.6. Trong monoit tự do của

các hợp thành Fibonacci của bội số của m bắt đầu với 2, các nguyên tố có trọng số

1 là các số hợp thành Fibonacci của m bắt đầu với 2, và có Fm−1 số như vậy. Mỗi

nguyên tố khác của monoit tự do này có dạng 2 uv1 v2 . . . vk w, cho k ≥ 0, trong đó

27

u và w là các hợp thành của m − 1 (có Fm số) và mỗi vi là hợp thành Fibonacci của

m (có Fm+1 số).

Không có kết quả đơn giản như Mệnh đề 2.2.5 và Mệnh đề 2.2.6 đối với fm,i

với i không bằng với 0 hoặc m − 2.

Với i = m − 1, chúng ta có, bởi (2.14)

∞ ∑ n=0

(2.17) fm,m−1 = Fm(n+1) = Fm 1 − Lmx + (−1)mx2

và một phép tính trực tiếp cho ta

(cid:18) (cid:19)−1 . 1 − (2.18) 1 + x fm,m−1 = Fm 1 − 2Fm−1x + (−1)mx2

Có thể mô tả các số nguyên tố tương ứng một cách tường minh, nhưng không có

một giải thích tổ hợp đơn giản cho hàm sinh (2.18).

Chúng ta lưu ý rằng nếu m là số lẻ thì bởi (2.14),

∞ ∑ n=0

Fmn+mxn = fm,m−1 = Fm 1 − Lmx − x2 .

Mặc dù công thức này có vẻ như sẽ có một giải thích tổ hợp đơn giản, nhưng hình

như vẫn chưa có.

Xét trường hợp m = 2 của (2.14), ta có

và f2,0 = f2,1 = 1 − x 1 − 3x + x2 1 1 − 3x + x2 .

Trường hợp m = 2 của (2.15) là

(cid:18) (cid:19)−1 1 − x 1 − 2x − (2.19) f2,0 = 1 − 3x + x2 = (1 − 2x − x2 − x3 − . . .)−1 = x2 1 − x

và các nguyên tố của monoit tự do của các hợp thành Fibonacci của các số nguyên chẵn là hợp thành 2 và hợp thành có dạng 1 2i 1 với các số nguyên không âm i.

Hàm sinh cho các nguyên tố, cùng với 3, cho ta công thức (vi) của Mục 1,

2#{i:ai=1}. F2n+1 = ∑ a∈C(n)

28

Chúng ta cũng có đồng nhất thức

(cid:18) (cid:19)−1 , 1 − (2.20) 1 + xk f2,0 = 1 + xk(1 − x) 1 − 3x + x2 = xk(1 − x) 1 − 3x + x2 + xk − xk+1

vì vậy xk(1 − x)/(1 − 3x + x2 + xk − xk+1) là hàm sinh đối với các số nguyên trong hợp thành monoit tự do của các số nguyên chẵn bắt đầu với 2 12k−2. Chỉ có trường

hợp k = 1 của (2.20), cũng là trường hợp m = 2 của (2.16), là đặc biệt đơn giản.

Ta có

(cid:18) (cid:19)−1 (cid:17)−1 = , (cid:16) 1 − x − x2 − 2x3 − 4x4 − 8x5 − . . . 1 − x − 1 + x f2,0 = x2 1 − 2x

nó cho công thức

2#{i:ai=1}+n−2k, F2n−1 = ∑ a∈C(n)

trong đó k là số các thành phần của hợp thành a.

Cũng lưu ý rằng, công thức liên phân số

1 + x f2,0 = 1 − 2x 1 − 3x + x2 = 1 1 − x 1− x 1−x

chỉ ra rằng F2n−1, với n > 0, là số đường Dyck độ dài 2n và độ cao tối đa là 3.

Công thức tương tự đối với f2,1 đơn giản hơn đối với f2,0.

Mệnh đề 2.2.7. Cố định số nguyên k ≥ 1. Tập hợp các hợp thành Fibonacci của các số chẵn bắt đầu với 1 2k−1 là các monoit tự do có các nguyên tố có dạng

1 2k−1 2i q 1 2 j, trong đó i và j là các số nguyên không âm và q là phần tử của

monoit tự do Q với các nguyên tố

1 2l 1 2m, với l ≥ 0 và 0 ≤ m ≤ k - 2m .

Điều này cho đồng nhất thức

(cid:18) (cid:19)−1 . 1 − (2.21) 1 + xk f2,1 = 1 + xk 1 − 3x + x2 = xk 1 − 3x + x2 + xk

Với k = 1, monoit tự do Q chỉ chứa từ rỗng, và các nguyên tố có dạng 1 2i 1 2 j

với i, j ≥ 0.

29

Chứng minh. Giả sử M là một monoit tự do của hợp thành Fibonacci của các số chẵn bắt đầu với 1 2k−1. Do Bổ đề 2.1.7, M là một monoit tự do. Một nguyên tố của M là một hợp thành Fibonacci bắt đầu với 1 2k−1 và chứa một số chẵn các

thành phần bằng 1, trong đó thành phần thứ j là 1, với j > 1 và là số lẻ, suy ra có

ít nhất k − 2 thành phần bằng 2. Rõ ràng rằng các nguyên tố đúng như đã được mô

tả trong mệnh đề.

(cid:33)−1 Hàm sinh đối với Q là (cid:32)

k−1 ∑ i=1

= u(x) = 1 − xi 1 − x (1 − x)2 1 − 3x + x2 + xk .

Như vậy, hàm sinh đối với các nguyên tố của M là

.u(x). = xk. 1 1 − x 1 1 − x xk 1 − 3x + x2 + xk .

Ta có điều phải chứng minh.

Với k = 1, từ (2.21) ta có (cid:18) (cid:19)−1 = (1 − x − 2x2 − 3x3 − . . .)−1. 1 + 1 − x 1 − 3x + x2 = x (1 − x)2

Chúng ta có thể thấy rằng có n hợp thành nguyên tố của 2n, vì các hợp thành này là các hợp thành của 2n có dạng 1 2i 1 2 j, mà có n nghiệm thoả mãn i + j = n − 1.

Đồng nhất thức này cho ta công thức (iv) của Mục 1,

(2.22) a1a2 . . . ak, F2n = ∑ a∈C(n)

với n ≥ 1, được chỉ ra bởi Moser và Whitney.

Stanley cho một giải thích tổ hợp của (2.22): Tổng ∑ a1a2 . . . ak là các số cách

chèn nhiều nhất một vạch thẳng vào mỗi n − 1 khoảng rỗng tách một dòng của n

dấu chấm và sau đó khoanh tròn một chấm trong mỗi đoạn. Thay thế mỗi vạch bởi

số 1, mỗi chấm không được khoanh bởi 2, và mỗi chấm được khoanh tròn bởi 1 sẽ

được tất cả các hợp thành Fibonacci của 2n − 1, mỗi cái đúng một lần. Một ví dụ

với n = 8, ta có

• (cid:12) |(cid:12)•| |(cid:12)| • •(cid:12) ⇔ 2 1 1 1 2 1 1 1 2 2 1.

30

Chúng ta có thể giải thích song ánh này bằng thuật ngữ monoit tự do: nếu chúng

ta chèn một vạch ở đầu của một trong những sắp xếp của các vạch và dấu chấm, (cid:12) (cid:12)•i (cid:12) • j, và cấu hình này tương ứng với các

thì ta có một dãy các cấu hình dạng nguyên tố 1 2i 1 2 j.

Cho k = 2, hàm sinh của các nguyên tố trong Mệnh đề 2.2.7 là

∞ ∑ n=2

n−2 ∑ i=0

∞ ∑ n=2

= 2ixn = (2n−1 − 1)xn. x2 1 − 3x + 2x2 = x2 (1 − 2x)(1 − x)

Điều này cho công thức (v) của Mục 1:

(2a1−1)(2a2−1) . . . (2ak−1), với n ≥ 1. (2.23) F2n−2 = ∑ a∈C(n)

Từ Mệnh đề 2.2.7, hợp thành nguyên tố tương ứng với (2.23) có dạng

1 2 2l0 1 2l1 12 2l2 12 . . . 12 2lm 12 2lm+1,

với m ≥ 0, trong đó l0, l1, . . . , lm+1 là các số nguyên không âm.

Để hiểu một cách tổ hợp rằng có 2n−1 − 1 hợp thành như vậy của 2n, ta bắt đầu

với hợp thành của 2n − 2 gồm n − 1 thành phần, tất cả bằng 2. Ta chọn một tập con không rỗng các thành phần, điều mà ta có thể làm bởi 2n−1 − 1 cách. Ta thay

trong cái được chọn đầu tiên 2 bởi 1, và thay trong những cái đã chọn khác 2 bởi

1 1. Cuối cùng ta thêm 1 2 vào đầu.

Với k > 2, các nguyên tố trong Mệnh đề (2.14) phức tạp hơn.

Bây giờ chúng ta hãy xem xét việc chia ba của dãy Fibonacci, chúng ta có

f3,0 =

f3,1 =

f3,2 = 1 − x 1 − 4x − x2 1 + x 1 − 4x − x2 2 1 − 4x − x2 .

Mệnh đề 2.2.5 và giải thích tổ hợp của nó cho chúng ta một giải thích tổ hợp đồng

nhất thức sau

(cid:18) (cid:19)−1 , 1 − 3x − 4 (2.24) f3,0 = (1 − 3x − 4x2 − 4x3 − . . .)−1 = x2 1 − x

31

nó cho công thức

3#{i:ai=1}4#{ j:a j(cid:54)=1}, F3n+1 = ∑ a∈C(n)

đối với n ≥ 0 : monoit tự do của các hợp thành Fibonacci của các số chia hết cho

3 có 3 nguyên tố trọng số, 1 1 1, 1 2 và 2 1, và bốn nguyên tố trọng số n với mỗi

n ≥ 2, mỗi một trong chúng có dạng a b c, trong đó a và c là 1 1 hoặc 2, và b là hợp

thành

2 1 2 1 . . . 2 1 2

với n − 2 thành phần 1 và n − 1 thành phần 2.

Tiếp theo, ta cho một mô tả monoit tự do cho trường hợp m = 3 của (2.18):

(cid:18) (cid:19)−1 . 1 − (2.25) 1 + x f3,2 = 1 + 2x 1 − 4x − x2 = 2x 1 − 2x − x2

Vế trái của (2.25) tính số các hợp thành Fibonacci của các số chia hết cho 3 bắt

đầu với thành phần 1. Trong monoit tự do này có hai nguyên tố trọng số một, 1 1 1

và 1 2. Với n ≥ 2, một nguyên tố trọng số n kết thúc bởi 2 1, 2 1 1 hoặc 2 2, vì vậy

nó phải thuộc một trong ba loại sau:

(1) p thu được từ một nguyên tố trọng số n − 1 bằng cách ghép 2 1 ở phần cuối;

(2) p thu được từ một nguyên tố trọng số n − 1 kết thúc với thành phần 1 bằng

việc thay thế 1 bởi 2 1 1;

(3) p thu được từ một nguyên tố trọng số n − 1 kết thúc bởi một thành phần 1

bằng việc thay thế 1 bởi 2 2.

Giả sử an là số của các nguyên tố trọng số n và giả sử bn là số các nguyên tố trọng

số n mà kết thúc với thành phần 1.

Khi đó ta có an = an−1 + 2bn−1 và bn = an−1 + bn−1.

Vì vậy

an = an−1 + 2bn−1

32

= an−1 + 2(an−2 + bn−2)

= (an−1 + an−2) + (an−2 + 2bn−2)

= (an−1 + an−2) + an−1

= 2an−1 + an−2,

đối với n ≥ 3, và từ a2 = a1 + 2b1 = 2 + 2 = 4 = 2a1 + a0, trong đó a0, quan hệ

truy hồi đúng với n ≥ 2. Vì vậy chúng ta tìm được hàm sinh cho các nguyên tố là

(2.26) 2x 1 − 2x − x2

và từ đó suy ra (2.25). Các hệ số của (2.26) là hai lần dãy số Pell.

Trường hợp m = 3 của Mệnh đề 2.2.6 là

∞ ∑ n=1

(cid:32) (cid:33)−1 (cid:18) (cid:19)−1 = . 1 − x − 1 − x − 4.3n−2xn 1 + x f3,1 = 4x2 1 − 3x

Chúng ta lưu ý rằng

(cid:19)−1 (cid:18) , 1 − 1 + x f3,0 = x(1 − x) 1 − 3x − 2x2

và (cid:18) (cid:19)−1 . 1 − 1 + x f4,3 = 3x) 1 − 4x + x2

33

Kết luận

Luận văn đã trình bày nhưng vấn đề sau:

1. Các dãy nâng Fibonacci, là một mở rộng của dãy Fibonacci cổ điển. Nếu

như đối với dãy Fibonacci cổ điển, ước chung lớn nhất của hai số hạng liên

tiếp luôn bằng 1, thì với dãy nâng Fibonacci, điều này không còn đúng nữa.

Luận văn giới thiệu những lớp dãy nâng Fibonacci mà ước chung lớn nhất

nói trên là bị chặn.

2. Hợp thành của các số Fibonacci. Một số công thức cho hợp thành của số

Fibonacci được giới thiệu với đầy đủ chứng minh.

Phương pháp tiếp cận ở đây là sử dụng các monoit tự do, lập nên bởi các hợp

thành với phép toán ghép.

34

Tài liệu tham khảo

Tiếng Việt

[1] Hà Huy Khoái (2004), Số học, NXB Giáo dục.

Tiếng Anh

[2] Chen K.W. (2011), “Greatest common divisors in shifted Fibonacci se-

quences”, Journal of Integer Sequences, Vol. 14, Article 11.4.7, pp. 1–17.

[3] Gessel I.M., Li J. (2013), “Compositions and Fibonacci identities”, Journal

of Integer Sequences, Vol. 16, Article 12.4.5, pp. 1–14.