การแข่งขัน Putnam เป็นข้อสอบแข่งขันคณิตศาสตร์สำหรับนักศึกษาปริญญาตรีที่ขึ้นชื่อว่าโหดหินที่สุด (แน่นอนว่ามันสามารถยากได้ยิ่งกว่า IMO สำหรับนักเรียนมัธยมเสียอีก) การแข่งจะจัดเพียงวันเดียวจบ โดยแบ่งออกเป็นช่วงเช้าและช่วงบ่าย แต่ละช่วงผู้เข้าแข่งขันจะได้รับโจทย์หกข้อมาทำในเวลาสามชั่วโมง แม้โจทย์จะเรียงลำดับความยากมาให้คร่าวๆ แต่โจทย์ทุกข้อก็คิดเป็นสิบคะแนนเท่ากันหมด และทั้งที่มีเพียงนักศึกษาที่หลงใหลในคณิตศาสตร์เท่านั้นที่จะมาสมัครแข่งขันในรายการสุดโหดเช่นนี้ แต่ค่าเฉลี่ยมัธยฐานจากโจทย์รวมทั้งสิบสองข้อก็มักจะตกอยู่ที่ศูนย์คะแนนเสมอ!

สำหรับการแข่งขันครั้งที่ 81 ที่ควรจะจัดในปี 2020 ที่ผ่านมา เดิมทีมันถูกวางแผนไว้ว่าจะจัดในวันเสาร์แรกของเดือนธันวาคมดังเช่นที่ผ่านมาทุกปี แต่ด้วยสถานการณ์ COVID-19 ก็ทำให้การแข่งขันถูกเลื่อนออกมายังปี 2021 พร้อมเปลี่ยนรูปแบบเป็นการส่งคำตอบผ่านอินเตอร์เน็ตแทน ซึ่งก็แลกมากกับการยกเลิกรางวัลทุนการศึกษาต่างๆ และนับว่านี่เป็นรอบการแข่งอย่างไม่เป็นทางการ

ส่วนตัวโหลดโจทย์มาลองแล้วพบว่าข้อท้ายๆ ยากจริงสมคำร่ำลือ แต่ข้อแรกๆ ที่ถือว่าเป็นข้อแจกแต้มก็ไม่ได้ยากจนเกินไป และสำหรับตอนนี้จะยกข้อ A2 (ข้อสองจากช่วงเช้า) มาเล่าให้ฟัง

A2. Let $k$ be a nonnegative integer. Evaluate $\sum_{j=0}^k 2^{k-j} \binom{k+j}{j}$.

Putnam Comptition, 2020

เตือนไว้ก่อนว่าโจทย์ค่อนข้างง่ายแถมยังสนุกมาก ระวังเลื่อนลงไปอ่านเฉลยโดยไม่ลองคิดเองก่อนแล้วจะเสียดายที่ปล่อยให้โจทย์น่ารักๆ แบบนี้หลุดมือไป 😜

---

ให้ $S_k = \sum_{j=0}^k 2^{k-j} \binom{k+j}{j}$ ลองถึกแทนค่า $k$ น้อยๆ ดู จะพบว่าคำตอบลำดับแรกๆ คือ $1, 4, 16, 64, \dots$ ดังนั้นก็เดาได้ไม่ยากว่าคำตอบกรณีทั่วไปต้องเป็น $S_k = 4^k$ อย่างแน่นอน

แต่อย่าลืมว่านี่คือข้อสอบคณิตศาสตร์ ถึงจะมีคำตอบที่ถูกต้องอยู่ในมือ แต่หากไม่สามารถแสดงบทพิสูจน์ให้เชื่อว่าคำตอบเป็นเช่นนั้นจริงๆ ก็จะชวดคะแนนเต็ม เช่นนั้นแล้วเราจะพิสูจน์ข้อนี้อย่างไร? อะไรคือสหัชญาณเบื้องหลังโจทย์ดังกล่าว?

ก่อนอื่นมาดูกันว่า $\binom{k+j}{j}$ หมายถึงอะไร โดยทั่วไปเมื่อเห็น $\binom{n}{r}$ หลายๆ พจน์ก็เดาได้เลยว่าต้องมีสามเหลี่ยมปัสกาลมาเกี่ยวข้องด้วยไม่ทางใดก็ทางหนึ่ง แต่ปรกติเรามักเห็นเลขข้างบนเป็นค่าคงตัวแล้วเลขข้างล่างเป็นดัชนีที่วิ่งตั้งแต่ $0$ ไปจนถึง $k$ (ซึ่งก็จะหมายถึงแถวแนวนอนแถวหนึ่งในสามเหลี่ยม) แต่คราวนี้เลขข้างบนกลับกลายเป็นดัชนีวิ่งด้วยเช่นกัน ดังนั้นพจน์ที่เราสนใจจะกลายเป็นแถวแนวทะแยงของสามเหลี่ยมปัสกาลนั่นเอง

\[\begin{array}{c|c} & 1 \\ & 1 \quad 1 \\ & 1 \quad 2 \quad 1 \\ \boxed{2^3} & \boxed{1} \quad 3 \quad 3 \quad 1 \\ \boxed{2^2} & 1 \quad \boxed{4} \quad 6 \quad 4 \quad 1 \\ \boxed{2^1} & 1 \quad 5 \quad \boxed{10} \quad 10 \quad 5 \quad 1 \\ \boxed{2^0} & 1 \quad 6 \quad 15 \quad \boxed{20} \quad 15 \quad 6 \quad 1 \\ & 1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1 \end{array}\]

ตัวอย่างพจน์ $\binom{k+j}{j}$ เมื่อ $k=3$ และ $j\in\lbrace0,1,\dots,k\rbrace$ ในสามเหลี่ยมปัสกาล

