โจทย์ real analysis เบื้องต้นอีกแล้วครับ เกี่ยวกับ Mathematical Induction

[rigor]

ขอความกรุณาท่านผู้รู้ช่วยเขียนพิสูจน์แบบฝึกหัดข้อนี้ให้ด้วยครับ

Let S be a subset of N such that
(a) 2^k ฮ S for all k ฮ N, and
(b) if k ฮ S and k ณ 2, then k-1 ฮ S.

Prove that S = N.

ผมลองเริ่มจาก (a) ได้ว่า P(2) เป็นจริง จากนั้นด้วย (b) ได้ว่า P(1) เป็นจริงด้วย จากนั้นก็ใบ้กินครับ มันวิ่งถอยหลังแบบนี้แล้วทำอะไรไม่ถูกเลย

ระยะนี้จะมีคำถามแบบนี้บ่อยๆ เกรงใจเหมือนกันนะคับ กำลังจะสั่งซื้อ Instructor's manual อยู่แล้ว ยังไงช่วงนี้ขอรบกวนสักพักนะคับ - -a ขอบคุณครับ

[passer-by]

ตอนนี้ ยังคิดแบบ induction ไม่ออก เอาแบบนี้ไปก่อนนะครับ

เนื่องจาก Sฬ N เป็นจริงจากโจทย์อยู่แล้ว
ดังนั้น ถ้าจะพิสูจน์ S= N จึงเหลือเพียงแสดงว่า Nฬ S

Let aฮ N

ถ้า a=2^k สำหรับบางค่า kฮN เมื่อ apply (a) จะได้ aฮS ตามต้องการ

ส่วนกรณีที่ a เขียนเป็น 2^k ไม่ได้ พบว่า
(i) 1ฮS เนื่องจาก 2¹ฮS และapply (b)
(ii) เพราะ มีจำนวนนับ m ซึ่ง 2^m <a<2^m+1 เสมอ
ทำให้ a เขียนได้ในรูปใดรูปหนึ่งจาก { 2^m+1,2^m+2,...,2^m+1-1}

จาก 2^m+1ฮS (เพราะ (a))
และจาก (b) จะได้ 2^m+1-1ฮS ด้วย หลังจากนั้นก็ apply (b) กับสมาชิกที่เหลือในเซตด้วยเหตุผลทำนองเดียวกัน ก็จะพบว่าทุกสมาชิกในเซตดังกล่าวอยู่ใน S หรือ aฮS

[rigor]

กระจ่างแล้วครับ ขอบคุณมากๆๆครับ

[SOS_math]

จริง ๆ ที่ passer-by ทำมาก็คือ Mathematical Induction นั่นเอง ลองสังเกตดี ๆ จะพบว่า passer-by พิจารณา P(n) แทนข้อความ n เป็นสมาชิกของ S ครับ

[warut]

ข้อความเดิมของคุณ rigor:
ขอความกรุณาท่านผู้รู้ช่วยเขียนพิสูจน์แบบฝึกหัดข้อนี้ให้ด้วยครับ

Let S be a subset of N such that
(a) 2^k ฮ S for all k ฮ N, and
(b) if k ฮ S and k ณ 2, then k-1 ฮ S.

Prove that S = N.

ถ้าผมเข้าใจไม่ผิดข้อความที่ต้องการให้พิสูจน์ข้างบนนั้นคือ หลักการของการทำสิ่งที่เรียกว่า "backward induction" ซึ่งมีชื่อเสียงพอควรเพราะได้ถูกนำเอาไปใช้ในการพิสูจน์อสมการ A.M.-G.M. แต่ยังไงคงต้องให้ผู้เชี่ยวชาญด้านอสมการมายืนยันอีกทีครับ

เนื่องจากเราต้องการพิสูจน์สิ่งที่เป็นพื้นฐานระดับนี้ การพิสูจน์ให้ rigorous คงต้องใช้ความระมัดระวังเป็นพิเศษ ถ้าใช้ intuition อย่างเดียวอาจผิดได้ครับ ลองนึกถึงภาพว่าถ้าเราต้องการพิสูจน์ว่า Principle of Mathematical Induction เป็นจริงก็ไม่ใช่ง่ายๆ เพราะเราเห็นจะๆอยู่แล้วว่ามันเป็นจริง (ตามแบบการล้มของโดมิโน) เราถึงต้องไปลากเอาพวก Well-Ordering Principle มาช่วยพิสูจน์ครับ

การพิสูจน์ต่อไปนี้ผมคิดขึ้นเองจึงคงไม่ใช่อันที่ดีที่สุดหรืออันที่เป็นมาตรฐาน แต่ผมก็ค่อนข้างมั่นใจว่า rigorous ยังไงก็ตามขอให้ผู้รู้มาช่วยให้ความกระจ่างด้วยจะดีที่สุด (อย่าเอาแต่อ่านแล้วยิ้มเยาะ - ใครทำงั้นขอให้จู๊ดๆเลย )

พิสูจน์

เริ่มจากการใช้ induction ธรรมดาพิสูจน์ว่า \(2^n>n\) สำหรับทุก \(n\in\mathbb N\) ซึ่งเดี๋ยวเราจะต้องใช้ความจริงอันนี้ครับ

ต่อไปเป็นการพิสูจน์ข้อความหลักโดยใช้ contradiction

ถ้า \(S\ne\mathbb N\) ดังนั้นจาก Well-Ordering Principle เราจะได้ว่า \(A:=\mathbb N\setminus S\) จะต้องมีสมาชิกที่น้อยที่สุด สมมติให้เป็น \(m\)

ให้สังเกตว่าข้อความ (b) ซึ่งก็คือ\[สำหรับ\;k\ge2,\quad k\in S\quad\Rightarrow
\quad k-1\in S\]สมมูลกับ\[สำหรับ\;k\ge2,\quad k-1\not\in S\quad
\Rightarrow\quad k\not\in S\]และสมมูลกับ\[สำหรับ\;n\ge1,\quad
n\not\in S\quad\Rightarrow\quad n+1\not\in S\]ซึ่งสมมูลกับ\[
สำหรับ\;n\ge1,\quad n\in A\quad\Rightarrow\quad n+1\in A\](ตรงนี้ทำละเอียดหน่อย เผื่ออาจมีใครงงครับ)

จากที่เรารู้ว่า \(m\in A\) และ \(n\in A\Rightarrow n+1\in A\) ดังนั้นโดย induction เราจึงได้ว่า\[m,m+1,m+2,\dots\in A\]นั่นคือ \(n\in A\) สำหรับทุก \(n\ge m\)

ดังนั้นจาก \(2^m>m\) เราจึงได้ว่า \(2^m\in A=\mathbb N\setminus S\) ด้วย ทำให้เกิดข้อขัดแย้งกับข้อความ (a) ที่ว่า \(2^m\in S\) เราจึงสรุปได้ว่าจริงๆแล้ว \(S=\mathbb N\) ครับ

[nooonuii]

Backward induction ใช้ในการพิสูจน์อสมการ AM-GM ครับ หาอ่านวิธีพิสูจน์แบบนี้ได้จากบทความ
" Inequalities " เขียนโดย Richard Bellman อยู่ในวารสาร Mathematics Magazine เล่มที่ 28 ปี 1954-55 หน้า 21-26

[warut]

โอ้โห...ข้อมูลแน่นปึ๊กจริงๆ ขอบคุณมากครับคุณ nooonuii

[rigor]

บังเอิญแวะกลับมาอ่านครับ ได้รู้อะไรเพิ่มอีกแล้ว ขอบคุณมากครับ รักที่นี่จังเลย