אינדוקציה מתמטית היא שיטה להוכיח שתכונה נכונה לכל המספרים הטבעיים. הרעיון הבסיסי פשוט: מראים שהמספר הראשון מקיים את התכונה (בסיס האינדוקציה), ואז מראים שאם מספר כללי n מקיים אותה, גם n+1 יקיים אותה (צעד האינדוקציה). אם שני השלבים נכונים, מתקבלת נכונות לכל n.
הרעיון הופיע כבר במקורות ישנים (כמו עבודות מהמאה ה-16 וה-17), ובאופן מפורש אצל בלה פסקל ב-1654 בעת שהוכיח תכונות במשולש פסקל. את המונח "אינדוקציה מתמטית" הציע אוגוסטוס דה-מורגן במאמר משנת 1838. במאה ה-19 שימשו ג'ורג' בול, דה-מורגן, צ'ארלס פירס, ג'וזפה פיאנו (פאנו) וריכרד דדקינד בפיתוח הצורה הפורמלית של השיטה.
שני חלקים עיקריים: בסיס וצעד. בניסוח מילולי: אם P(1) נכונה, ואם מכל n שבו P(n) נכונה נובע ש-P(n+1) נכונה, אז P(n) נכונה לכל n. מונח טכני: אקסיומת האינדוקציה היא האקסיומה שמבטיחה חלות השיטה במערכת פאנו.
מבנה טיפוסי: בודקים את המקרה n=1; מניחים את P(n) כהנחה; מוכיחים ש-P(n+1) נובעת ממנה. שגיאות נפוצות: השמטת בסיס האינדוקציה, או ביצוע צעד האינדוקציה רק ל-n>2 (כפי שמדגים פרדוקס הסוסים).
- אינדוקציה שלמה (אינדוקציה חזקה): צעד האינדוקציה משתמש בנכונות הטענה לכל הערכים הקטנים מ-n, לא רק ב-n בלבד. שימושי לדוגמאות כמו פירוק לגורמים.
- אינדוקציה כפולה/מרובת פרמטרים: מבצעים אינדוקציה על שני פרמטרים בו-זמנית.
- אינדוקציה על קבוצות סדורות היטב (אינדוקציה טרנספיניטית): מחליפים את המספרים הטבעיים בקבוצות מסודרות אחרות.
- נסיגה אינסופית והפוכה: שיטות שמשתמשות בכיוון יורד או בהפעלה חוזרת אחורה של הטיעון.
- דוגמה קלאסית: הוכחה באינדוקציה שסכום המספרים 1+2+...+n שווה ל-n(n+1)/2. ביסוס: נכונה עבור n=1; צעד האינדוקציה מראה שאם זה נכון עבור n אז גם עבור n+1.
- מגדלי האנוי: בעזרת אינדוקציה מראים שאפשר להעביר כל מגדל של דיסקיות לפי החוקים.
- מספרי רמזי (בעיית רמזי): באמצעות אינדוקציה מראים שקיימים מספרים שמחייבים קבוצות של מכרים או זרים, ומקבלים גבול עליהם.
- עץ בינארי: בעזרת אינדוקציה מראים שמספר העלים גדול במספר אחד ממספר הקודקודים המלאים.
- פרדוקס הסוסים מצביע על זהירות: טעויות קטנות בבסיס או בצעד יכולות להפוך הוכחה לא תקפה.
באקסיומות פאנו עקרון האינדוקציה הוא חלק מהאקסיומות. במסגרת תורת הקבוצות, ניתן לגזור את עקרון האינדוקציה מעקרון הסדר הטוב (כל קבוצה לא־ריקה בקבוצה מסודרת היטב מכילה איבר מינימלי). בטיעונים פורמליים מזכירים שגם אקסיומת האינסוף ואקסיומת היסוד משחקות תפקיד בבניין המספרים הטבעיים.
אינדוקציה מתמטית היא דרך להוכיח שמשהו נכון עבור כל המספרים הטבעיים. ההוכחה עובדת בשני שלבים פשוטים:
1) בוחנים את המספר הראשון. זה נקרא בסיס האינדוקציה.
2) מראים שאם זה נכון עבור n, אז גם עבור n+1. זה נקרא צעד האינדוקציה.
אם שני השלבים נכונים, אז זה נכון לכל המספרים.
הרעיון היה בשימוש כבר במאות קודמות. בלה פסקל השתמש בו ב-1654. במאה ה-19 המתמטיקאים סידרו והגו אותו בצורה רשמית.
- סכום המספרים: בעזרת אינדוקציה מראים ש-1+2+...+n = n(n+1)/2.
- מגדלי האנוי: אפשר להראות באינדוקציה שאפשר להעביר כל מגדל לפי הכללים.
חשוב לבדוק את בסיס האינדוקציה. אם שוכחים אותו, ההוכחה עלולה להיות שגויה, כמו בפרדוקס הסוסים.
תגובות גולשים