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

( 1 ) נוכיח באינדוקציה שלכל n טבעי , המספר n - n מתחלק ב- 6 ללא שארית . צעד ההתחלה : בסיס האינדוקציה ( כלומר הטענה הראשונה בשרשרת ) הוא הטענה ש- 0 - 0 מתחלק ב- , 6 וזה נכון ( . ( 0 =  60 צעד האינדוקציה : הנחת האינדוקציה תהיה ( , T ( k האומרת : k - k מתחלק ב- . 6 בהנחה זו נוכיח את ( , T ( k + 1 האומרת : ( k + 1 ) - ( k + 1 ) מתחלק ב- . 6 הנה : = ( k + 1 ) - ( k + 1 ) = ( + 3 + kkk + 31 ) - ( k + 1 ) ( = ( k - k ) + k + 33 = ( kk - k ) + 3 ( kk + 1 המחובר הראשון בסכום שמימין מתחלק ב- 6 לפי הנחת האינדוקציה . המחובר השני מתחלק ב- , 3 משום שהוא כפולה של , 3 והוא מתחלק גם ב- , 2 כי אחד מבין המספרים העוקבים k + 1 ) , k ) הוא זוגי . לכן גם המחובר השני מתחלק ב- . 6 לפיכך הסכום מתחלק ב- . 6 מאחר שאימתנו את בסיס האינדוקציה והצלחנו גם בצעד האינדוקציה , הרי שהטענה הכללית הוכחה כנדרש . ( 2 ) נוכיח באינדוקציה את הטענה : לכל 1 +  + n n ( n 2 + 1 ) n < 1 צעד ההתחלה : בסיס האינדוקציה הוא הטענה ( . 1 = 1 ( 1 2 + 1 הטענה הזאת נכונה ( . ( 1 = 2 הנחת האינדוקציה , ( , T ( k היא : ( 1 + 2 +  + k = k ( k 2 ...  To the book