ปัญหาชิงรางวัลข้อที่ 12: Divisibility of Central Binomial Coefficients

[warut]

จงพิสูจน์ว่า สำหรับทุกจำนวนเต็มบวก $n$ แล้ว$$(n+1)\, \Bigg| \, {2n\choose n}$$ป.ล. เห็นว่ายังหัวค่ำอยู่ก็เลยรีบเอาโจทย์มาให้ก่อน แล้วจะตามไปตอบกระทู้ที่เกี่ยวข้องทีหลังครับ

[nongtum]

เราจะพิสูจน์เอกลักษณ์ต่อไปนี้ $$C_n=\frac{1}{2n+1}{{2n+1}\choose{n}}=\frac{1}{n+1}{{2n}\choose{n}}$$
เอกลักษณ์นี้เป็นจริงเนื่องจาก $${{2n+1}\choose{n}}
=\frac{(2n+1)\cdot 2n\cdots (n+2)}{n!}=\frac{2n+1}{n+1}\cdot\frac{2n!}{(n!)^2}
=\frac{2n+1}{n+1}{{2n}\choose{n}}$$ ซึ่งสิ่งที่ต้องการพิสูจน์ตามมาจากความจริงที่ว่า (n+1,2n+1)=1 ###
(Edited: Danke sehr nong Nithi ^_^)

หมายเหตุ: $C_n$ เป็น n^th catalan numbers หากต้องการอ่านเพิ่มเติมสามารถอ่านได้จากลิงค์ด้านล่างครับ
central binomial coefficients
Catalan number from mathworld
Central Binomial Coefficient identities

[nithi_rung]

ข้อความเดิมของคุณ nongtum:
ซึ่งสิ่งที่ต้องการพิสูจน์ตามมาจากความจริงที่ว่า $(n+1)\not| 2n+1$

ผมว่าเหตุผลน่าจะเป็นเพราะ $$gcd(n+1,2n+1)=1$$ มากกว่านะครับ

ขอเสนออีกวิธีนึงครับ พิจารณาตามนี้
$${{2n+1}\choose{n+1}}-2{{2n}\choose{n+1}}
=\frac{(2n+1)!}{(n+1)!n!}-\frac{2(2n)!}{(n+1)!(n-1)!}
=\frac{(2n+1)!-2n(2n)!}{(n+1)!n!}
=\frac{(2n)!}{(n+1)!n!}
=\frac{1}{n+1}{{2n}\choose{n}}$$

เนื่องจาก ${{2n+1}\choose{n+1}}$ และ ${{2n}\choose{n+1}}$ เป็นจำนวนเต็ม จะได้ว่า $\frac{1}{n+1}{{2n}\choose{n}}$ เป็นจำนวนเต็มด้วย ดังนั้น
$$(n+1)\, \Bigg| \, {2n\choose n}$$

[nongtum]

เอิ๊ก จริงด้วยๆ ขอบคุณน้อง nithi_rung มากๆครับสำหรับคำแนะนำ ตอนพิมพ์ตอนแรกนึกไม่ออกจะอ้างอะไร หากใครเข้ามาตอนแรกๆคงเห็นผมใช้การอ้างว่า $C_n$ เป็นจำนวนเต็มด้วยซ้ำ... ไปแก้แล้วครับ

[warut]

ดีใจจังที่เห็นน้อง nithi_rung ผู้เคยได้รับเหรียญโอลิมปิกมาแล้วมาเล่นด้วย

วิธีทำของคุณ nongtum แปลกดี ผมชอบครับ ส่วนของน้อง nithi_rung ก็เป็นแบบง่ายๆที่ผมไม่เคยเห็น อ้อ ขอบใจน้อง nithi_rung ที่ช่วยเช็คคำตอบของคนอื่นให้ด้วยนะครับ

ผมยังรอการพิสูจน์แบบอื่นๆ (น่าจะมีอีกนา) อยู่นะครับ

