דוגמה פדגוגית: מבקשים מהתלמידים לבדוק את הטענה: \(P(n):\) “המספר \(2^n - 1\) הוא ראשוני.”

תלמידים בודקים: \(n=2: 2^2-1=3\) – ראשוני \(n=3: 2^3-1=7\) – ראשוני \(n=5: 2^5-1=31\) – ראשוני ומסיקים בטעות: “נראה שזה תמיד ראשוני.” אבל עבור \(n=11\), למשל, \(2^{11}-1 = 2047 = 23 \cdot 89\) – שאינו ראשוני.

זו דוגמה מצוינת להראות שתצפיות על מקרים פרטיים יכולות להטעות. רק הוכחה כללית (עוד לפני אינדוקציה) נותנת ודאות.

בבסיס אנו מוכיחים באופן מדויק: \(P(n_0)\) נכונה עבור ערך התחלתי מסוים (למשל \(n_0=1\) או \(n_0=0\) או \(n_0=3\)).

דימוי לתלמידים:

דמיינו מדרגות שמטפסות עד אינסוף. שלב הצעד אומר: "אם אתה כבר עומד על מדרגה מס' \(k\), אתה יכול להגיע למדרגה \(k+1\)". אבל אם אף אחד לא עומד על מדרגות בכלל (אין בסיס) – אף אחד לא מתחיל לטפס.

דוגמה 1: צעד נכון, בסיס שגוי

נבחן את הטענה:

\(P(n):\quad n \ge 2\) לכל \(n \in \mathbb{N}\).

שלב הצעד: נניח \(k \ge 2\) (כלומר \(P(k)\) נכונה). אז ברור ש-\(k+1 \ge 2\), ולכן \(P(k+1)\) נכונה. כלומר הצעד האינדוקטיבי תקין.

אבל שלב הבסיס עבור \(n=1\) נכשל, כי: \(1 \not\ge 2\). מסקנה: הטענה אינה נכונה לכל \(n\), למרות שהצעד לבד "עובד".

דוגמה 2: בסיס נכון, צעד שגוי

נבחן טענה בדיונית (לא נכונה):

\(P(n):\quad 2n \le n+1\) לכל \(n \in \mathbb{N}\).

שלב הבסיס: עבור \(n=1\) מתקיים \(2\cdot1 \le 1+1\), כלומר \(2 \le 2\) – נכון. אבל הצעד האינדוקטיבי ידרוש:

מניחים \(2k \le k+1\) ומנסים להוכיח: \(2(k+1) \le (k+1)+1\), כלומר \(2k+2 \le k+2 \Rightarrow 2k \le k\).

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

הנחת האינדוקציה: נניח כי \(P(k)\) נכונה עבור מספר טבעי מסוים \(k\).
המטרה: להוכיח כי \(P(k+1)\) נכונה.

טיפ לתלמידים:

המשפט "נניח כי הטענה נכונה עבור \(n=k\)" אינו אומר שאנחנו יודעים שהיא נכונה. הוא אומר: "בואו נבדוק מה יקרה אם היא נכונה עבור \(k\), האם מכאן נובע שהיא נכונה עבור \(k+1\)".

פעילות חקר מומלצת:

לתת לתלמידים הוכחות מסוג "אם \(A\) אז \(B\)" שבהן לא ברור אם \(A\) נכון, ולהראות שניתן להוכיח קשר לוגי בין \(A\) ל-\(B\) גם בלי לדעת האם \(A\) מתקיימת בפועל. זה מחזק את ההבנה שה"הנחה" היא כלי לוגי, לא הצהרה על המציאות.

1. ניסוח הטענה: "נוכיח באינדוקציה על \(n\) כי: \(P(n):\) (כאן כותבים במפורש את הטענה עבור \(n\))."

2. שלב הבסיס: "נבדוק את הטענה עבור \(n=n_0\):" (מציבים ומראים במפורש שהשוויון/אי-שוויון נכון).

3. הנחת האינדוקציה: "נניח כי הטענה נכונה עבור \(n=k\), כלומר: \(P(k): \dots\)"

4. צעד האינדוקציה: "נוכיח שהטענה נכונה עבור \(n=k+1\):" (כותבים \(P(k+1)\), משתמשים בהנחת האינדוקציה בדרך מסודרת, מצמצמים, מסדרים ומגיעים לאמת מתמטית).

5. סיכום: "מכיוון שהטענה נכונה עבור \(n=n_0\) (שלב הבסיס), וכן לכל \(k \ge n_0\) מתקיים: אם \(P(k)\) נכונה אז \(P(k+1)\) נכונה (צעד האינדוקציה), נקבל כי הטענה נכונה לכל \(n \ge n_0\)."