הוכחה באינדוקציה

אינדוקציה היא שיטה הוכחה מתמטית. נשתמש באינדוקציה על פי רוב כדי להוכיח את נכונותה של טענה או של משוואה אלגברית עבור משפחת המספרים השלמים החל מהערך אפס או החל מהערך אחד והלאה.

דרך הפעולה של האינדוקציה מתבצעת בשני שלבים:

1. הוכחת נכונות המשוואה לערך התחתון בתחום הקיום שלה, פשוט על-ידי הצבתו בה.
2. הוכחה שאם המשוואה נכונה לערך n כלשהו אזי היא בהכרח נכונה גם לערך השלם הבא בקבוצה, n+1. מנכונות עבור ערך n מתבצעת הקשה (אינדוקציה בלעז) עבור הערך n+1.

בעזרת שני שלבים אלו מתקבלת הטענה שהמשוואה נכונה לערך הראשון בתחום ושממנו והלאה המשוואה תמשיך להיות נכונה עבור כל ערך בתחום הקיום, כי אם היא נכונה לערך n כלשהו היא נכונה גם לערך n+1.

דוגמה

טענה: x² ≥ x עבור כל x שלם חיובי.

הוכחה באינדוקציה:

שלב 1 – הערך התחתון בתחום הקיום של אי-השוויון הוא x = 1. נוכיח שהטענה נכונה עבור x=1 על-ידי הצבה בתוך המשוואה.

x² ≥ x
1² ≥ 1

שלב 2 – אחרי שהוכח שהטענה נכונה עבור x=1 נוכיח שאם הטענה נכונה עבור ערך x כלשהו אזי היא נכונה גם עבור ערך x+1 הבא אחריו בתחום הקיום של הטענה. לשם כך, בכל מקום באי-השוויון בו מופיע x נציב את הביטוי x+1.

(x+1)² ≥ (x+1)
x² + 2x + 1 ≥ x + 1
x² + x ≥ 0

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

(x² + x) / x ≥ 0
x + 1 ≥ 0

אי-השוויון החדש שהתקבל מתקיים תמיד בתחום הקיום הכולל רק את המספרים החיוביים.

לכן, הוכח בשיטת האינדוקציה שאי-השוויון המקורי נכון עבור כל x שלם וחיובי.

[לפרק הקודם | לפרק הבא]

[ עמוד ראשי - אלגברה והנדסה | סדרות וממוצעים : סדרה חשבונית | סדרה הנדסית | ממוצע חשבוני | ממוצע חשבוני משוקלל | ממוצע הנדסי | ממוצע הנדסי משוקלל | מספרים ראשוניים | הוכחה באינדוקציה ]