ข้อนี้เป็นข้อแรกที่ผมเอามาจากหนังสือที่เขารวมโจทย์ไว้ (โดยไม่มีประสพการณ์เกี่ยวกับโจทย์ข้อนี้จากที่อื่นมาก่อนเลย) ผมรู้สึกว่าข้อนี้ยากตรงที่ทุกครั้งที่ผมเริ่มทำใหม่ (หลังจากที่ลืมเฉลยไปแล้ว) ผมจะเริ่มต้นด้วยการพยายามใช้ induction ทุกทีเลย (เนื่องจากเป็นโจทย์ประเภทให้พิสูจน์ว่า $\forall n\in\mathbb N\dots$) แล้วก็ไม่เคยสำเร็จ สงสัยมันจะใช้กับข้อนี้ไม่ได้จริงๆแฮะ

อ้อ เวลาใช้ฟังก์ชัน gcd ใน LaTeX อย่าลืมใส่ \ ข้างหน้า (เป็น \gcd) ด้วยนะครับ

[warut]

Hint: ลองหาดูสิครับว่าพอจะมีวิธีอื่นนอกจากที่น้อง nithi_rung แสดงไปแล้วอีกไหม ที่เราสามารถเขียน $$\frac{1}{n+1} {2n \choose n}$$ ในรูปของผลบวกหรือผลต่างของสัมประสิทธิ์ทวินามได้

[warut]

อืม ไม่รู้จะ hint ว่าไงแล้วครับ เอาเป็นแจกคะแนนไปก่อนละกัน ครับ...คุณ nongtum และน้อง nithi_rung รับไปคนละ 5 คะแนนครับ

[nooonuii]

คำตอบนี้ไม่ขอรับคะแนนละกัน เอามาจาก Hint ของคุณ Warut ครับ

\( \displaystyle{\frac{1}{n+1}{2n \choose n} = {2n \choose n} - \frac{n}{n+1}{2n \choose n} = {2n \choose n} - {2n \choose n+1}} \)

[warut]

อ้าว ทำไมไม่เอาคะแนนล่ะครับ

[nooonuii]

ข้อความเดิมของคุณ warut:
อ้าว ทำไมไม่เอาคะแนนล่ะครับ

ผมว่าวิธีคิดก็ไม่ต่างจากของน้อง nithi ซักเท่าไหร่น่ะครับ แถมส่งการบ้านช้าอีก น่าจะให้เครดิตกับคำตอบของน้อง nithi มากกว่าครับ

[warut]

คุณ nooonuii ไม่ต้องเป็นห่วงเรื่องพวกนั้นหรอกครับ แค่เข้ามาเล่นก็นับเป็นเกียรติอย่างสูงแล้ว (ไม่ได้หมายถึงเฉพาะคุณ nooonuii คนเดียวนะครับ แต่หมายถึงทุกๆคนที่เข้ามาร่วมตอบคำถาม) เรื่องคะแนน เรื่องช้าเร็ว และเรื่องอื่นๆ ปล่อยให้เป็นภาระของผมเถอะครับ

ผมรอคำตอบอันของคุณ nooonuii มาตั้งเกือบเดือน ไม่ให้คะแนนได้ไง ถ้าผมเห็นว่าช้าไป คงเฉลยไปแล้วไม่รออยู่อย่างนี้หรอกครับ ผมว่าคำตอบอันนี้สวยกว่าของน้อง nithi_rung อีกเพราะใช้ binomial coefficients แค่ 2 ตัว (ของน้อง nithi_rung เทียบเท่ากับใช้ 3 ตัว) คำตอบอีกอันหนึ่งที่ใช้ได้ก็คือ
$$\frac{1}{n+1} {2n\choose n} = 2{2n\choose n} - {2n+1\choose n}$$
สรุปว่าคุณ nooonuii รับไปอีก 5 คะแนนสำหรับคำตอบอันนี้ครับ

[nooonuii]

ขอบคุณครับ

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