อุปนัยสองชั้นกับ $\binom{n}{r}$
ตอนเรียนการนับและการจัดหมู่ครั้งแรก เห็นนิยาม $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}\]มาพิสูจน์แบบอุปนัยธรรมดาๆ ก็ออกแล้ว 😂

author