Về số padovan và một vài ứng dụng
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (389.33 KB, 48 trang )
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
---------------------------
NGUYỄN TIẾN LONG
VỀ SỐ PADOVAN
VÀ MỘT VÀI ỨNG DỤNG
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 8 46 01 13
LUẬN VĂN THẠC SĨ TỐN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. Nơng Quốc Chinh
THÁI NGUN - 2021
1
Mục lục
Lời cảm ơn
2
Bảng ký hiệu
3
Mở đầu
4
Chương 1. Một số kiến thức chuẩn bị
7
1.1
Khái niệm về phần nguyên . . . . . . . . . . . . . . . . . . . . . .
7
1.2
Một số tính chất về phần nguyên . . . . . . . . . . . . . . . . . .
8
Chương 2. Dãy số Padovan, một số tính chất của dãy số Padovan 11
2.1
Dãy số Padovan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2
Công thức hàm sinh và công thức Binet . . . . . . . . . . . . . . 17
2.3
Ma trận Padovan . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1
Ma trận Toeplitz-Hessenberg . . . . . . . . . . . . . . . . 19
2.3.2
Ma trận Padovan . . . . . . . . . . . . . . . . . . . . . . . 21
Chương 3. Biểu diễn các số Padovan dưới dạng tổng của các hệ
số đa thức trên các phân hoạch của một số nguyên n thành
những phần lẻ
26
3.1
Phân hoạch của một số nguyên n . . . . . . . . . . . . . . . . . . 26
3.2
Biểu diễn các số Padovan dưới dạng tổng các hệ số đa thức trên
các phân hoạch nguyên của n thành những phần lẻ lớn hơn 1 . . 32
Kết luận
45
Tài liệu tham khảo
46
2
Lời cảm ơn
Để hoàn thành được luận văn một cách hoàn chỉnh, ngoài sự nỗ lực học hỏi
của bản thân, em luôn nhận được sự hướng dẫn và giúp đỡ nhiệt tình của PGS.
TS. Nơng Quốc Chinh, Giảng viên Trường Đại học Khoa học, Đại học Thái
Nguyên. Em xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy và xin gửi lời
tri ân nhất của em đối với những điều thầy đã dành cho em.
Em xin chân thành cảm ơn phịng Đào tạo, Khoa Tốn Tin, q thầy cô
giảng dạy lớp Cao học K12A5 (2018 - 2020) Trường Đại học Khoa học - Đại
học Thái Nguyên đã tận tình truyền đạt những kiến thức quý báu cũng như tạo
điều kiện cho em hồn thành khóa học.
Tơi xin cảm ơn Ban giám hiệu Trường trung học phổ thông Bắc Kạn, tỉnh
Bắc Kạn đã tạo điều kiện cho tôi trong suốt q trình học tập.
Tơi xin gửi lời cảm ơn chân thành nhất tới gia đình, bạn bè và đồng nghiệp,
những người đã động viên, hỗ trợ và tạo điều kiện cho tơi trong suốt q trình
học tập và thực hiện luận văn.
Xin trân trọng cảm ơn.
Thái Nguyên, tháng 12 năm 2020
Tác giả luận văn
Nguyễn Tiến Long
3
Bảng ký hiệu
R
tập các số thực
N
tập các số tự nhiên
∀x
với mọi x
Z
tập các số nguyên
Z+
tập các số nguyên dương
Q
tập các số hữu tỷ
{Pn }n≥0
dãy số Padovan
[x]
phần nguyên của số thực x
x
số nguyên bé nhất không nhỏ hơn số thực x được gọi
là trần của x
x
số nguyên lớn nhất không vượt quá số thực x được
gọi là sàn của x
(x)
số nguyên gần một số thực x nhất hay số làm tròn
của x
kết thúc chứng minh của định lí hoặc bổ đề
4
Mở đầu
Trong Toán học, dãy số nguyên thường xuyên xuất hiện và được ứng
dụng rộng rãi trong nhiều ngành khoa học khác nhau. Một ví dụ nổi tiếng
là dãy số Fibonacci, dãy này đã được biết đến cách đây hàng nghìn năm
và được ứng dụng rộng rãi trong Tốn học, Sinh học, Kinh tế, Khoa
học Máy tính, Vật lý, Kiến trúc, hội họa. . . .Ta đã biết dãy số Fibonacci
{Fn }n≥0 được xác định bởi quan hệ truy hồi:
Fn = Fn−1 + Fn−2
với điều kiện ban đầu là:
F0 = 0, F1 = 1.
Dãy số Padovan xuất hiện muộn hơn rất nhiều, và nó được gọi theo tên
nhà tốn học Richard Padovan vào năm 1994. Tương tự dãy Fibonacci,
dãy Padovan {Pn }n≥0 là một dãy số nguyên cũng được xác định bởi quan
hệ truy hồi:
Pn = Pn−2 + Pn−3
với điều kiện ban đầu:
P0 = 1, P1 = 0, P2 = 0.
Một vài số hạng ban đầu của dãy Padovan là:
1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, . . .
5
Mặt khác cũng có thể bắt đầu dãy số Padovan với điều kiện ban đầu
khác:
P0 = P 1 = P2 = 1
khi đó ta có dãy:
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, . . .
Dãy số này chính là dãy số ở trên bỏ đi 5 số đầu tiên.
Dãy số Padovan được ứng dụng trong Tốn học, Sinh học, Kinh tế, Khoa
học Máy tính, Vật lý, Kiến trúc, hội họa. Một ví dụ khá thú vị, hình
xoắn ốc của các hình tam giác đều có độ dài cạnh theo trình tự Padovan.
Mục tiêu của luận văn là nghiên cứu dãy số Padovan và một vài ứng
dụng. Ngoài phần Mở đầu, Kết luận, Tài liệu tham khảo, luận văn gồm
6
ba chương.
Chương 1: Kiến thức chuẩn bị. Chương này giới thiệu khái niệm và
một số tính chất cơ bản về phần ngun được trình bày với mục đích
cung cấp các kiến thức cần thiết để người đọc dễ theo dõi các kiến thức
ở phần sau.
Chương 2: Dãy số Padovan, một số tính chất của dãy số Padovan.
Trong chương này giới thiệu tính chất cơ bản về dãy số Padovan, cơng
thức hàm sinh và công thức Binet của dãy số Padovan.
Chương 3: Biểu diễn các số Padovan dưới dạng tổng của các hệ số
đa thức trên các phân hoạch của một số nguyên n thành những phần lẻ.
Trong chương này nghiên cứu tính chất biểu diễn các số Padovan như
tổng của các hệ số đa thức trên các phân hoạch của các số nguyên n
thành những phần lẻ.
7
Chương 1
Một số kiến thức chuẩn bị
Chương này giới thiệu các kiến thức cơ bản về số nguyên, phần
nguyên, hàm trần, hàm sàn, phần dư của số thực. Sau đó, một số tính
chất về phần ngun được trình bày với mục đích cung cấp các kiến thức
cần thiết để người đọc dễ theo dõi các kiến thức ở phần sau. Nội dung
của chương được tham khảo chủ yếu trong tài liệu [1].
1.1
Khái niệm về phần nguyên
Định nghĩa 1.1.1. Cho một số thực x ∈ R. Số nguyên lớn nhất không
lớn hơn x được gọi là phần nguyên. Ta thường kí hiệu phần nguyên của
x là [x] hoặc x .
Định nghĩa 1.1.2. Cho một số thực x ∈ R. Số nguyên bé nhất không
nhỏ hơn x được gọi là trần của x và kí hiệu là x
Định nghĩa 1.1.1 và Định nghĩa 1.1.2 tương đương với:
z ≤x
[x] = z ⇔
⇔
z∈Z
z∈Z
8
và
z−1
x =z⇔
⇔
z∈Z
z ∈ Z.
Hơn nữa, x = x nếu x ∈ Z và x = x + 1 với mọi x ∈
/ Z.
Định nghĩa 1.1.3. Phần dư ( phần thập phân, phần lẻ ) của một số
thực x, kí hiệu là {x} được định nghĩa bởi cơng thức {x} = x − [x].
Từ Định nghĩa 1.1.3 ta suy ra ngay, 0 ≤ {x} < 1 với mọi x ∈ R và
{z} = 0 khi và chỉ khi z là số nguyên. Ta biết rằng, với mỗi x ∈ R thì
tồn tại số nguyên z ∈ Z sao cho z ≤ x < z + 1.
Định nghĩa 1.1.4. Số nguyên gần một số thực x nhất được kí hiệu là
(x) và (x) được gọi là số làm tròn của x.
1.2
Một số tính chất về phần nguyên
Tính chất 1.2.1. Với mọi x ∈ R ta có
a) [x] ≤ x < [x] + 1 hay x − 1 < [x] ≤ x;
b) x − 1 < x ≤ x hay x ≤ x < x + 1.
Dấu bằng xảy ra khi và chỉ khi x là số nguyên.
Tính chất 1.2.2.
x = [x] + {x} ; 0 ≤ {x} < 1; x = {x} ⇔ 0 ≤ x < 1.
Tính chất 1.2.3.
[x + z] = [x] + z; {x + z} = {x} với mọi z ∈ Z.
Đảo lại, {x} = {y} thì y = x + z với z ∈ Z nào đó.
9
Tính chất 1.2.4. Nếu x ∈ Z thì [x] = x và {x} = 0. Ngược lại nếu
[x] = x hoặc {x} = 0 thì x ∈ Z. Nếu x ∈ Q là số hữu tỉ nhưng không
phải là số nguyên thì {x} cũng là một số hữu tỉ thuộc khoảng (0; 1). Nếu
x ∈ R là số vô tỉ thì {x} cũng là một số vơ tỉ thuộc khoảng (0; 1).
Tính chất 1.2.5. Phần dư, sàn và trần có tính chất luỹ đẳng, tức là
khi hai lần áp dụng phép tốn thì kết quả khơng đổi:
{{x}} = {x} ; [[x]] = [x] , và
x
= x với mọi x ∈ R.
Hơn nữa,
{[x]} = [{x}] = { x } = 0 với mọi x ∈ R.
Nhưng
{x} = 0 và [x] = [ x ] = x với mọi x ∈ Z;
{x} = 1, [x] = [x] = x − 1 = [ x ] − 1 với mọi x ∈
/ Z.
Tính chất 1.2.6. Các qui tắc đổi chỗ (hoán vị), kết hợp của phép toán
cộng và phép toán nhân, qui tắc kết hợp giữa phép toán nhân và phép
toán cộng vẫn đúng cho phần nguyên và phần dư.
Tính chất 1.2.7. Phép làm trịn số (x) thơng thường như đã nêu trong
Định nghĩa 1.1.4 chính là phép lấy phần nguyên của x + 0, 5, tức là
(x) = [x + 0, 5].
Tính chất 1.2.8. Nếu [x] = [y] thì |x − y| < 1 hay −1 < x − y < 1.
Tính chất 1.2.9. Nếu x ≥ y thì [x] ≥ [y]. Đảo lại, nếu [x] > [y] thì
x > y.
Tính chất 1.2.10.
a) Cả hai số x và y là hai số nguyên khi và chỉ khi {x} + {y} = 0.
10
b) Trong hai số x và y có một số ngun và một số khơng phải là số
ngun thì 0 < {x} + {y} < 1.
c) Hai số x và y khơng ngun có tổng x + y là một số nguyên khi và
chỉ khi {x} + {y} = 1.
Tính chất 1.2.11. Với mọi x, y ∈ R ta có
{x + y} ≤ {x} + {y} ≤ {x + y} + 1,
[x] + [y] ≤ [x + y] ≤ [x] + [y] + 1.
Tính chất 1.2.12. Giả sử r là phần dư khi chia một số nguyên m cho
một số nguyên dương n, m = pn + r với r ∈ {0, 1, . . . , n − 1}. Khi ấy
m
r =m−n
.
n
p
Tính chất 1.2.13. Nếu p và q là những số nguyên dương sao cho
q
p
1
p
+ .
không phải là số ngun thì ≥
q
q
q
Tính chất 1.2.14. Cho q là số tự nhiên, x là số thực dương bất kì. Có
x
đúng
số tự nhiên không vượt quá x và chia hết cho q.
q
Hệ quả 1.2.15. Cho q và n là các số tự nhiên bất kỳ. Trong dãy các số
n
n
n
1, 2, . . . , n có đúng
số chia hết cho q, 2 số chia hết cho q 2 , 3
q
q
q
n
số chia hết cho q 3 , . . . , k số chia hết cho q k .
q
Ta nhắc lại, một số tự nhiên bao giờ cũng có một phân tích duy nhất
ra thừa số nguyên tố, tức là n = pα1 1 pα2 2 · · · pαk k với pi là các số nguyên tố
khác nhau và αi là các số tự nhiên khác 0.
Tính chất 1.2.16 (Cơng thức Polignac). Số mũ cao nhất k của thừa số
nguyên tố q trong phân tích n! ra thừa số nguyên tố bằng:
k=
n
n
n
+ 2 + 3 + ··· .
q
q
q
11
Chương 2
Dãy số Padovan, một số tính chất
của dãy số Padovan
Chương này giới thiệu khái niệm về dãy số Padovan và các tính chất
cơ bản, cơng thức hàm sinh và công thức Binet của dãy số này. Nội dung
của chương được tham khảo trong [3, 5, 15] và wikipedia.
2.1
Dãy số Padovan
Định nghĩa 2.1.1. Dãy số Padovan {Pn }n≥0 là một dãy số nguyên được
xác định bởi quan hệ truy hồi:
Pn = Pn−2 + Pn−3 .
với điều kiện ban đầu:
P0 = P1 = P2 = 1.
Một vài số hạng ban đầu của dãy số Padovan là:
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, . . . .
Định lý 2.1.2. Cho {Pn }n≥0 là dãy số Padovan khi đó ta có:
n
Pm = Pn+5 − 2
a)
m=0
(2.1)
12
n
b)
P2m = P2n+3 − 1
(2.2)
P2m+1 = P2n+4 − 1
(2.3)
P3m = P3n+2
(2.4)
P3m+1 = P3n+3 − 1
(2.5)
P3m+2 = P3n+4 − 1
(2.6)
P5m = P5n+1 .
(2.7)
m=0
n
c)
m=0
n
d)
m=0
n
e)
m=0
n
f)
m=0
n
g)
m=0
Chứng minh. a) Với n = 1 ta có:
P0 + P1 = P6 − 2 = 2.
Giả sử (2.1) đúng với n = k tức là:
P0 + P1 + · · · + Pk = Pk+5 − 2,
ta phải chứng minh (2.1) đúng với n = k + 1, tức là:
P0 + P1 + · · · + Pk + Pk+1 = Pk+6 − 2.
Thật vậy,
(P0 + P1 + · · · + Pk ) + Pk+1 = Pk+5 − 2 + Pk+1
= Pk+3 + Pk+2 − 2 + Pk+1
= Pk+4 + Pk+3 − 2
= Pk+6 − 2.
b) Với n = 1 ta có:
P0 + P2 = P5 − 1 = 2.
13
Giả sử (2.2) đúng với n = k tức là:
P0 + P2 + · · · + P2k = P2k+3 − 1,
ta phải chứng minh (2.2) đúng với n = k + 1, tức là:
P0 + P2 + · · · + P2k + P2k+2 = P2k+5 − 1.
Thật vậy,
(P0 + P2 + · · · + P2k ) + P2k+2 = P2k+3 − 1 + P2k+2
= P2k+5 − 1.
c) Với n = 1 ta có:
P1 + P3 = P5 − 1 = 3.
Giả sử (2.3) đúng với n = k tức là:
P1 + P3 + · · · + P2k+1 = P2k+4 − 1,
ta phải chứng minh (2.3) đúng với n = k + 1, tức là:
P1 + P3 + · · · + P2k+1 + P2k+3 = P2k+6 − 1.
Thật vậy,
(P1 + P3 + · · · + P2k+1 ) + P2k+3 = P2k+4 − 1 + P2k+3
= P2k+6 − 1.
d) Với n = 1 ta có:
P0 + P3 = P5 = 3.
Giả sử (2.4) đúng với n = k tức là:
P0 + P3 + · · · + P3k = P3k+2 ,
14
ta phải chứng minh (2.4) đúng với n = k + 1, tức là:
P0 + P3 + · · · + P3k + P3k+3 = P3k+5 .
Thật vậy,
(P1 + P3 + · · · + P3k ) + P3k+3 = P3k+2 + P3k+3
= P3k+5 .
e) Với n = 1 ta có:
P1 + P4 = P6 − 1 = 3.
Giả sử (2.5) đúng với n = k tức là:
P1 + P4 + · · · + P3k+1 = P3k+3 − 1,
ta phải chứng minh (2.5) đúng với n = k + 1, tức là:
P1 + P4 + · · · + P3k+1 + P3k+4 = P3k+6 − 1.
Thật vậy,
(P1 + P4 + · · · + P3k+1 ) + P3k+4 = P3k+3 − 1 + P3k+4
= P3k+6 − 1
f) Với n = 1 ta có:
P2 + P5 = P7 − 1 = 4.
Giả sử (2.6) đúng với n = k tức là:
P2 + P5 + · · · + P3k+2 = P3k+4 − 1,
ta phải chứng minh (2.6) đúng với n = k + 1, tức là:
P2 + P5 + · · · + P3k+2 + P3k+5 = P3k+7 − 1.
15
Thật vậy,
(P2 + P5 + · · · + P3k+2 ) + P3k+5 = P3k+4 − 1 + P3k+5
= P3k+7 − 1.
g) Với n = 1 ta có:
P0 + P5 = P6 = 4.
Giả sử (2.7) đúng với n = k tức là:
P0 + P5 + · · · + P5k = P5k+1 ,
ta phải chứng minh (2.7) đúng với n = k + 1, tức là:
P0 + P5 + · · · + P5k + P5k+5 = P5k+6 .
Thật vậy,
(P0 + P5 + · · · + P5k ) + P5k+5 = P5k+1 + P5k+5
= P5k+1 + P5k+2 + P5k+3
= P5k+4 + P5k+3
= P5k+6 .
Định lý 2.1.3. Cho {Pn }n≥0 là dãy số Padovan khi đó ta có:
n
Pm2 Pm+1 = Pn Pn+1 Pn+2
a)
m=0
(2.8)
n
Pm Pm+2 =Pn+2 Pn+3 − 1.
b)
m=0
(2.9)
16
Chứng minh. a) Với n = 2 ta có:
(P0 )2 P1 + (P1 )2 P2 + (P2 )2 P3 = P2 P3 P4 = 4
Giả sử (2.8) đúng với n = k tức là:
(P0 )2 P1 + (P1 )2 P2 + · · · + (Pk )2 Pk+1 = Pk Pk+1 Pk+2
ta phải chứng minh (2.8) đúng với n = k + 1, tức là:
(P0 )2 P1 + (P1 )2 P2 + · · · + (Pk )2 Pk+1 + (Pk+1 )2 Pk+2 = Pk+1 Pk+2 Pk+3
Thật vậy, ta có:
((P0 )2 P1 + (P1 )2 P2 + · · · + (Pk )2 Pk+1 ) + (Pk+1 )2 Pk+2
= Pk Pk+1 Pk+2 + (Pk+1 )2 Pk+2 = Pk+2 Pk Pk+1 + (Pk+1 )2
= Pk+2 Pk+1 (Pk + Pk+1 ) = Pk+1 Pk+2 Pk+3 .
b) Với n = 1 ta có:
P0 P2 + P 1 P3 = P 3 P4 − 1 = 3
Giả sử (2.9) đúng với n = k tức là:
P0 P2 + P1 P3 + · · · + Pk Pk+2 = Pk+2 Pk+3 − 1
ta phải chứng minh (2.9) đúng với n = k + 1, tức là:
P0 P2 + P1 P3 + · · · + Pk Pk+2 + Pk+1 Pk+3 = Pk+3 Pk+4 − 1
Thật vậy, ta có:
(P0 P2 + P1 P3 + · · · + Pk Pk+2 ) + Pk+1 Pk+3
= Pk+2 Pk+3 − 1 + Pk+1 Pk+3 = Pk+3 (Pk+2 + Pk+1 ) − 1
= Pk+3 Pk+4 − 1
17
Theo wikipedia, ta có các tính chất sau:
Tính chất 2.1.4. Cho {Pn }n≥0 là dãy số Padovan khi đó ta có:
k
2
m
m
=
.
Pk−2 =
n
k − 2m
2m+n=k
m= k
3
(2.10)
Ví dụ 2.1.5. Đối với k = 12, các giá trị của cặp (m, n) với 2m + n = 12,
ta có hệ số nhị thức khác 0 là (6, 0), (5, 2), (4, 4) và
6
5
4
+ + = C60 + C52 + C44 = 1 + 10 + 1 = 12 = P10
0
2
4
Tính chất 2.1.6. Dãy số Padovan (Pm ) xác định bằng quan hệ truy
hồi:
Pm = Pm+3 − Pm+1 ,
cho m < 0 được mở rộng sang các chỉ số âm, với điều kiện ban đầu:
P−1 = P−3 = P−4 = 0 và P−2 = P−5 = 1. Một vài số hạng ban đầu:
. . . − 3, 1, 1, −2, 2, −1, 0, 1, −1, 1, 0, 0, 1, 0
2.2
Công thức hàm sinh và công thức Binet
Định nghĩa 2.2.1. Hàm sinh của một dãy số vô hạn a0 , a1 , a2 , . . . , an , . . .
là một chuỗi hình thức được xác định bởi
G(x) = a0 + a1 x + a2 x2 + · · · + an xn + · · ·
Định lý 2.2.2 (Công thức hàm sinh). Cho dãy số Padovan {Pn }n≥0 với
điều kiện ban đầu P0 = 1, P1 = 0, P2 = 0. (Pn ) có hàm sinh là:
∞
1 − x2
P (x) =
.
Pn x =
2 − x3
1
−
x
n=0
n
18
Chứng minh. Đặt P (x) là hàm sinh của dãy số (Pn ) ta có:
P (x) = P0 + P1 x + P2 x2 + P3 x3 + P4 x4 + · · ·
(2.11)
−x2 P (x) = −P0 x2 − P1 x3 − P2 x4 − P3 x5 − · · ·
(2.12)
−x3 P (x) = −P0 x3 − P1 x4 − P2 x5 − P3 x6 − · · ·
(2.13)
Cộng vế với vế của (2.11), (2.12), (2.13) ta được:
1 − x2 − x3 P (x) = P0 + P1 x + (P2 − P0 ) x2 + (P3 − P1 − P0 ) x3 + · · ·
= P0 + P1 x + (P2 − P0 ) x2 + 0
= 1 − x2 .
Suy ra
∞
1 − x2
.
P (x) =
Pn x =
2 − x3
1
−
x
n=0
n
Tính chất 2.2.3 (Cơng thức Binet). Với n ≥ 0, ta có các số Padovan
được biểu thị bởi cơng thức:
Pn =
ρn+1
β
,
trong đó, ρ là nghiệm thực duy nhất của phương trình x3 − x − 1 = 0,
β là nghiệm thực duy nhất của phương trình s3 − 2s2 + 23s − 23 = 0.
Chứng minh. Tỷ lệ các số Padovan liên tiếp có một giá trị giới hạn khi
n tiến đến dương vô cùng. Giá trị này được gọi là số dẻo hay số nhựa ρ
Pn+1
=
n→+∞ Pn
ρ = lim
3
1 1
+
2 6
23 3 1 1
+
−
3
2 6
23
= 1, 3247179572447460259...
3
Đó là nghiệm thực duy nhất của phương trình bậc ba
x3 − x − 1 = 0
19
phương trình này cịn có hai nghiệm phức q và r. Các số Padovan có thể
được viết dưới dạng luỹ thừa các nghiệm của phương trình này. Ta có:
Pn = aρn + bq n + crn ,
trong đó a, b, c là hằng số. Vì độ lớn các nghiệm phức q và r đều nhỏ
hơn 1, đây là các số phức liên hợp, luỹ thừa của các số này dần đến 0
khi n tiến đến dương vô cực và Pn − aρn tiến tới 0. Với n ≥ 0 thì Pn là
ρn+1
số nguyên gần nhất với
trong đó:
β
ρ
β = = 1, 0453567932525329623...
a
là nghiệm thực duy nhất của phương trình
s3 − 2s2 + 23s − 23 = 0.
2.3
2.3.1
Ma trận Padovan
Ma trận Toeplitz-Hessenberg
Ma trận vuông cấp n sau đây được gọi là ma trận Toeplitz-Hessenberg
a0
0 ··· 0 0
a1
a2
a
a
·
·
·
0
0
1
0
An ≡ An (a0 , a1 , . . . , an ) = · · · · · · · · ·
an−1 an−2 an−3 · · · a1 a0
an an−1 an−2 · · · a2 a1
Ta có:
n
(−a0 )k−1 ak det An−k ,
det An =
k=1
20
det A0 = 1,
n
(−a0 )k−1 ak det An−k
det An =
k=1
(−a0 )n−(t1 +···+tn ) pn (t)at11 at22 · · · atnn ,
=
t1 +2t2 +···+ntn =n
trong đó:
pn (t) =
(t1 + t2 + · · · + tn )!
=
t1 !t2 ! · · · tn !
t1 + t2 + · · · + tn
.
t1 , t2 , . . . , tn
Ta sẽ viết: det An = det(a0 , a1 , . . . , an ), với cách viết như vậy ta có định
lý sau:
Định lý 2.3.1. Với n ≥ 1 ta có:
n−1
3
(−1)i
a) det (P0 , P1 , . . . , Pn−1 ) =
i=1
b) det (P1 , P2 , . . . , Pn ) = 1 − δn,2
1
(−1)
c) det (P2 , P3 , . . . , Pn+1 ) =
2
n − 2 − 2i
+ δn,1
i−1
n+1
3
d) det (P3 , P4 , . . . , Pn+2 ) = n + δn,1
1
(−1)
e) det (P4 , P5 , . . . , Pn+3 ) = 1 +
2
n2 + n + 4
f ) det (P5 , P6 , . . . , Pn+4 ) =
,
2
+ (−1)
n
3
n+2
3
+ (−1)
n+1
3
+ δn,1
(2.14)
,
(2.15)
trong đó ký hiệu δn,k là Kronecker.
Chứng minh. Ta sẽ chứng minh ý c) của định lý bằng phương pháp quy
nạp.
Ký hiệu: Dn = det (P2 , P3 , . . . , Pn+1 ) .
Ta có (2.14) luôn đúng với n = 1 và n = 2.
Giả sử (2.14) đúng với k ≤ n − 1 trong đó n ≥ 2. Theo tính chất của
21
dãy số Padovan ta có:
n
(−1)i−1 Pi+1 Dn−i
Dn =
i=1
n
(−1)i−1 (Pi−1 + Pi−2 ) Dn−i
= P2 Dn−1 − P3 Dn−2 +
i=3
n−2
n−3
= Dn−1 − 2Dn−2 +
(−1)
i−1
(−1)i Pi+1 Dn−i−3
Pi+1 Dn−i−2 +
i=1
i=0
n−3
(−1)i Pi+1 Dn−i−3 + P1 Dn−3
= Dn−1 − 2Dn−2 + Dn−2 +
i=1
= Dn−1 − Dn−2 − Dn−3 + Dn−3
= Dn−1 − Dn−2 .
Sử dụng giả thiết quy nạp ta thu được:
1
(−1)
2
1
=
(−1)
2
Dn =
n
3
n+1
3
+ (−1)
n+1
3
+ (−1)
n+2
3
− (−1)
n−1
3
− (−1)
n
3
.
Do đó (2.14) đúng với n. Vậy bằng cách quy nạp ta suy ra điều phải
chứng minh.
2.3.2
Ma trận Padovan
Định nghĩa 2.3.2. Ma trận Padovan (Pn ) được xác định bởi quan hệ
truy hồi: Pn+3 = Pn+1 + Pn với n ∈ N,
1 0
P0 = 0 1
0 0
0 1
P1 = 0 0
1 1
điều kiện ban đầu:
0
0
1
0
1
0
22
0 0 1
P2 = 1 1 0 .
0 1 1
Định lý 2.3.3. Đối với bất kỳ số nguyên dương nào ta có ma trận
Padovan :
Pn−5 Pn−3 Pn−4
Pn = Pn−4 Pn−2 Pn−3
Pn−3 Pn−1 Pn−2
(2.16)
Chứng minh. Ta chứng minh theo phương pháp quy nạp. Trước tiên, ta
xét với n = 2, n = 1, n = 0, n = −1, n = −2 và theo tính chất 2.1.6 ta
thu được kết quả:
P−1 = P−3 = P−4 = 0 và P−2 = P−5 = 1.
Ta có:
P−5 P−3
P0 = P−4 P−2
P−3 P−1
P−4 1 0 0
P−3 = 0 1 0
0 0 1
P−2
và theo tính chất các số hạng đầu tiên của dãy số Padovan ta có:
0 1 0
P1 = 0 0 1 .
1 1 0
Giả sử (2.16) đúng với n = k ∈ Z+ , ta suy ra (2.16) đúng với n = k + 1
Pk+1 = Pk−1 + Pk−2
Pk−6 Pk−4 Pk−5 Pk−7 Pk−5 Pk−6
= Pk−5 Pk−3 Pk−4 + Pk−6 Pk−4 Pk−5
Pk−4 Pk−2 Pk−3
Pk−5 Pk−3 Pk−4
23
Pk−4 Pk−2 Pk−3
= Pk−3 Pk−1 Pk−2 .
Pk−2 Pk Pk−1
Định lý 2.3.4. Với mọi n ∈ N ta có thể viết công thức Binet cho chuỗi
ma trận Padovan
Pn = A1 xn + B1 y n + C1 z n ,
trong đó:
A1 =
yP2 + y 2 P1 + P0
xP2 + x2 P1 + P0
, B1 =
,
x(x − y)(x − z)
y(y − x)(y − z)
C1 =
zP2 + z 2 P1 + P0
,
z(z − x)(z − y)
x, y, z là nghiệm của phương trình đặc trưng của: Pn+3 = Pn+1 + Pn
Chứng minh. Dựa trên quan hệ truy hồi của dãy số Padovan:
Pn+3 = Pn+1 + Pn với n ∈ N,
ta có:
Pn = A1 xn + B1 y n + C1 z n .
Sử dụng điều kiện ban đầu trong Định nghĩa 2.3.2 và áp dụng các phép
tốn đại số tuyến tính cơ bản ta sẽ nhận được ma trận A1 , B1 , C1 từ đó
suy ra điều phải chứng minh.
Hệ quả 2.3.5. Theo công thức Binet đối với dãy số Padovan ta có:
Pn−1
xn+3
y n+3
z n+3
=
+
+
,
(x − y)(x − z) (y − x)(y − z) (z − x)(z − y)
trong đó n > 0.
24
Chứng minh. Theo Định nghĩa 2.3.2 và Định lý 2.3.3 ta có:
Pn = A1 xn + B1 y n + C1 z n
xP2 + x2 P1 + P0 n yP2 + y 2 P1 + P0 n zP2 + z 2 P1 + P0 n
=
x +
y +
z
x(x − y)(x − z)
y(y − x)(y − z)
z(z − x)(z − y)
2
x
x
1
xn−1
=
x x+1
x2
(x − y)(x − z)
2
2
x x+x x+1
2
1
y
y
n−1
y
+
y y +1
y2
(y − x)(y − z)
2
2
y y+y y+1
2
1
z
z
n−1
z
+
z z +1
z2 ,
(z − x)(z − y)
2
2
z z+z z+1
x, y, z là nghiệm của phương trình X 3 − X − 1 = 0 và ta có:
2
1 x x
n−1
x
Pn =
x x 3 x2
(x − y)(x − z)
2
4
3
x x x
2
1 y y
n−1
y
+
y y3 y2
(y − x)(y − z)
2
4
3
y y y
1 z2 z
n−1
z
+
z z3 z2 .
(z − x)(z − y)
2
4
3
z z z
