ความแตกต่างของStrong induction กับ induction

[jabza]

ตามที่บอกอะผม ผมไม่เข้าใจว่ามันต่างกันอย่างไร

เพราะ ตามที่ผมเข้าใจ การพิสูจน์แบบ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แล้วพิสูจน์ไม่ได้อ่างับ


ปล.ถ้าผมใช้ภาษาไม่ค่อยเข้าใจก้อบอกได้นะคับ เพราะยังงงๆอยู่เลย

[LightLucifer]

ผมว่าภาษามันดูงงๆนะครับ

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 อีกที

[jabza]

คับ เริ่มเข้าใจละ งั้นก้อแปลว่า ส่วนใหญ่strongจะใช้ในกรณีที่ P(n)มีมีกรณีแยก2กรณีคือ P(1),P(2),..P(10)เป็นแบบนี้
ส่วนP(n)ที่nมากกว่าเท่ากับ10เป็นอีกอย่าง เพราะพวกนี้มันจะใช้inductionธรรมดาไม่ได้ใช่ไหมครับ

[LightLucifer]

ก็ประมาณนั้นครับ

ผมว่าจะใช้ Strong ในกรณีที่ สมมติ P(k) เป็นจริงเพียงอย่างเดียวแล้วไม่เพียงพอที่จะพิสูจน์ส่วนจะยังไงก็ลองทำโจทย์ต่างๆดู

ผมก็ไม่ค่อยมั่นใจนะครับ -_-

[~king duk kong~]

แหม คุณ jabza เตรียมเข้าสอวน.แล้วสินะครับ
ขอบคุณครับ ผมก็เพิ่งเข้าใจ

[jabza]

ก้อนิดหน่อยครับ พอดีเปิดไปเจอMy math ก้อลองๆอ่านดู

ไว้รอสู้กับที่1ค่าย ^^