ความแตกต่างของStrong induction กับ induction
ตามที่บอกอะผม ผมไม่เข้าใจว่ามันต่างกันอย่างไร
เพราะ ตามที่ผมเข้าใจ การพิสูจน์แบบinductionมีขั้นตอนก้อคือ 1.พิสูจน์ว่า P(n) เมื่อn=1เป็นจริง 2.กำหนดให้P(n) เมื่อn=k เป็นจริง แล้วจะทำให้P(n) จะเป็นจริง เมื่อ n=k+1 และการพิสูจน์แบบ strong inductionก้อคือ 1.พิสูจน์ว่าP(n) เมื่อ n=1เป็นจริง 2.กำหนดให้P(n)เป็นจริง เมื่อ n=1,2,3,...k เป็นจริง จะทำให้P(n)เป็นจริงเมื่อn=k+1 เมื่อ nน้อยกว่าเท่ากับk แล้วจะทำให้P(n)เป็นจริงเมื่อ n = k+1 ผมสงสัยตรงข้อ2.ของstrong inductionที่ว่า"กำหนดให้P(n)เป็นจริง เมื่อ n=1,2,3,...k เป็นจริง จะทำให้P(n)เป็นจริงเมื่อn=k+1 เมื่อ nน้อยกว่าเท่ากับk แล้วจะทำให้P(n)เป็นจริงเมื่อ n = k+1" คือว่ามันกำหนดให้n=kเป้นจริงไม่รวบรัดกว่าเหรอครับ และทำไมต้องกำหนดให้n=1,2,3...k-1เป็นจริงด้วย มันจำเป็นด้วยเหรอครับ ผมรู้สึกว่าเหมือนกับว่า strong induction มันเป็นส่วนหนึ่งของinductionคือว่า ไม่จำเป็นต้องใช้strong เพียงแค่ใช้induction ก้อสามารถแก้ได้แล้ว แล้วจะมีstrongเพื่อ??(คล้ายๆกับFermat's TheoremกับEuler's Theorem ที่เป็นส่วนหนึ่งรึเปล่าครับ) ทางที่ดีผมขอโจทย์Basic Basic ที่มันจำเปนต้องใช้strong เพราะใช้inductionแล้วพิสูจน์ไม่ได้อ่างับ ปล.ถ้าผมใช้ภาษาไม่ค่อยเข้าใจก้อบอกได้นะคับ เพราะยังงงๆอยู่เลย |
ผมว่าภาษามันดูงงๆนะครับ
Strong ในหนังสือผมเขียนว่า 1. $P(1)$ เป็นจริง 2. $\forall k\in \mathbb{N} , P(1)\wedge P(2)\wedge...\wedge P(k)$ เป็๋นจริง $\rightarrow P(k+1)$ เป็นจริง จะได้ว่า $P(n)$ สำรับทุกจำนวนนับ $n$ ส่วนโจทย์ นิยามลำดับ $a_n$ โดย $a_1=1,a_2=3$ และ $a_n=2a_{n-1}-a_{n-2}$ สำหรับ $n\geqslant 3$ จงพิสูจน์ว่า $\forall n\in \mathbb{N} ,a_n=2n-1$ ส่วนที่ว่าจะมี Strong ทำไม ยกตัวอย่างจากโจทย์ ดูจากโจทย์แล้ว ถ้าไม่สมมติให้ทุก $m\leqslant k$ เป็นจริง จะสรุปไม่ได้ว่า $a_{k+1}$ เป็นจริงเพราะ $a_{k+1}=2a_k-a_{k-1}$ แต่เราไม่รุ้ว่า $a_k=2k-1$ และ $a_{k-1}=2(k-1)-1$ หรือป่าวเพราะฉนั้นจึงต้องสมมติมาอ่ะครับ นี่คือความเข้าใจของผมนะครับ ส่วนจะถูกผิดรอให้เซียนมา confirm อีกที :sweat::sweat: |
คับ เริ่มเข้าใจละ งั้นก้อแปลว่า ส่วนใหญ่strongจะใช้ในกรณีที่ P(n)มีมีกรณีแยก2กรณีคือ P(1),P(2),..P(10)เป็นแบบนี้
ส่วนP(n)ที่nมากกว่าเท่ากับ10เป็นอีกอย่าง เพราะพวกนี้มันจะใช้inductionธรรมดาไม่ได้ใช่ไหมครับ |
ก็ประมาณนั้นครับ
ผมว่าจะใช้ Strong ในกรณีที่ สมมติ P(k) เป็นจริงเพียงอย่างเดียวแล้วไม่เพียงพอที่จะพิสูจน์ส่วนจะยังไงก็ลองทำโจทย์ต่างๆดู ผมก็ไม่ค่อยมั่นใจนะครับ -_- |
แหม คุณ jabza เตรียมเข้าสอวน.แล้วสินะครับ
ขอบคุณครับ ผมก็เพิ่งเข้าใจ |
ก้อนิดหน่อยครับ พอดีเปิดไปเจอMy math ก้อลองๆอ่านดู
ไว้รอสู้กับที่1ค่าย ^^ |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 02:38 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha