עקרון האינדוקציה

שיטת ההוכחה באינדוקציה מתמטית , שתוצג ותודגם בסעיף זה , היא אחת משיטות ההוכחה הנוחות והנפוצות לטענות מסוג מסוים . הטענות שלהוכחתן השיטה עשויה להתאים , הן טענות המתייחסות לכל מספר טבעי , n או באופן כללי יותר , לכל מספר שלם , n החל מאיזשהו מספר ראשון נתון , m כגון הטענה : לכל מספר טבעי , n ≥ 1 סכום המספרים הטבעיים מ- 1 עד n הוא ) n ) n 2 + 1 אינדוקציה מתמטית אינה מתאימה בהוכחת טענות כגון : סכום הזוויות בכל משולש הוא  . 180 סימן ההיכר של משפט הראוי להיחשב כמועמד להוכחה באינדוקציה הוא , שאת הנטען בו אפשר לתאר כשרשרת של טענות , שבה יש טענה ראשונה , טענה שנייה , טענה שלישית וכך הלאה . דוגמאות ( 1 ) תהי T הטענה : לכל n ≥ 1 טבעי , סכום המספרים הטבעיים מ- 1 עד n הוא ) n ) n 2 + 1 הטענה T היא , למעשה , שרשרת אינסופית של טענות נפרדות , אחת לכל מספר שלם חיובי . n נסמן ב- ( T ( 1 את מה ש- T אומרת ביחס ל- , n = 1 שהוא : ( 1  ( 1 + 1 סכום המספרים הטבעיים מ-1 עד 1 הוא , 2 כלומר היא אומרת . 1 = 1 זה נכון . ( T ( 2 אומרת : ( 1 + 2 = 2 ( 2 2 + 1 כלומר : . 1 + 2 = 3 גם זה נכון . ( T ( 100 אומרת : 1 + 2 ...  To the book