מיריאינדוקציה מתמטית שורת דומינו שלא נגמרת
איך מוכיחים שטענה נכונה לכל מספר טבעי, בלי לבדוק אינסוף מקרים? מראים שהדומינו הראשון נופל, ושכל דומינו שנופל מפיל את הבא אחריו. זאת אינדוקציה מתמטית, לרמת 4 ו-5 יח״ל. במעבדה מזיזים מחוונים ורואים מה קורה, ובתרגול מקבלים רמזים במקום תשובות.
שלושה שלבים
1. בסיס
בודקים שהטענה נכונה עבור n = 1. הדומינו הראשון נופל.
2. הנחה
מניחים שהטענה נכונה עבור n כלשהו. הדומינו ה-n נפל.
3. צעד
מוכיחים, בעזרת ההנחה, שהיא נכונה גם עבור n + 1. כל דומינו מפיל את הבא.
מעבדה: מפילים דומינו
בחרו טענה והזיזו את n. הטבלה בודקת את שני האגפים לכל מספר עד n, והדומינו הצהוב הוא הבא בתור. לחצו על "בסיס", "הנחה" ו"צעד" כדי לראות את ההוכחה של הטענה.
נסו את אלה:
שלוש מלכודות
בדיקה של כמה מקרים זאת לא הוכחה
הביטוי n² − n + 41 נותן מספר ראשוני לכל n מ-1 עד 41.
אבל ב-n = 42 יוצא 1763 = 41 · 43. רק הצעד מבטיח שזה ממשיך לנצח.
שוכחים את הבסיס
"n = n + 1" עובר את הצעד: אם זה נכון, מוסיפים 1 לשני הצדדים ומקבלים את הטענה ל-n + 1.
אבל עבור n = 1 יוצא 1 = 2. בלי בסיס, אף דומינו לא נופל.
מציבים n + 1 רק בחלק מהמקומות
בטענה עבור n + 1 מחליפים כל n ב-(n + 1).
n(n + 1)/2 הופך ל-(n + 1)(n + 2)/2, ולא ל-(n + 1)(n + 1)/2.
דוגמה פתורה, צעד אחרי צעד
הוכיחו שלכל n טבעי:
תרגול: חלקי ההוכחה
כל פעם תקבלו טענה ושאלה על אחד השלבים של ההוכחה: איזה איבר מוסיפים בצעד, מה צריך לצאת בצעד, או בדיקה של מקרה אחד.
שאלות שכולם שואלים
מה זה אינדוקציה מתמטית?
שיטה להוכיח שטענה נכונה לכל מספר טבעי. בודקים את המקרה הראשון (בסיס), מניחים שהטענה נכונה עבור n (הנחה), ומוכיחים שהיא נכונה גם עבור n + 1 (צעד). כמו שורת דומינו: הראשון נופל, וכל אחד מפיל את הבא. ראו במעבדה.
מה ההבדל בין הנחת האינדוקציה לצעד האינדוקציה?
בהנחה לא מוכיחים כלום: רק כותבים את הטענה עבור n ומניחים שהיא נכונה. בצעד מוכיחים את הטענה עבור n + 1, ומשתמשים בהנחה באמצע הדרך. ראו בדוגמה הפתורה.
למה לא מספיק לבדוק הרבה מקרים?
כי טענה יכולה להיות נכונה במקרים הראשונים ולהישבר אחר כך. למשל n² − n + 41 ראשוני עד 41, אבל ב-42 יוצא 41 · 43. רק הצעד מבטיח שהטענה ממשיכה לכל n.