דלג לתוכן

עקרון האינדוקציה

סדרות ואינדוקציה, כיתה י"א (5 יח"ל) שיעור 17 מתוך 23לימוד

עקרון האינדוקציה

דוגמאות אינן הוכחה

נבדוק את הביטוי n2+n+41\displaystyle n^2+n+41 עבור n=1,2,3,…\displaystyle {n}={1, 2, 3, \ldots}: מתקבלים 43,47,53,61,71,…\displaystyle 43, 47, 53, 61, 71, \ldots – כולם מספרים ראשוניים. כך עד n=39\displaystyle {n}={39}.

  • האם n2+n+41\displaystyle n^2+n+41 ראשוני לכל n\displaystyle n טבעי? לא: עבור n=40\displaystyle {n}={40} מתקבל 1600+40+41=1681=412\displaystyle {1600+40+41}={1681}={41^2}.
  • 39 דוגמאות תמכו בהשערה, ובכל זאת היא אינה נכונה.
  • טענה על כל המספרים הטבעיים – אינסוף מקרים – אי אפשר להוכיח בבדיקה של מקרים. צריך שיטה אחרת.
שורה של אבני דומינו

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

  • האבן הראשונה נופלת;
  • כל אבן שנופלת מפילה את האבן שאחריה.

אז הראשונה מפילה את השנייה, השנייה את השלישית, וכך כל אבן נופלת בסופו של דבר. אם חסר אחד מהשניים – אין ודאות: אולי אף אחת לא נופלת, ואולי יש רווח באמצע השורה.

שלושת שלבי ההוכחה

הוכחה באינדוקציה מתמטית של טענה לכל n\displaystyle n טבעי:

  • שלב הבסיס – מוכיחים שהטענה נכונה עבור n=1\displaystyle {n}={1}.
  • שלב הצעד – מניחים שהטענה נכונה עבור מספר טבעי כלשהו k\displaystyle k (הנחת האינדוקציה), ומוכיחים שהיא נכונה גם עבור k+1\displaystyle k+1.
  • שלב ההסקה – לפי עקרון האינדוקציה, הטענה נכונה לכל n\displaystyle n טבעי.

כל הוכחה כותבים בשלושת השלבים האלה, וכל שלב בשמו.

הוכחה: סכום המספרים האי־זוגיים

13579

הציור מראה ש-1+3+5+7+9=52\displaystyle {1+3+5+7+9}={5^2}: כל שכבה בצורת L מגדילה ריבוע של k\displaystyle k על k\displaystyle k לריבוע של k+1\displaystyle k+1 על k+1\displaystyle k+1, ויש בה 2k+1\displaystyle 2k+1 משבצות. זה בדיוק שלב הצעד של ההוכחה שלפניכם, שבה נוכיח באינדוקציה ש-

1+3+5+…+(2n−1)=n21+3+5+\ldots+(2n-1)=n^2

לכל n\displaystyle n טבעי. לחצו על “הצג את ההוכחה”, והתקדמו שלב אחר שלב:

טענהנימוק
1עבור n=1\displaystyle {n}={1}: 1=12\displaystyle {1}={1^2}שלב הבסיס
21+3+…+(2k−1)=k2\displaystyle {1+3+\ldots+(2k-1)}={k^2}הנחת האינדוקציה, עבור k\displaystyle k טבעי כלשהו
3צריך להוכיח: 1+3+…+(2k−1)+(2k+1)=(k+1)2\displaystyle {1+3+\ldots+(2k-1)+(2k+1)}={(k+1)^2}הטענה עבור k+1\displaystyle k+1; האיבר ה-(k+1)\displaystyle (k+1) הוא 2(k+1)−1=2k+1\displaystyle {2(k+1)-1}={2k+1}
41+3+…+(2k−1)+(2k+1)=k2+(2k+1)\displaystyle {1+3+\ldots+(2k-1)+(2k+1)}={k^2+(2k+1)}לפי הנחת האינדוקציה (2)
5k2+2k+1=(k+1)2\displaystyle {k^2+2k+1}={(k+1)^2}נוסחת הכפל המקוצר; הוכחנו את (3)
61+3+…+(2n−1)=n2\displaystyle {1+3+\ldots+(2n-1)}={n^2} לכל n\displaystyle n טבעישלב ההסקה: (1), (2)–(5) ועקרון האינדוקציה
הנחה לעומת טענה

