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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מתמטיקה תיכונית | אלגברה תיכונית | אינדוקציה מתמטית

תוכן עניינים

1 אינדוקציה של טענה כללית
- 1.1 מבנה ההוכחה באינדוקציה
- 1.2 אינדוקציה של טענה כללית
  - 1.2.1 דוגמא

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

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

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

טענה שניתן להוכיח באינדוקציה היא טענה שתלויה במספר טבעי כלשהו (סימון מקובל במקרה זה - $\;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$ טבעי כי הוא סכום של מספרים חיוביים.
מסקנה: קיבלנו סכום של שני ביטויים חיוביים, שהוא תמיד חיובי, ולכן על פי משפט ההוכחה באינדוקציה הטענה נכונה לכל מספר טבעי.

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

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

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

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

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

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

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

[עריכה] דוגמא

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא