BMA1_003 אינדוקציה

אינדוקציה

אינדוקציה

הוכחה באינדוקציה היא שיטת הוכחה עבור טענות המערבות מספרים טבעיים. באופן יותר מדויק, אם יש טענה כי משהו נכון לכל טבעי, אז אפשר לנסות להוכיח לפי אינדוקציה. למשל את הטענה כי לכל טבעי מתקיים:

אפשר לנסות להוכיח באינדוקציה.
הוכחה באינדוקציה עובדת בצורה הבאה:

• שלב הבסיס: מוכיחים ישירות כי הטענה מתקיימת עבור . למשל, עבור הדוגמה שרשמנו, עבור השאלה היא האם צד שמאל של המשוואה עבור שווה לצד ימין של המשווה כאשר . בצד שמאל נקבל ובצד ימין נקבל ולכן יש שוויון.
• שלב המעבר/צעד האינדוקציה: אנו מוכיחים כי אם עבור מסויים, הטענה נכונה לכל , אז הטענה נכונה עבור . כך שלמשל בדוגמה שלנו, אנו מניחים כי עבור טבעי מסויים, מתקיים כי לכל :

אנו רוצים להוכיח כי הטענה נכונה עבור , כלומר כי:

נראה זאת: כיוון שעבור נקבל:

אז:

ובזאת סיימנו את ההוכחה באינדוקציה של הטענה כי לכל טבעי מתקיים כי: