מתמטיקה תיכונית/אלגברה תיכונית/אינדוקציה מתמטית/אינדוקציה של טענה כללית

אינדוקציה של טענה כללית

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

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

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

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

טענה שניתן להוכיח באינדוקציה היא טענה שתלויה במספר טבעי כלשהו (סימון מקובל במקרה זה - $n$). לגבי הטענה עלינו להוכיח שהיא מתקיימת לכל מספר טבעי בכלל ולצורך זה יש לבצע את שלושת שלבי ההוכחה באינדוקציה:

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

לאחר ביצוע כל שלושת השלבים, יש להוסיף את המסקנה ש"על סמך משפט ההוכחה באינדוקציה הטענה נכונה לכל מספר טבעי". ניתן לסיים אותה בכל דרך שתרצו (כמו מ.ש.ל או מש"ל, Q.E.D, שרטוט ריבוע קטן וכדומה, אלה דרכים מוסכמות לומר שביצוע ההוכחה הסתיים).

אינדוקציה של טענה כללית

דוגמא

הוכיחו שהביטוי $2n^{2}+3n-4$ חיובי לכל $n$ טבעי.

הוכחה:

• שלב א': בסיס האינדוקציה: בדיקה עבור $n=1$ (אם בתרגיל עלינו להוכיח שהטענה מתקיימת החל ממספר מסוים $p$ , מתחילים את הבדיקה עבור $n=p$). מציבים במקום $n$ בטענה את המספר עבורו בודקים, ולאחר ההצבה מקבלים: $2n^{2}+3n-4=2\cdot 1^{2}+3\cdot 1-4=2+3-4=1$ שהוא מספר חיובי. כלומר, הטענה נכונה עבור המקרה הפרטי של $n=1$ .
• שלב ב': הנחת האינדוקציה: אנו מניחים שעבור $n=k$ , הביטוי $2k^{2}+3k-4$ חיובי. על מה מתבססת ההנחה שלנו? - על השלב הקודם, בו הראינו שהטענה נכונה עבור $n$ מסוים.
• שלב ג: צעד האינדוקציה: עלינו להוכיח, שעבור $n=k+1$ מתקיים:

$2(k+1)^{2}+3(k+1)-4>0$

נפתח סוגריים, נפשט את הביטוי ונקבל:

$2(k^{2}+2k+1)+3(k+1)-4=2k^{2}+4k+2+3k+3-4=2k^{2}+7k+1$

כלומר, מספיק להוכיח שהביטוי $2k^{2}+7k+1$ חיובי לכל $k$ טבעי. על-מנת להוכיח זאת ניעזר בהנחת האינדוקציה (במקרים אחרים היא הדרך היחידה לפתרון), ונפרק את הביטוי $2k^{2}+7k+1$ , כך שנקבל את הנחת האינדוקציה ועוד אבר (או אברים). ואז, כל שיוותר לנו הוא להוכיח עבור האברים הנוספים. נקבל:

$2k^{2}+7k+1=2k^{2}+3k+4k-4+5=2k^{2}+3k-4+4k+5>0$

הביטוי $2k^{2}+3k-4$ על פי הנחת האינדוקציה הוא חיובי לכל $k$ טבעי. והביטוי $4k+5$ הוא חיובי לכל $k$ טבעי כי הוא סכום של מספרים חיוביים.

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

הפרק הקודם: סדרות

אינדוקציה של טענה כללית תרגילים

הפרק הבא: אינדוקציה על סכומים