ตอนเรียนการนับและการจัดหมู่ครั้งแรก เห็นนิยาม $n!$ กับ $n!/r!$ แล้วก็ไม่ได้ตะหงิดติดใจอะไร แต่พอมาถึง $\binom{n}{r}$ แล้วแอบคาใจแปลกๆ ว่าทำไมตัวเลขตัวนี้ถึงเป็นจำนวนเต็มได้ … แน่นอนหละว่ามันเป็นการนับ ยังไงซะเราคงไม่นับสิ่งที่สนใจด้วยเลขที่ไม่ใช่จำนวนเต็มเป็นแน่ แต่มันจะมีวิธีการพิสูจน์แบบอื่นที่อธิบายได้รัดกุม ขจัดปัดเป่าข้อข้องใจนี้ทิ้งไป ไม่ชวนให้กลับมาสงสัยซ้ำๆ ในเรื่องเดิมมั้ย?

ผ่านมาน่าจะเกินสิบปี จู่ๆ ก็นึกวิธีพิสูจน์ที่ฟังดูเข้าท่า (อย่างน้อยก็กับตัวเอง) ที่ทำได้ผ่านการอุปนัยสองชั้น (double induction) ออก ซึ่งนี่เป็นท่าที่เจ๋งดีเวลาต้องพิสูจน์บนตัวแปรหลายตัว

---

แต่ก่อนอื่น จะขอเปลี่ยนปัญหาตั้งต้นไปเขียนอยู่ในรูปนี้แทน “$r!$ หารลงตัวกับผลคูณของจำนวนธรรมชาติที่เขียนติดกัน $r$ ตัว” หรือก็คือ สำหรับ $r,k \in \mathbb{N}$ เราต้องการพิสูจน์ว่า

\[\forall r \forall k\left[r! \mid \prod_{i=0}^{r-1} (k+i) \right]\]

ดังนั้น การอุปนัยขั้นแรกบน $r$ คือ

\[P(r):\; \forall k \left[ r! \mid \prod_{i=0}^{r-1}(k+i) \right]\]

ซึ่งเราย่อมเห็นได้ทันทีว่า $P(1)$ จริงแน่นอน ด้วยสมมติฐานของการอุปนัย สมมติให้ $P(r)$ จริงเพื่อพิสูจน์ $P(r+1)$

ถึงตอนนี้ เราจะทำการอุปนัยซ้อนลงไปอีกครั้งบน $k$ ดังนี้

\[P(r, k):\; r! \mid \prod_{i=0}^{r-1}(k+i)\]

เราก็จะเห็นอีกว่า $P(r+1, 1)$ จริง (เพราะด้านขวาของการหารลงตัวก็คือนิยามของแฟคทอเรียลเลย) ทำให้เราตั้งสมมติฐานว่า $P(r+1, k)$ จริงเพื่อพิสูจน์ $P(r+1, k+1)$ ต่อไป

จากสมมติฐาน $P(r+1, k)$ ได้ว่า

\[\begin{align} (r+1)! \mid \prod_{i=0}^r (k+i) \label{eq:p(r+1,k)}\tag{1} \end{align}\]

และจากสมมติฐาน $P(r)$ ซึ่งจริงสำหรับทุกค่า $k$ เลือกพิจารณา $P(r)$ ที่ $k+1$ จะได้

\[r! \mid \prod_{i=0}^{r-1} (k+1+i)\]

ซึ่งหมายความว่า มี $s \in \mathbb{N}$ บางตัวที่ทำให้

\[\begin{align} sr! = \prod_{i=0}^{r-1} (k+1+i) \label{eq:sr!prod}\tag{2} \end{align}\]

ถึงตอนนี้จะย้อนกลับไปจัดรูป $\eqref{eq:p(r+1,k)}$ ให้กลายเป็น

\[(r+1)r! \mid k \prod_{i=0}^{r-1} (k+1+i)\]

แล้วแทนค่าจาก $\eqref{eq:sr!prod}$ ลงไป ก็จะได้

\[(r+1)r! \mid ksr!\]

เพราะทั้งสองข้างของการหารลงตัว มีตัวประกอบเป็น $r! \neq 0$ เช่นกัน ดังนั้น

\[\begin{align} r+1 \mid ks \label{eq:r1ks}\tag{3} \end{align}\]

นอกจากนี้ เรายังรู้อีกว่า $r+1$ หารลงตัวกับผลคูณของจำนวนเต็มใดๆ กับตัวมันเอง เราจึงได้

\[\begin{align} r+1 \mid (r+1)s \label{eq:r1r1s}\tag{4} \end{align}\]

รวม $\eqref{eq:r1ks}$ กับ $\eqref{eq:r1r1s}$ เข้าด้วยกัน

\[r+1 \mid (k+r+1)s\]

คูณทั้งด้านซ้ายและขวาของการหารลงตัวด้วย $r!$ แล้วแทนค่าจาก $\eqref{eq:sr!prod}$ กลับคืนลงไป ก็จะได้

\[(r+1)r! \mid (k+r+1) \prod_{i=0}^{r-1} (k+1+i)\]

จัดรูปอีกนิดเดียวก็จะกลายเป็น

\[(r+1)! \mid \prod_{i=0}^{r}(k+1+i)\]

หรือก็คือ $P(r+1, k+1)$ เป็นจริงด้วยนั่นเอง ซ.ต.พ.

---

คิดบทพิสูจน์ซะซับซ้อนยืดยาว เพื่อที่จะไปเห็นว่าคนอื่นใช้อัตลักษณ์

\[\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\]

มาพิสูจน์แบบอุปนัยธรรมดาๆ ก็ออกแล้ว 😂