נדב כץלמידה ברמה אחרת
מתמטיקה · יא׳ · 5 יח״ל 5 יחידות
הוכחה לכל n טבעי

אינדוקציה מתמטית - הוכחה בשני שלבים

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

מעבדת האינדוקציה הזיזו את n וראו את שרשרת הדומינו נופלת ואת נוסחת הסכום נבדקת
1 + 2 + … + n = n(n+1)/2
סכום ישיר - נוסחה - בדיקה -
עד n4

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

מבט מקרוב

האנטומיה של הוכחה באינדוקציה

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

שני שלבי האינדוקציה - על 1 + 2 + … + n = n(n+1)/2
P(n): 1 + 2 + … + n = n(n+1)/2 שלב 1 - בסיס (n = 1) אגף שמאל = 1 אגף ימין = 1·2/2 = 1 שווים ✓ - האבן הראשונה נופלת שלב 2 - צעד (n → n+1) מניחים: 1+…+n = n(n+1)/2 מוסיפים (n+1) לשני האגפים כל אבן מפילה את הבאה הפישוט האלגברי n(n+1)/2 + (n+1) = (n+1)(n+2)/2 בסיס + צעד ← הטענה נכונה לכל n טבעי כל אבני הדומינו נופלות
נכיר צעד אחר צעד

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

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

1

הטענה P(n)

מנסחים במדויק את מה שרוצים להוכיח לכל n טבעי. למשל P(n): 1 + 2 + … + n = n(n+1)/2. שימו לב - זו טענה אחת עם משתנה n, ולא אינסוף טענות נפרדות.

2

שלב הבסיס

בודקים שהטענה נכונה עבור n = 1. מציבים ומשווים בין האגפים: אגף שמאל = 1, אגף ימין = 1·22 = 1. שווים - הבסיס מתקיים. זו האבן הראשונה שנופלת.

3

הנחת האינדוקציה

מניחים שהטענה נכונה עבור n מסוים: 1 + 2 + … + n = n(n+1)/2. זו ההנחה שממנה נצא - האבן ה-n שכבר נפלה. איננו מוכיחים אותה, אלא משתמשים בה.

4

שלב הצעד

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

5

הפישוט האלגברי

לב הצעד. מ-n(n+1)/2 + (n+1) מוציאים גורם משותף (n+1): (n+1)(n/2 + 1) = (n+1)(n+2)/2 - בדיוק הנוסחה עבור n + 1, כנדרש.

6

המסקנה

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

n = 1
בסיס : n = 1
בסיס: מציבים n = 1 ובודקים ששני האגפים שווים ← האבן הראשונה נופלת
n+1
צעד : n → n+1
צעד: מניחים ל-n ומוכיחים ל-n+1 ← כל אבן מפילה את הבאה
נפתור יחד

דוגמאות פתורות

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

דוגמה 11 + 2 + … + n = n(n+1)/2
  1. בסיס (n = 1): אגף שמאל = 1; אגף ימין = 1·22 = 1. שווים ✓
  2. הנחה: נניח שעבור n מתקיים 1 + 2 + … + n = n(n+1)/2.
  3. צעד: מוסיפים (n + 1) לשני האגפים: 1 + … + n + (n+1) = n(n+1)/2 + (n+1).
  4. פישוט: מוציאים (n+1) משותף: (n+1)(n/2 + 1) = (n+1)(n+2)/2 - בדיוק הנוסחה עבור n + 1.
  5. הבסיס והצעד מתקיימים, ולכן לפי עקרון האינדוקציה 1 + 2 + … + n = n(n+1)/2 לכל n טבעי.
דוגמה 21 + 3 + 5 + … + (2n − 1) = n²
  1. בסיס (n = 1): אגף שמאל = 1; אגף ימין = 1² = 1. שווים ✓
  2. הנחה: נניח שעבור n מתקיים 1 + 3 + … + (2n − 1) = n².
  3. צעד: האיבר הבא הוא 2(n+1) − 1 = 2n + 1. מוסיפים אותו: n² + (2n + 1).
  4. פישוט: n² + 2n + 1 = (n + 1)² - בדיוק הנוסחה עבור n + 1.
  5. הבסיס והצעד מתקיימים, ולכן 1 + 3 + … + (2n − 1) = n² לכל n טבעי.
דוגמה 31² + 2² + … + n² = n(n+1)(2n+1)/6
  1. בסיס (n = 1): אגף שמאל = 1; אגף ימין = 1·2·36 = 1. שווים ✓
  2. הנחה: נניח שעבור n מתקיים 1² + … + n² = n(n+1)(2n+1)/6.
  3. צעד: מוסיפים (n + 1)²: n(n+1)(2n+1)/6 + (n+1)². מוציאים (n+1)/6 משותף: (n+1)[n(2n+1) + 6(n+1)]/6.
  4. פישוט: n(2n+1) + 6(n+1) = 2n² + 7n + 6 = (n+2)(2n+3), אז מקבלים (n+1)(n+2)(2n+3)/6 - בדיוק הנוסחה עבור n + 1.
  5. הבסיס והצעד מתקיימים, ולכן 1² + … + n² = n(n+1)(2n+1)/6 לכל n טבעי.
תרגלו ובדקו את עצמכם

תרגול אינטראקטיבי

ניקוד: 0 / 0

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

לוח המשחק

דרכים לתרגל את הדף הזה

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

0%
שליטה
0חדש
0בלימוד
0בחזרה
0שולט

הנקודות שכדאי לזכור

  • 1שני שלבים: בסיס (n=1) ו-צעד (מ-n ל-n+1) - יחד מוכיחים לכל n טבעי.
  • 2בסיס: מציבים n = 1 ומראים ששני האגפים שווים.
  • 3הנחה: מניחים שהטענה נכונה עבור n - ולא מוכיחים אותה.
  • 4צעד: מוסיפים את האיבר הבא לשני האגפים ומפשטים עד לצורה עם n + 1.
  • 5דומינו: אבן ראשונה נופלת + כל אבן מפילה את הבאה ← כולן נופלות.
מפתח פתרונות (תרגול)

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

    תצוגת דף עבודה כל השאלות פתוחות, בלי מענה אינטראקטיבי