neizod's speculation

insufficient data for meaningful answer

อุปนัยสองชั้นกับ ${n \choose r}$

Sunday, September 30, 2018, 11:17 PM

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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