Một số đẳng thức liên quan đến số Catalan

Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 MỘT SỐ ĐẲNG THỨC LIÊN QUAN ĐẾN SỐ CATALAN Hoàng Minh Quân, THPT Ngọc Tảo, Hà Nội Nguyễn Văn Sơn, THPT Thường Xuân 2 - Thanh Hóa Tóm tắt nội dung Số Catalan là chủ đề hay và khó mà nhiều bài toán đếm cho ra kết quả là số Cata- lan, chẳng hạn như bài toán dấu ngoặc, bài toán hành trình Dick, bài toán đoàn quân kiến,. . . Bài viết sau đây trình bày về một số đẳng thức đẹp liên quan đến số Catalan. 1 Bài toán Euler Trước hết để tìm công thức số Catalan, ta xét bài toán Euler sau: Bài toán 1.1. Một cách phân chia thành các tam giác củamột đa giác lồi n cạnh Pn (n ≥ 3), là một cách chia Pn thành các tam giác (không tính đến các giao điểm của các đường chéo của Pn). Đặt a0 = 1 và n ≥ 1 đặt an là số cách khác nhau để phân chia thành các tam giác của đa giác lồi n+ 2 cạnh trên mặt phẳng. Chứng minh rằng với n ≥ 1 ta có: an = a0an−1 + a1an−2 + a2an−3 · · · an−2a1 + an−1a0. Lời giải. Hiển nhiên a1 = 1. Ta xét P4, P5 (đa giác lồi 4 và 5 cạnh) như hình vẽ 1 2 3 4 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ta ký hiệu đa giác (n+ 2) cạnh là Pn+2. Ta cố định một cách chia trong Pn+2, (n ≥ 2) . Hiển nhiên n = 1 đẳng thức đúng. Chọn một cạnh bất kỳ, ta ký hiệu cạnh đó là [1, n+ 2] được nối từ điểm 1 và điểm (n+ 2) của Pn+2. Ta có cạnh [1, n+ 2] thuộc vào duy nhất một tam giác trong cách chia này. Ký hiệu điểm thứ 3 của tam giác có cạnh là [1, n+ 2] là r với r = 2, 3, · · · , n+ 1 và tam giác là ∆ (1, n+ 2, r) như hình bên dưới đây. 1 2 r n+ 1 n+ 2 (1) (2) Ta thấy ∆ (1, n+ 2, r) chia Pn+2 thành 2 đa giác nhỏ hơn: Đa giác r cạnh (1) và đa giác (n+ 3− r) cạnh (2) như hình vẽ. Từ định nghĩa, đa giác r cạnh (1) có thể được chia thành các tam giác bằng ar+2 cách, trong khi đó đa giác (n+ 3− r) cạnh (2) được chia thành các tam giác bằng an+1−r cách độc lập nhau. Do đó, theo quy tắc nhân số các tam giác khác nhau được chia thành của Pn+2 bởi tam giác ∆ (1, n+ 2, r) là: ar−2an+1−r. Do giá trị của r chạy từ 2 đến (n+ 1) nên theo quy tắc cộng ta có an = n+1 ∑ r=2 ar−2an+1−r hay an = n−1 ∑ k=0 akan−1−k với n ≥ 1. Ta sẽ chứng minh an = n−1 ∑ k=0 akan−1−k, bằng kỹ thuật hàm sinh. Đặt A(x) = ∞ ∑ n=0 anxn là hàm sinh của dãy (an) thì: A(x)− a0 = ∞ ∑ n=1 akxn = ∞ ∑ n=1 ( n−1 ∑ k=0 akan−1−k ) xn = (a0a0) x+ (a0a1 + a1a0 + a1a0) x2 + (a0a1 + a1a1 + a2a0) x3 + · · · = ( a0 + a1x+ a2x2 + a3x3 + · · · ) · (a0x+ a1x2 + a2x3 + · · · ) = x (A (x))2 . Do đó, vì a0 = 1 nên x (A(x)) 2 − A(x) + 1 = 0. ta nhận được nghiệm của phương trình là A(x) = 1±√1− 4x 2x = 1 2x [ 1± (1− 4x) 12 ] . 2 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Hệ số của xn(n 6= 1) trong khai triển (1− 4x) 12 là Cn1 2 (−4)n = 1 2 ( 1 2 − 1 ) · ( 1 2 − 2 ) · · · ( 1 2 − n+ 1 ) n! (−4)n = (−4)n ( 1 2 )n (−1)n−1 1 · 1 · 3 · 5 · · · (2n− 3) n! = −2n ((2n− 2)! n! · 2 · 4 · 6 · · · (2n− 2) = 2 n · (2n− 2)! (n− 1)! (n− 1)! − 2 n ·Cn−12(n−1). Vì an ≥ 1, nên từ A(x) = 12x [ 1± (1− 4x) 12 ] suy ra A(x) = 1 2x [ 1− (1− 4x) 12 ] = 1 2x ∞ ∑ n=1 2 n Cn−12(n−1)x n. Do đó, với n ≥ 1 ta có an = 12 · 2 n+ 1 Cn2n = Cn. Số Cn = 1 n+ 1 Cn2n gọi là số Catalan thứ n. Có rất nhiều bài toán tổ hợp có kết quả là số Catalan. Đây là kết quả do nhà toán học Eugène Catalan (1814 - 1894) phát hiện và mang tên ông. Sau đây là một số đẳng thức đẹp liên quan đến số Catalan. Bài toán 1.2. Cho số tự nhiên n 6= 1. Chứng minh rằng Cn2n −Cn−12n = 1 n+ 1 Cn2n. Lời giải. Ta có Cn2n −Cn−12n = (2n)! n! · n! − (2n)! (n− 1)! · (n+ 1)! = (2n)! [(n+ 1)− n] n! · (n+ 1)! = 1 n+ 1 · (2n)! n! · n! = 1 n+ 1 Cn2n. Bài toán 1.3. Chứng minh rằng với mọi số nguyên không âm n, ta có Cn = 2Cn2n −Cn2n+1. 3 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Lời giải. Ta có Cn2n −Cn−12n = 2 · (2n)! n! · n! − (2n+ 1)! n! · (n+ 1)! = 2 · (n+ 1) · (2n)! n! · (n+ 1)! − (2n+ 1)! n! · (n+ 1)! = (2n+ 1)!+ (2n)! n! · (n+ 1)! − (2n+ 1)! n! · (n+ 1)! = (2n)! n! · (n+ 1)! = 1 n+ 1 · (2n)! n! · n! = Cn. Bài toán 1.4. Chứng minh rằng với mọi số nguyên dương n, ta có Cn = 4Cn2n−1 −Cn2n+1. Lời giải. Ta có 4Cn2n−1 −Cn2n+1 = 4(2n− 1)! n! · (n− 1)! − (2n+ 1)! n! · (n+ 1)! = 4n(n+ 1) · (2n− 1)! n! · (n+ 1)! − (2n+ 1)! n! · (n+ 1)! = 1 n+ 1 · 2n · (2n+ 2)(2n− 1)!− (2n+ 1)! n! · n! = 1 n+ 1 · (2n+ 2)(2n)!− (2n+ 1)(2n)! n! · n! = 1 n+ 1 · (2n)! n! · n! = Cn. Bài toán 1.5. Chứng minh rằng với mọi số nguyên dương n, ta có Cn = Cn+12n+1 − 2Cn+12n . Lời giải. Ta có Cn+12n+1 − 2Cn+12n = (2n− 1)! (n+ 1)! · n! − 2(2n)! (n+ 1)! · (n− 1)! = (2n+ 1)! (n+ 1)! · n! − 2(2n)! · n (n+ 1)! · n! = (2n+ 1)!− 2(2n)! · n (n+ 1)! · n! = (2n)! [(2n+ 1)− 2n] (n+ 1)! · n! = 1 n+ 1 · (2n)! n! · n! = Cn. 4 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Bài toán 1.6. Chứng minh rằng với mọi số nguyên dương n ≥ 2, ta có Cn+1 = 2Cn + 2 n ·Cn−22n . Lời giải. Ta có 2Cn + 2 n ·Cn−22n = 2 1 n+ 1 ·Cn−22n + 2 n ·Cn−22n = 2 n+ 1 · (2n)! n! · n! + 2 n · (2n)! (n− 2)! · (n+ 2)! = 2 · (2n)! (n+ 1)! · n! + 2(n− 1) · (2n)! n! · n! = 1 n+ 2 · (2n)! · (2n+ 4+ 2n− 2) n! · (n+ 1)! = 1 n+ 2 · (2n)! · 2 · (2n+ 1) n! · (n+ 1)! = 1 n+ 2 · (2n)! · 2 · (n+ 1)(2n+ 1) (n+ 1)! · (n+ 1)! = 1 n+ 2 · (2n)!(2n+ 2)(2n+ 1) (n+ 1)! · (n+ 1)! = 1 n+ 2 · (2n+ 2)! (n+ 1)! · (n+ 1)! = 1 n+ 2 ·Cn+12n+2 = Cn+1. Bài toán 1.7. Chứng minh rằng với mọi số nguyên dương n ≥ 1, ta có C2n = C2n4n −C2n4n −C2n−14n . Lời giải. Ta có C2n4n −C2n−14n = C2n4n − (4n)! (2n− 1)!(2n+ 1)! = C2n4n − 1 2n+ 1 · (2n) · (4n)! (2n)! · (2n)! = C2n4n − 2n 2n+ 1 ·C2n4n = C2n4n ( 1− 2n 2n+ 1 ) = 1 2n+ 1 ·C2n4n = C2n. Bài toán 1.8. Chứng minh rằng với mọi số nguyên dương 1 ≤ k ≤ n, ta có n ∑ k=1 k ( Ckn )2 = n · (2n− 1)! ·Cn. 5 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Lời giải. Khai triển (1+ x)n = C0n +C1nx+C2nx2 + · · ·+Cnnxn. Lấy đạo hàm hai vế ta được n(1+ x)n−1 = C1n + 2C2nx+ · · · nCn−1n Tương đương nx(1+ x)n−1 = C1nx+ 2C2nx2 + · · ·+ nCnnxn. Thay x bởi 1 x ta có n x ( 1+ 1 x )n−1 = 1 x C1n + 2 x2 C2n + · · ·+ n xn Cnn. Đem quy đồng ta được n(1+ x)n−1 = nCnn + (n− 1)Cn−1n x+ · · ·+ 2C2nxn−2 +C1nxn−1 = n ∑ k=1 kCknx k (1) Mặt khác (1+ x)n = n ∑ k=0 Cknx k (2) Từ (1) và (2) nhân tương ứng các vế, ta có n(1+ x)2n−1 = [ n ∑ k=1 kCknx n−k ] · [ n ∑ k=0 kCknx k ] So sánh hệ số của xn ở hai vế ta có n ∑ k=1 k ( Ckn )2 = nCn2n−1 = n(2n− 1)! n!(n− 1)! = n(2n− 1)(2n− 2)! n(n− 1)!(n− 1)! = n(2n− 1) · 1 n · (2n− 2)! (n− 1)!(n− 1)! = n(2n− 1)Cn−1. Bài toán 1.9. Chứng minh rằng với mọi số nguyên dương 0 ≤ k ≤ n, ta có Cn = 1 2 n+1 ∑ k=0 [ Ckn −Ck−1n ]2 . Lời giải. Đặt f (n) = 1 2 n+1 ∑ k=0 [ Ckn −Ck−1n ]2 Ta có tính chất của tam giác PasCal như sau Ckn+1 = C k−1 n +C k n ⇔ ( Ckn+1 )2 = ( Ck−1n )2 + 2Ck−1n Ckn + ( Ckn )2 Suy ra ( Ckn+1 )2 − (Ckn)2 − (Ck−1n )2 = 2Ck−1n Ckn 6 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Do đó f (n) = n+1 ∑ k=0 [ Ckn −Ck−1n ]2 = n+1 ∑ k=0 [( Ckn )2 − 2CknCk−1n + (Ck−1n )2] = 2 n+1 ∑ k=0 ( Ckn )2 + 2 n+1 ∑ k=0 ( Ck−1n )2 − n+1∑ k=0 ( Ckn+1 )2 = 2 n ∑ k=0 ( Ckn )2 + 2 n ∑ k=0 ( Ckn )2 − n+1∑ k=0 ( Ckn+1 )2 = 2Cn2n + 2C n 2n −Cn+12n+2 = 4Cn2n − 2 [ Cn−12n +C n 2n ] = Cn2n − 2Cn−12n = 2 ( Cn2n −Cn−12n ) . Theo kết quả Bài toán 1, ta có Cn2n −Cn−12n = 1 n+ 1 Cn2n. Vậy ta có f (n) = 2 ( Cn2n −Cn−12n ) = 2 1 n+ 1 Cn2n = 2Cn. Do đó Cn = 1 2 f (n) = 1 2 n+1 ∑ k=0 [ Ckn −Ck−1n ]2 . Nhận xét 1.1. Trong lời giải Bài toán 8, ta đã sử dụng đẳng thức Lagrange: Đẳng thức Lagrange phát biểu như sau: Với mọi số nguyên dương 0 ≤ k ≤ n, ta có n ∑ k=0 ( Ckn )2 = Cn2n (Đây là đẳng thức quen thuộc dễ chứng minh). Bài toán 1.10. Chứng minh rằng với mọi số nguyên dương 1 ≤ k ≤ n, ta có b n−12 c ∑ k=0 [ n− 2k n .Ckn ]2 = Cn−1 Lời giải. Đặt f (n) = b n−12 c ∑ k=0 [ n−2k n .C k n ]2 = Cn−1. Ta dễ thấy f (n) = 1 2 n ∑ k=0 [ n− 2k n ·Ckn ]2 = 1 2 n ∑ k=0 ( Ckn )2 − 2 n∑ k=0 ( Ckn )2 · k n + 2 n ∑ k=0 ( Ckn )2 · k2 n2 = 1 2 n ∑ k=0 ( Ckn )2 − 2 n∑ k=0 Ckn.C k−1 n−1 + 2 n ∑ k=0 ( Ck−1n−1 )2 = 1 2 n ∑ k=0 ( Ckn )2 − 2 n−1∑ k=0 Ck+1n ·Ckn−1 + 2 n−1 ∑ k=0 ( Ckn−1 )2 = 1 2 Cn2n − 2 ·Cn2n−1 + 2Cn−12n−2 = Cn−12n−2 [ 2n− 1 n − 2(2n− 1) n + 2 ] = 1 n Cn−12n−2 = Cn−1. 7 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Bài toán 1.11. Chứng minh rằng với mọi số nguyên dương 1 ≤ k ≤ n, ta có n ∑ k=0 (−1)k 2k+ 1 Ckn = 22n+1 (n+ 1)(n+ 2)Cn+1 . Lời giải. Ta có khai triển (1− x2)n = n ∑ k=0 (−1)kCknx2k. Do đó 1∫ 0 (1− x2)ndx = 1∫ 0 n ∑ k=0 (−1)kCknx2kdx. Tương đương pi 2∫ 0 cos2n+1 tdt = n ∑ k=0 (−1)kCkn · 1 2k+ 1 Tương đương 1 · 2 · 4 · 6 · · · (2n) 1 · 3 · 5 · · · (2n+ 1) = n ∑ k=0 (−1)k 2k+ 1 Ckn. Viết lại thành n ∑ k=0 (−1)k 2k+ 1 Ckn = n!2n 1 · 3 · 5 · · · (2n+ 1) n!2n [2 · 4 · 6 · · · (2n+ 2)] (2n+ 2)! = 22n+1n!(n+ 1)! (2n+ 2)! = 22n+1(n+ 1)!(n+ 1)!(n+ 2) (n+ 1)(n+ 2)(2n+ 2)! = 22n+1 (n+ 1)(n+ 2)Cn+1 . Vì Cn+1 = 1 n+ 2 · (2n+ 2)! (n+ 1)!(n+ 1)! . 2 Bài tập tương tự Một số đẳng thức sau đây bạn đọc có thể chứng minh trực tiếp, hoặc các kết quả của nó được tìm ra từ những bài toán đếmmà có. Việc chứng minh trực tiếp hay nghiên cứu, tìm tòi để tìm ra các đẳng thức này xin được dành cho bạn đọc. Bài 2.1. Với mọi số nguyên dương n ta có Cn = 1 2n+ 1 ·Cn2n+1. Bài 2.2. Cho số Catalan Cn = 1 n+ 1 ·Cn2n. Chứng minh rằng C2n−1 = n−1 ∑ k=0 [( Cn−k−12n−1 ) − ( Cn−k−22n−1 )]2 . 8 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Bài 2.3. Cho số Catalan Cn = 1 n+ 1 ·Cn2n. Chứng minh rằng n ∑ k=1 k n 2 Cn−12n−k−1 = Cn+1 −Cn. Bài 2.4. Cho số Catalan Cn = 1 n+ 1 · Cn2n. Đẳng thức sau đề cập đến trong một bài báo của David Callan năm 2010: n ∑ k=0 1 2n− 2k+ 1C k 2n−2k+1C n−k 2k = Cn. Bài 2.5. Cho số CatalanCn = 1 n+ 1 ·Cn2n. Đẳng thức sau được Arthur Cayley và Krikman tìm ra năm 1859: Cn−1 = 1 · 3 · 5 · · · (2n− 3) 1 · 2 · 3 · · · n · 2 n−1. Tài liệu [1] Nguyễn Văn Mậu, Chuyên đề chọn lọc tổ hợp và toán rời rạc, NXBGD 2010. [2] Ngô Thị Nhã, Nguyễn Văn Lợi, Các bài toán nổi tiếng về dãy Catalan, Tạp chí Toán học Tuổi trẻ. [3] Richard P. Stanley, Enumerative Combinatorics. 9