אינדוקציה מתמטית – איך כותבים הוכחה, עם דוגמאות
אפשר לתרגל את זה עכשיו — 3 פעולות ראשונות בחינם, בלי כרטיס אשראי.
איך כותבים הוכחה באינדוקציה — התשובה הקצרה
הוכחה באינדוקציה מתמטית מראה שטענה נכונה לכל מספר טבעי n, בשני שלבים. בשלב הבסיס בודקים שהטענה נכונה עבור המספר הראשון, בדרך כלל n = 1. בשלב המעבר מניחים שהטענה נכונה עבור n = k, ומוכיחים שהיא נכונה גם עבור n = k + 1. משני השלבים יחד נובע שהטענה נכונה לכל n טבעי, מהבסיס והלאה.
אפשר לחשוב על שורה של אבני דומינו. שלב הבסיס מפיל את האבן הראשונה. שלב המעבר מראה שכל אבן שנופלת מפילה את זו שאחריה. שני הדברים יחד מבטיחים שכל האבנים נופלות.
אינדוקציה נלמדת ב-5 יחידות. לפי מבנה הבחינה, בשאלון 35571 יש פרק של אינדוקציה, סדרות והסתברות.
מבנה ההוכחה: שלב הבסיס ושלב המעבר
כל הוכחה באינדוקציה נכתבת באותו סדר. כדאי לכתוב כותרת קצרה לכל שלב, כדי שיהיה ברור מה נבדק, מה מונח ומה מוכח.
| שלב | מה כותבים | על מה מקפידים |
|---|---|---|
| בסיס | מציבים את ה-n הראשון בשני האגפים ומשווים | לחשב כל אגף בנפרד |
| הנחת האינדוקציה | את הטענה עבור n = k | זו הנחה, לא מוכיחים אותה |
| מה צריך להוכיח | את הטענה עבור n = k + 1 | להחליף כל n ב-k + 1, בכל מקום |
| מעבר | דרך מההנחה אל הטענה עבור k + 1 | לציין היכן השתמשתם בהנחה |
| מסקנה | משפט סיום עם התחום | לכל n טבעי, או מהבסיס והלאה |
העצה הכי שימושית: לכתוב במפורש את מה שצריך להוכיח עבור k + 1 לפני שמתחילים בחישוב. כך יודעים לאן צריך להגיע, והאלגברה הופכת לדרך עם יעד ברור.
דוגמה 1 ודוגמה 2 — הוכחת סכום
דוגמה 1 — סכום המספרים האי-זוגיים. הטענה: 1 + 3 + 5 + … + (2n − 1) = n² לכל n טבעי. בסיס: עבור n = 1 אגף שמאל הוא 1 ואגף ימין הוא 1² = 1. הנחה: 1 + 3 + … + (2k − 1) = k². צריך להוכיח: 1 + 3 + … + (2k − 1) + (2k + 1) = (k + 1)². האיבר שנוסף הוא 2(k + 1) − 1, כלומר 2k + 1.
מעבר: לפי ההנחה, הסכום עד האיבר 2k − 1 שווה ל-k². לכן אגף שמאל שווה ל-k² + 2k + 1, וזה בדיוק (k + 1)². מסקנה: הטענה נכונה לכל n טבעי. בדיקה במספרים: עבור n = 3 הסכום הוא 1 + 3 + 5 = 9, וזה 3².
דוגמה 2 — סכום של מכפלות. הטענה: 1·2 + 2·3 + … + n(n + 1) = n(n + 1)(n + 2)/3. בסיס: עבור n = 1 אגף שמאל הוא 1·2 = 2, ואגף ימין הוא 1·2·3/3 = 2. הנחה: 1·2 + … + k(k + 1) = k(k + 1)(k + 2)/3. צריך להוכיח: 1·2 + … + k(k + 1) + (k + 1)(k + 2) = (k + 1)(k + 2)(k + 3)/3.
מעבר: לפי ההנחה, אגף שמאל שווה ל-k(k + 1)(k + 2)/3 + (k + 1)(k + 2). מוציאים את הגורם המשותף (k + 1)(k + 2) ומקבלים (k + 1)(k + 2)·(k/3 + 1). הסוגריים האחרונים שווים ל-(k + 3)/3, ולכן התוצאה היא (k + 1)(k + 2)(k + 3)/3. זה בדיוק אגף ימין. בדיקה במספרים: עבור n = 3 הסכום הוא 2 + 6 + 12 = 20, והנוסחה נותנת 3·4·5/3 = 20.
בשתי הדוגמאות אותו מהלך: מפרידים את האיבר האחרון, מחליפים את כל מה שלפניו לפי ההנחה, ומסדרים. הוצאת גורם משותף כמעט תמיד קצרה יותר מפתיחת כל הסוגריים.
דוגמה 3 — טענת התחלקות
הטענה: 4^n + 6n − 1 מתחלק ב-9 לכל n טבעי. בסיס: עבור n = 1 מקבלים 4 + 6 − 1 = 9, שמתחלק ב-9. הנחה: 4^k + 6k − 1 = 9m, עבור m שלם כלשהו. מכאן 4^k = 9m − 6k + 1. צריך להוכיח: 4^(k+1) + 6(k + 1) − 1 מתחלק ב-9.
מעבר: 4^(k+1) + 6(k + 1) − 1 = 4·4^k + 6k + 5. מציבים את 4^k מההנחה: 4(9m − 6k + 1) + 6k + 5 = 36m − 24k + 4 + 6k + 5 = 36m − 18k + 9. מוציאים 9 ומקבלים 9(4m − 2k + 1). הביטוי שבסוגריים הוא מספר שלם, ולכן הכול מתחלק ב-9.
בדיקה במספרים: עבור n = 2 מקבלים 16 + 12 − 1 = 27, ועבור n = 3 מקבלים 64 + 18 − 1 = 81. שניהם מתחלקים ב-9. בטענות התחלקות המהלך קבוע: כותבים את ההנחה כשוויון עם m, מבודדים את החזקה, ומציבים אותה בביטוי של k + 1.
דוגמה 4 — אי-שוויון
הטענה: 2^n > 2n + 1 לכל n טבעי שמקיים n ≥ 3. עבור n = 1 ו-n = 2 הטענה לא נכונה: 2 אינו גדול מ-3, ו-4 אינו גדול מ-5. לכן הבסיס הוא n = 3: 2³ = 8, ו-2·3 + 1 = 7. אכן 8 גדול מ-7.
הנחה: 2^k > 2k + 1, עבור k ≥ 3. צריך להוכיח: 2^(k+1) > 2(k + 1) + 1, כלומר 2^(k+1) > 2k + 3. מעבר: 2^(k+1) = 2·2^k. לפי ההנחה זה גדול מ-2(2k + 1), כלומר מ-4k + 2. נשאר להראות ש-4k + 2 גדול מ-2k + 3. ההפרש ביניהם הוא 2k − 1, והוא חיובי לכל k טבעי. לכן 2^(k+1) גדול מ-4k + 2, שגדול מ-2k + 3. בדיקה במספרים: עבור n = 4 מקבלים 16 מול 9.
באי-שוויון המעבר בנוי כשרשרת. מהביטוי של k + 1 יורדים, בעזרת ההנחה, לביטוי ביניים, וממנו לביטוי שרוצים. הצעד השני דורש נימוק משלו, ושם רוב הטעויות קורות.
למה צריך את שני השלבים
שלב מעבר בלי בסיס לא מוכיח דבר. ניקח את הטענה השגויה "n² + n הוא מספר אי-זוגי". אם מניחים ש-k² + k אי-זוגי, אז (k + 1)² + (k + 1) = k² + k + 2k + 2. זה מספר אי-זוגי ועוד מספר זוגי, כלומר אי-זוגי. המעבר עובד. אבל הבסיס נכשל: עבור n = 1 מקבלים 2, מספר זוגי. למעשה n² + n = n(n + 1) הוא מכפלה של שני מספרים עוקבים, ולכן הוא זוגי תמיד.
גם בסיס בלי מעבר לא מספיק. הביטוי n² − n + 41 נותן מספר ראשוני לכל n מ-1 עד 40. עבור n = 41 הוא שווה ל-41², שאינו ראשוני. בדיקה של הרבה מקרים אינה הוכחה.
הטעויות שחוזרות הכי הרבה
- לדלג על שלב הבסיס, או לחשב בו רק אגף אחד
- להחליף n ב-k + 1 רק בחלק מהמקומות. האיבר 2n − 1 הופך ל-2(k + 1) − 1, כלומר ל-2k + 1
- להתחיל מהשוויון שצריך להוכיח ולפתח אותו כאילו הוא כבר נכון. עדיף להתחיל מאגף אחד ולהגיע לאגף השני
- לא לציין היכן נעשה שימוש בהנחת האינדוקציה
- באי-שוויון: לדלג על הנימוק של הצעד השני בשרשרת
- לבדוק בסיס ב-n = 1 כשהטענה מתחילה ממספר אחר
- לכתוב מסקנה בלי התחום שבו הטענה הוכחה
הרבה טענות באינדוקציה עוסקות בסכומים של סדרות, ולכן כדאי לשלוט קודם בסדרה חשבונית ובסדרה הנדסית: איך ללמוד סדרות. לאי-שוויונים יש מדריך נפרד: איך ללמוד אי-שוויונים. על הפרקים בשאלון ועל כללי הבחירה ביניהם אפשר לקרוא במבנה הבגרות במתמטיקה.
שאלות נפוצות
מה ההבדל בין שלב הבסיס לשלב המעבר?
בשלב הבסיס בודקים שהטענה נכונה עבור המספר הראשון, בהצבה ישירה. בשלב המעבר מוכיחים קשר כללי: אם הטענה נכונה עבור k, היא נכונה גם עבור k + 1. הבסיס נותן נקודת התחלה, והמעבר מעביר את הנכונות ממספר למספר שאחריו.
האם שלב הבסיס הוא תמיד n = 1?
לא. הבסיס הוא המספר הראשון שעבורו הטענה אמורה להתקיים. אם הטענה מנוסחת עבור n ≥ 3, בודקים את n = 3. במקרה כזה ההוכחה תקפה מ-3 והלאה, ולא אומרת דבר על המספרים הקטנים ממנו.
איך מותר להניח את מה שרוצים להוכיח?
לא מניחים את הטענה לכל n. מניחים אותה עבור מספר אחד, k, ומוכיחים שמזה נובעת הטענה עבור k + 1. מה שמוכח בשלב המעבר הוא הקשר "אם נכון עבור k אז נכון עבור k + 1". יחד עם הבסיס, הקשר הזה נותן את הטענה לכל המספרים.
איך בודקים שנוסחה נכונה לפני שמוכיחים אותה?
מציבים n = 1, n = 2 ו-n = 3 ומשווים את שני האגפים. זו לא הוכחה, אבל זה תופס טעות העתקה בנוסחה לפני שמשקיעים זמן באלגברה של שלב המעבר.
באיזה שאלון בגרות יש אינדוקציה?
לפי מבנה הבחינות שמפרסם הפיקוח על הוראת המתמטיקה, בשאלון 35571 ב-5 יחידות יש פרק של אינדוקציה, סדרות והסתברות, ובו 2 שאלות.
רוצים לתרגל את זה עכשיו?
נועה מסבירה שלב אחר שלב בעברית פשוטה, ומתרגלת איתכם עד שזה מובן. לכל נושא כתובה שיטת הוראה משלו — כולל הטעות הנפוצה שנעצרת מראש.
לתרגול עם נועה ←3 פעולות ראשונות חינם, בלי כרטיס אשראי
רוצים לתרגל את זה בפועל?
התחילו עם אבחון רמה קצרנתקעתם? שאלו את נועה
רוצים לנסות?
נועה זמינה 24/7, מסבירה שלב אחר שלב בעברית, ובודקת גם פתרונות שכתבתם ביד. אפשר להתחיל בלי להירשם בכלל.
בואו נתחיל בחינם3 פעולות ראשונות בחינם · בלי כרטיס אשראי · אפשר לבטל בכל שלב
נכתב על ידי
אבי יחיאל
מייסד ומפתח של מורה מתמטיקה AI
בונה מוצרי לימוד דיגיטליים בעברית לשוק הישראלי.
התכנים באתר נשענים על תוכנית הלימודים של משרד החינוך ועל שאלוני הבגרות הרשמיים. איך נכתבים התכנים כאן