שימוש קלוקל באינדוקציה – דוגמאות

( 1 ) בדוגמה ( 5 ) בעמוד 135 הוכחנו , שלכל n < 5 מתקיים : . 2 > n 2 אם תחזרו להוכחת צעד האינדוקציה שם , תיווכחו שהיא נסמכה על העובדה שלכל k < 5 מתקיים : . k ( -k 2 >) 1 בפועל , האי-שוויון k ( k - 2 ) > 1 מתקיים לא רק לכל , k < 5 אלא לכל . k < 3 האם אפשר להסיק מכך שהטענה הכללית 2 > n 2 נכונה לכל ? n < 3 התשובה היא לא , והסיבה היא שכאשר שרשרת הטענות מתחילה ב- , n = 3 הטענה הראשונה – בסיס האינדוקציה – היא הטענה : . 2 > 3 2 הטענה הזאת אינה נכונה ( . ( 8 / > 9 מאחר שהוכחת צעד האינדוקציה תקפה לכל , k < 3 הטענה הכללית תהיה נכונה לכל , n < 3 החל בראשון שעבורו . 2 > n כפי שראינו , עבור ; 2 / > n 2 n = 3 גם עבור . ( 16 / > 16 ) 2 / > n 2 n = 4 אם-כן , המספר הטבעי הראשון הגדול מ- 3 שעבורו 2 > n 2 הוא . n = 5 האי-שוויון הנידון נכון אפוא לכל n מ- 5 ואילך . ( 2 ) תהי ( T ( n הטענה , n + 1 = n ונניח שלאיזשהו מספר שלם T ( k ) , k היא אמת , כלומר שלאיזשהו . k + 1 = k , k מתוך הנחה זו קל להוכיח שגם ( , T ( k + 1 האומרת : k + 2 = k + 1 היא אמת : אכן : = k + 2 = ( k + 1 ) + 1 לפי הנחת האינדוקציה = k + 1 ה...  To the book