שיעור תאוריה
אינדוקציה מתמטית
איך מזהים שהנושא מתאים
- הטענה צריכה להתקיים לכל מספר טבעי החל מערך התחלתי מסוים.
- מופיע ביטוי שתלוי ב-n, ומבקשים להוכיח חלוקה, שוויון או אי-שוויון.
- אפשר לקשור את הביטוי עבור n+1 לביטוי שכבר ידוע עבור n.
אינטואיציה
אינדוקציה מתאימה לטענה שמסודרת בשלבים. קודם מוודאים שהשלב הראשון עומד, ואז מוכיחים שמכל שלב שעומד אפשר לעבור לשלב הבא. שני החלקים יחד מכסים את כל השרשרת.
הנחת האינדוקציה אינה אומרת שהטענה כבר הוכחה לכל המספרים. היא מאפשרת לבחור שלב שרירותי, להניח שהטענה נכונה בו, ולבדוק אם המידע הזה מספיק כדי לבנות את השלב הבא.
בשאלת התחלקות מחפשים בתוך הביטוי הבא עותק של הביטוי מהנחת האינדוקציה. את השארית צריך לכתוב גם היא ככפולה של המחלק. כך מתקבל עד מפורש לכך שהביטוי הבא מתחלק.
הגדרות פורמליות
| מושג | משמעות |
|---|---|
| טענת האינדוקציה | P(n) היא הטענה שאותה רוצים להוכיח עבור כל n בתחום. |
| בסיס האינדוקציה | הוכחת P(n₀) עבור הערך הראשון n₀. |
| הנחת האינדוקציה | בחירת k≥n₀ שרירותי והנחה ש-P(k) נכונה. |
| צעד האינדוקציה | הוכחת P(k+1) מתוך הנחת האינדוקציה. |
| התחלקות | d מחלק את a אם קיים t∈Z כך ש-a=dt. המספר t הוא עד להתחלקות. |
עקרון האינדוקציה:
P(n₀) ∧ ∀k≥n₀(P(k)→P(k+1)) ⟹ ∀n≥n₀ P(n)הבסיס מכניס את הערך הראשון לשרשרת. צעד האינדוקציה מעביר את נכונות הטענה מכל ערך לערך הבא, ולכן אפשר לחזור על המעבר עבור כל ערך גדול יותר.
בהוכחת התחלקות, הנחת האינדוקציה צריכה להיפתח לעד:
d | E(k) ⇔ ∃t∈Z: E(k)=dtבצעד הבא מחפשים כתיבה של E(k+1) באמצעות E(k) וכפולות נוספות של d. לאחר הצבת E(k)=dt, אוספים את הגורם d ומוודאים שהעד החדש שלם.
שיטת פתרון
- מגדירים במפורש את P(n) ואת הערך הראשון בתחום.
- מוכיחים את בסיס האינדוקציה בהצבה מלאה.
- בוחרים k שרירותי בתחום ומנסחים את הנחת האינדוקציה. בהתחלקות מציגים עד t∈Z.
- מתחילים מהביטוי של k+1, ולא מן התוצאה המבוקשת.
- מסדרים את הביטוי כך שיופיע בו הביטוי של k, ואז מציבים את הנחת האינדוקציה.
- מוציאים את המחלק כגורם משותף, מזהים את העד החדש ומוכיחים שהוא שייך ל-Z.
- מסיימים במשפט שמחבר את הבסיס ואת הצעד למסקנה עבור כל n בתחום.
הערות מוכנות למבחן
- הנחת האינדוקציה נכתבת עבור k שרירותי, לא עבור כמה ערכים שנבדקו.
- בצעד האינדוקציה מתחילים מהביטוי של k+1 ומראים כיצד הנחת האינדוקציה נכנסת אליו.
- בחלוקה, סיום בצורת d·u דורש לציין ש-u מספר שלם.