สังเกตว่า พจน์สุดท้ายจะเป็นตัวตรงกลางในแถวเลขคู่เสมอ เพราะมันคือพจน์ที่ $\binom{2k}{k}$

นอกจากนี้ ระลึกว่าแต่ละพจน์ใดๆ ในสามเหลี่ยมปัสกาลนั้นเกิดมาจากสองพจน์ในแถวก่อนหน้าบวกกัน หรือก็คือ $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ นั่นทำให้เราสามารถแบ่ง $\binom{k+j}{j} = \binom{k+j-1}{j-1} + \binom{k+j-1}{j}$

สนใจ $\binom{k+j-1}{j-1}$ ซึ่งเป็นซีกซ้ายของการแบ่ง สังเกตว่าสิ่งที่ต่างไปจากสามเหลี่ยมเดิม คือ พจน์สุดท้าย $\binom{2k}{k}$ หายไปเพราะแถวทะแยงโดนเลื่อนทะลุออกไปนอกสามเหลี่ยมปัสกาล

\[\begin{array}{c|c} & 1 \\ & 1 \quad 1 \\ \boxed{2^3} & \boxed{0} \quad 1 \quad 2 \quad 1 \quad \phantom{0} \\ \boxed{2^2} & \boxed{1} \quad 3 \quad 3 \quad 1 \\ \boxed{2^1} & 1 \quad \boxed{4} \quad 6 \quad 4 \quad 1 \\ \boxed{2^0} & 1 \quad 5 \quad \boxed{10} \quad 10 \quad 5 \quad 1 \\ & 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \\ & 1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1 \end{array}\]

ตัวอย่างซีกซ้าย $\binom{k+j-1}{j-1}$ เมื่อ $k=3$

ดังนั้นจะได้ว่า ผลรวมของซีกซ้ายนี้ (ที่แต่ละตัวถูกคูณด้วย $2^{k-j}$ แล้ว) คือ

\[\begin{align} L_k &= \sum_{j=1}^k 2^{k-j} \binom{k+j-1}{j-1} \\ &= \sum_{j=0}^{k-1} 2^{k-j-1} \binom{k+j}{j} \\ &= \frac12 \left( \sum_{j=0}^{k-1} 2^{k-j} \binom{k+j}{j} \right) \\ &= \frac12 \left( \sum_{j=0}^k 2^{k-j} \binom{k+j}{j} \right) - \frac12 \binom{2k}{k} \\ &= \frac{S_k}2 - \frac12 \binom{2k}{k} \end{align}\]

ต่อมาพิจารณาซีกขวาของการแบ่ง ซึ่งก็คือพจน์ที่อยู่ในรูป $\binom{k+j-1}{j}$ จะได้ว่ามันคือการเลื่อนแถวทะแยงในสามเหลี่ยมตั้งต้นขึ้นไปยังแถวก่อนหน้า โดยที่พจน์สุดท้ายไม่ได้หยุดตรงกลางพอดีเป๊ะ เพราะเป็นพจน์ $\binom{2k-1}{k}$ ที่เกินมานั่นเอง

\[\begin{array}{c|c} & 1 \\ & 1 \quad 1 \\ \boxed{2^3} & \boxed{1} \quad 2 \quad 1 \\ \boxed{2^2} & 1 \quad \boxed{3} \quad 3 \quad 1 \\ \boxed{2^1} & 1 \quad 4 \quad \boxed{6} \quad 4 \quad 1 \\ \boxed{2^0} & 1 \quad 5 \quad 10 \quad \boxed{10} \quad 5 \quad 1 \\ & 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \\ & 1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1 \end{array}\]

ตัวอย่างซีกขวา $\binom{k+j-1}{j}$ เมื่อ $k=3$

ย้ำอีกทีว่าเมื่อนำไปหาผลรวม แต่ละพจน์ต้องตัวคูณ $2^{k-j}$ ด้วย ทำให้ได้ว่าผลรวมของซีกขวาก็จะกลายเป็น

\[\begin{align} R_k &= \sum_{j=0}^k 2^{k-j} \binom{k-1+j}{j} \\ &= \left( \sum_{j=0}^{k-1} 2^{k-j} \binom{k-1+j}{j} \right) + \binom{2k-1}{k} \\ &= 2\left( \sum_{j=0}^{k-1} 2^{k-1-j} \binom{k-1+j}{j} \right) + \binom{2k-1}{k} \\ &= 2S_{k-1} + \binom{2k-1}{k} \end{align}\]

เนื่องจากเรามีผลรวมของซีกซ้ายกับซีกขวาแยกกันแล้ว เมื่อจับกลับมารวมกันมันก็คือผลรวมตั้งต้นที่เราต้องการหานั่นเอง

\[\begin{align} S_k &= L_k + R_k \\ &= \frac12 S_k - \frac12 \binom{2k}{k} + 2S_{k-1} + \binom{2k-1}{k} \end{align}\]

แต่สังเกตว่า $\binom{2k}{k}$ นั้นเป็นพจน์พิเศษเนื่องจากมันอยู่ตรงกลางพอดีในแถวเลขคู่ของสามเหลี่ยมปัสกาล ซึ่งจะทำให้ได้ผลข้างเคียงว่า $\binom{2k-1}{k-1} = \binom{2k-1}{k}$ นั่นก็คือ $\binom{2k}{k} = 2 \binom{2k-1}{k}$ และหักล้างพจน์คู่นี้ทิ้งไป หลังจากจัดรูปอีกเล็กน้อย สมการก็จะเหลือเพียง

\[S_k = 4S_{k-1}\]

ด้วยหลักอุปนัยก็จะเห็นว่า $S_k = 4^k$ ซ.ต.พ.