הנחת האינדוקציה דומה לטענה, אבל היא טענה אחרת:

  • הטענה: “לכל n\displaystyle n טבעי, 1+3+…+(2n−1)=n2\displaystyle {1+3+\ldots+(2n-1)}={n^2}” – זה מה שמוכיחים.
  • ההנחה: “עבור k\displaystyle k מסוים, 1+3+…+(2k−1)=k2\displaystyle {1+3+\ldots+(2k-1)}={k^2}” – היא רק חלק משלב הצעד, ובו מוכיחים טענה מהצורה “אם הטענה נכונה עבור k\displaystyle k, אז היא נכונה עבור k+1\displaystyle k+1”.
  • כדי להוכיח “אם… אז…” לא צריך לדעת אם ההנחה נכונה: מניחים אותה ככלי עבודה, לא כעובדה.
  • שני השלבים נחוצים, ואף אחד מהם לא נובע מהשני: הבסיס בלי הצעד הוא דוגמה אחת, והצעד בלי הבסיס הוא שרשרת שאין לה התחלה.
ריצוף לוחות

n = 1n = 2n = 3

לוח n\displaystyle n הוא ריבוע של 2n\displaystyle 2^n על 2n\displaystyle 2^n משבצות, שהמשבצת השמאלית התחתונה שלו חסרה. נוכיח באינדוקציה שאפשר לרצף כל לוח כזה בצורות L של שלוש משבצות (לוח 1).

  • שלב הבסיס: לוח 1 הוא בעצמו צורת L.
  • שלב הצעד: נניח שאפשר לרצף את לוח k\displaystyle k. נחלק את לוח k+1\displaystyle k+1 לארבעה ריבועים של 2k\displaystyle 2^k על 2k\displaystyle 2^k. לריבוע השמאלי התחתון חסרה פינה – הוא לוח k\displaystyle k. בשלושת האחרים נניח צורת L אחת במרכז הלוח, כך שתכסה בכל אחד מהם את הפינה שפונה למרכז. עכשיו כל אחד מהם הוא לוח k\displaystyle k (מסובב), ולפי ההנחה אפשר לרצף אותו.
  • שלב ההסקה: לפי עקרון האינדוקציה, אפשר לרצף את לוח n\displaystyle n לכל n\displaystyle n טבעי.
תרגיל 1

2+4+6+…+2n=n(n+1)\displaystyle {2+4+6+\ldots+2n}={n(n+1)}
הוכיחו באינדוקציה שהטענה נכונה לכל n\displaystyle n טבעי.

שלב הבסיס

בדקו את הטענה עבור n=1\displaystyle {n}={1}.

שלב הצעד

כתבו את הנחת האינדוקציה – הטענה עבור k\displaystyle k טבעי כלשהו – ואת מה שצריך להוכיח עבור k+1\displaystyle k+1.

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

    / – קו שבר · Tab או החצים – בין המונה למכנה, ואחר כך פתק מעל או מתחת · Enter – בדיקה ושורה חדשה · * – כפל · ^ – חזקה, ↓ – סוף החזקה

    / – קו שבר · Tab או החצים – בין המונה למכנה, ואחר כך פתק מעל או מתחת · Enter – שורה חדשה · * – כפל · ^ – חזקה, ↓ – סוף החזקה

    שלב ההסקה
    תרגיל 2

    כמה צורות L יש בריצוף של לוח 3 (8 על 8 משבצות, אחת חסרה)? ובלוח n\displaystyle n? כתבו את החישוב ללוח 3.

      / – קו שבר · Tab או החצים – בין המונה למכנה, ואחר כך פתק מעל או מתחת · Enter – בדיקה ושורה חדשה · * – כפל · ^ – חזקה, ↓ – סוף החזקה

      / – קו שבר · Tab או החצים – בין המונה למכנה, ואחר כך פתק מעל או מתחת · Enter – שורה חדשה · * – כפל · ^ – חזקה, ↓ – סוף החזקה

      תרגיל 3

      נועה בדקה את n2−n+11\displaystyle n^2-n+11 עבור n=1,2,…,10\displaystyle {n}={1, 2, \ldots, 10}, וקיבלה רק מספרים ראשוניים.
      היא טוענת שהביטוי ראשוני לכל n\displaystyle n טבעי. האם היא צודקת? נמקו.