אינדוקציה מתמטית
ברב ההוכחות באינפי אנו משתמשים באינדוקציה,
האינדוקציה נועדה להוכיח נכנותו של ביטוי או טענה כך שבלעדי
האינדוקציה הינו אמורים להציב בביטוי אינסוף מיספרים.
אקסיומת האינדוקציה המתמטית :
אם טענה המתייחסת למספרים טבעיים מקיימת את התכונות
הבאות
1) הטענה נכונה עבור n=1
2) מההנחה שהטענה נכונה עבור n=k נובע שהיא נכונה עבור n=k+1
אז הטענה נכונה לכל n טבעי
ניסוח שקול:
נתונה סדרה של מספרים טבעיים ...n 1,n
2, n 3אם טענה מסויימת נכונה עבור n 1
(האיבר הראשון)
ואם מההנחה שהיא נכונה עבור n k (האיבר ה-k) נובע שהיא
נכונה עבור n k+1
(האיבר ה-k+1)
אז היא נכונה לכל איבר בסדרה
שלבים בהוכחת האינדוקציה:
שלב א' - בודקים את נכונות הטענה
עבור n=1 ע"י שמציבים 1 במקום n.
(אם הטענה נכונה רק החל מ-n=m כאשר 1 < m וטבעי אז בודקים את הטענה
עבור m )
שלב ב' - מניחים את הנחת האינדוקציה , כלומר
מניחים שהטענה נכונה עבור n=k ,
רושמים את הטענה כאשר במקום n מציבים k.
שלב ג' - רושמים את מה שצריך להוכיח עבור n=k+1
,
כלומר רושמים את הטענה כאשר במקום n מציבים k+1.
שלב ד' - מוכיחים את נכונות הטענה עבור n=k+1
בהסתמך על הנחת האינדוקציה
עבור n=k .
|