אינדוקציה שלמה

יש טענות שרשרת , שלהוכחתן נוח להשתמש באינדוקציה שלמה – גרסה חלופית לשיטת ההוכחה באינדוקציה שבה נעזרנו עד כה . כמו ההוכחות בשיטת האינדוקציה המקורית , גם הוכחות באינדוקציה שלמה כוללות צעד התחלה וצעד אינדוקציה . צעד ההתחלה של הוכחה באינדוקציה שלמה זהה לצעד ההתחלה בגרסה המקורית : מאמתים על ידי בדיקה ישירה את בסיס האינדוקציה , כלומר את הראשונה בשרשרת הטענות שמהם מורכבת הטענה הכללית . צעד האינדוקציה של הוכחה באינדוקציה שלמה : מראים שכל טענה בשרשרת נובעת מכלל הטענות הקודמות לה . כאשר הטענה הראשונה היא ( , T ( m צעד האינדוקציה כרוך בהוכחת הטענה שעבור T ( m ) , T ( m + 1 ) ,  , T ( 1-k ) T ( k ) , k > m לפי הגרסה הזאת , הנחת האינדוקציה היא שכל הטענות בשרשרת , הקודמות ל- ( , T ( k הן נכונות , ומתוכן מוכיחים את ( T ( k עצמה . הצלחה בשני הצעדים – צעד ההתחלה וצעד האינדוקציה , מהווה הוכחה לטענה הכללית . למרות שבגרסה הזאת הנחת האינדוקציה חזקה יותר , המסקנה שהטענה הכללית נכונה עדיין מוצדקת . כדי להשתכנע , חשבו על אבני הדומינו שבעזרתן הצדקנו את הגרסה הקודמת . אם האבן הראשונה מפילה את השניה , השתיים ה...  To the book