הוכחה באמצעות אינדוקציה
הוצג| English | משמעות |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | מספר טבעי חיובי |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | אינדוקציה מתמטית |
| base case/beɪs keɪs/ | מקרה בסיסי |
| inductive step/ɪnˈdʌktɪv step/ | שלב אינדוקטיבי |
| conjecture/kənˈdʒektʃə/ | ניחוש |
| divisible/dɪˈvɪzɪbl/ | מתחלק |
ההוכחה על ידי דומינו
- איך מוכיחים שמשהו נכון לכל מספר טבעי חיובי — מספר אינסופי של מקרים?
- אינדוקציה מתמטית פועלת כמו דומינו: להפיל את הראשונה (מק בסיס), ולהראות שכל דומינו מפילה את הבאה אחריה (שלב האינדוקציה). אם שניהם עובדים, כולם ייפלו.
מסלול ההוכחה באמצעות אינדוקציה
תחשבו על אינדוקציה כעל המדומה הראשונה בתור, שאליו מצטרפת כלל הדוחף את כל המקרה הבא.
שני שלבי האינדוקציה
- אינדוקציה מתמטית מוכיחה תוצאה לכל מספר טבעי חיובי $n$ בשני שלבים:
- מקרה בסיס: הוכיחו שהוא נכון עבור $n = 1$.
- שלב אינדוקציה: נניח שהטענה נכונה עבור $n = k$, ואז נוכיח אותה עבור $n = k + 1$.
דוגמה מפורטת. הוכח $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. מקרה בסיס ($n=1$): אג"פ $= 1$, אג"ר $= \dfrac{1(2)}{2} = 1$. ✓ שלב אינדוקטיבי: נניח נכון עבור $n = k$. עבור $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
הוכחה באינדוקציה עובדת כמו שרשרת של דומינו נופלים
שני השלבים בהוכחה באמצעות אינדוקציה הם המקרה הבסיסי וה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אינדוקציה דורשת מקרה בסיסי וכן שלב אינדוקטיבי מ-k ל-k+1.
המקרה הבסיסי מראה בדרך כלל שהתוצאה נכונה עבור:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
המקרה הבסיסי בודק את הערך הקטן ביותר, בדרך כלל n = 1.
אם גם המקרה הבסיסי וגם השלב האינדוקטיבי מתקיימים, התוצאה נכונה לכל המספרים הטבעיים החיוביים n.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
זה בדיוק מה שהעקרון האינדוקטיבי מבטיח.
מדוע שני השלבים חיוניים
- המקרה הבסיס מתחיל את השרשרת. ללאו, ניתן "להוכיח" טענות שגויות.
- שלב האינדוקציה ממשיך אותו. ללאו, הוכחת רק מקרה אחד.
שני השלבים חיוניים. הוכחה עם שלב אינדוקציה בלבד היא כמו שורה של דומינו שאף אחד לא דוחף — הם לעולם לא מתחילים ליפול. הוכחה עם מקרה בסיס בלבד היא כמו הדחיפה של דומינו אחד — רק אחד נופל.
ניתן להוכיח תוצאה באמצעות אינדוקציה רק באמצעות השלב האינדוקטיבי, ללא מקרה בסיסי.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
שני השלבים חיוניים. ללא המקרה הבסיסי, השרשרת לעולם לא מתחילה.
ניחוש ולאחר מכן הוכחה
- לעיתים קרובות מבצעים ניחוש (מישור הגיוני) מספר מקרים, ואז מאמתים אותו באמצעות הוכחה באינדוקציה.
- דוגמה: $1 + 3 + 5 + 7 = 16 = 4^2$. השערה: סכום ה$n$ מספרים אי-זוגיים הראשונים הוא $n^2$.
באמצעות אינדוקציה, הסכום 1 + 2 + ... + n = n(n+1)/2. עבור n = 10, מצאו את הסכום.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
10(11)/2 = 55.
אינדוקציה לחילוק
- הוכח כי $3^n - 1$ מתחלק ב-$2$ לכל המספרים הטבעיים $n$.
- מקרה בסיס ($n=1$): $3^1 - 1 = 2$, מתחלק ב-$2$. ✓
- שלב אינדוקציה: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. מכיוון ש-$3^k - 1$ מתחלק ב-$2$ (על פי הנחה), גם הביטוי כולו מתחלק. ✓
במתמטיקה, ניחוש הוא:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הנחה היא טענה שאינה מוכחת, המבוססת על עובדות — ולאחר מכן מנסים להוכיח אותה (לרוב באמצעות אינדוקציה).
הבנתך מושלמת
- אינדוקציה = מקרה בסיס ($n=1$) + שלב אינדוקציה ($n=k \Rightarrow n=k+1$)
- שני השלבים יחד מוכיחים זאת עבור כל המספרים הטבעיים
- לעיתים קרובות מוניחים מהמקרים, ואז מוכיחים באינדוקציה