אינדוקציה מתמטית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
גישת האינדוקציה המתמטית מומחשת לעתים באמצעות האפקט הסדרתי של אבני דומינו נופלות.
Nuvola apps edu mathematics blue-p.svg

בערך זה
נעשה שימוש
בסימנים מוסכמים
מתחום המתמטיקה.
להבהרת הסימנים
ראו סימון מתמטי.

אינדוקציה מתמטית היא שיטה לוגית המאפשרת להוכיח שתכונה מסוימת משותפת לכל המספרים הטבעיים. ההוכחה באינדוקציה מורכבת משתי טענות: ראשית, שהמספר 1 מקיים את התכונה, ושנית, שאם מספר טבעי n מקיים אותה, אז גם המספר n+1 מקיים אותה. גמישותה של שיטת האינדוקציה הפכה אותה לאחד מכלי ההוכחה החזקים ביותר בארגז הכלים של כל מתמטיקאי.

היסטוריה[עריכת קוד מקור | עריכה]

את המונח "אינדוקציה מתמטית" הציע הלוגיקן אוגוסטוס דה-מורגן, כשכתב את הערך "אינדוקציה (מתמטיקה)" בציקלופדיית פני ב-1838, ‏[1] אך השיטה עצמה הופיעה אצל מחברים רבים קודם לכן. בלז פסקל עסק במשולש פסקל, המוגדר במונחים קומבינטוריים, והוכיח תכונות יסוד שלו, כמו העובדה שכל מקדם שווה לסכום שני המקדמים שמעליו במשולש. אצל פסקל, ב-1654, הופיעה האינדוקציה לראשונה, באופן מפורש ובסגנון מודרני‏[2]. ההיסטוריון של המתמטיקה פלוריאן קג'ורי‏‏‏[1]מצא סימנים של הוכחות עם טיעון חוזר, המזכירות את שלבי האינדוקציה הראשונים (ראו להלן) כבר אצל Campanus‏ (1260) ואצל פרוקלוס (Proclus)‏ (410-485), אבל סיכם שהוכחות אלו "אינן אינדוקציה".

הדגמת הטענה "סכומם של n המספרים האי-זוגיים הראשונים הוא המספר הריבועי העומד במקום n".

גאורג קנטור, ב-1902, מייחס את שיטתו של פסקל למאורוליצוס (Maurolycus), שספרו "אריתמטיקה" פורסם ב-1575‏‏‏[3]. מאורוליצוס בנה בספר טבלאות של מספרים "מיוחדים", כגון זוגיים, אי-זוגיים, משולשיים וריבועיים, והבחין בתכונות שונות שלהן. לאחר שהוכיח את טענה XIII בספר, ש"כל ריבוע שמוסיפים לו את המספר האי-זוגי הבא שווה לריבוע הבא" (היינו, \ n^2+(2n+1)=(n+1)^2), הוא הוכיח את הטענה ה-XV, "סכומם של n המספרים האי-זוגיים הראשונים הוא המספר הריבועי העומד במקום n" (בלשון מודרנית, \ 1+3+\cdots+(2n-1)=n^2), כך: "המספר הריבועי הראשון, כשהוא נוסף למספר האי-זוגי הבא, נותן את הריבוע הבא (4); והמספר הריבועי השני, כשהוא נוסף למספר האי-זוגי הבא (5), נותן את הריבוע השלישי (9); וכך, המספר הריבועי השלישי, כשהוא נוסף למספר האי-זוגי הרביעי (7), נותן את המספר הריבועי הרביעי (16); וכך באופן עוקב עד אינסוף הטענה מוכחת באמצעות הפעלה חוזרת של טענה XIII".

הרב ד"ר נחום רבינוביץ'‏‏‏[4] טען שרבי לוי בן גרשום (הרלב"ג, 1288-1344) היה "הכותב הראשון שהשתמש באינדוקציה באופן שיטתי, ושהכיר בה כהליך מתמטי נפרד". לוי בן גרשום כתב כמה ספרי הערות על "יסודות" של אוקלידס; בספר "מעשה חושב" (1321) הוא באר את הספרים השביעי, השמיני והתשיעי של אוקלידס, והוכיח תוצאות קומבינטוריות משל עצמו. לשיטה של עלייה צעד אחר צעד ששימשה אותו בהוכחות הוא העניק את השם העברי "הדְרגה". רבינוביץ' הציע שהרלב"ג יכול היה לשאוב את רעיונותיו מפירושו של שבתאי בן אברהם דונולו (913-970) לספר יצירה, שמנה תמורות והסביר כיצד לחשב (רקורסיבית) את מספר התמורות של 3 עצמים מזה של 2 עצמים, של 4 מזה של 3, של 5 מזה של 4, וכן הלאה, עד לתמורות של 7 עצמים (אותן הוא מנה אחת לאחת).

עיקרי הטיעון[עריכת קוד מקור | עריכה]

כאמור לעיל, להוכחה באינדוקציה שני חלקים. ראשית, מראים שהמספר 1 מקיים את התכונה המבוקשת (זהו בסיס האינדוקציה), ושנית, שאם המספר n מקיים אותה, אז גם המספר n+1 מקיים אותה (צעד האינדוקציה). בשפה פורמלית, אקסיומת האינדוקציה קובעת שלכל פסוק P, מתקיים:

\ [P(1) \wedge \forall n (P(n) \implies P(n+1))] \implies \forall n P(n),

כלומר, אם המספר 1 מקיים את התכונה, ומנכונותה ל-n נובעת הנכונות ל-n+1, אז כל המספרים הטבעיים מקיימים את התכונה.

מבנה ההוכחה[עריכת קוד מקור | עריכה]

מבנה ההוכחה באינדוקציה תמיד זהה: בדיקה למקרה n=1, הנחה עבור n כללי, והוכחה שמההנחה נובעת נכונות הטענה עבור n+1. בין השגיאות הנפוצות בהוכחות באינדוקציה: הוכחת צעד האינדוקציה ללא הבסיס (צעד האינדוקציה תקף באופן ריק גם לתכונות שאף מספר אינו מקיים), או הוכחת צעד האינדוקציה עבור n>2 בלבד (כפי שמדגים פרדוקס הסוסים). הנוסח המתאר את צעד האינדוקציה בספרים אחדים "נניח שהוכחנו את הטענה עבור n, ונוכיח אותה עבור n+1", פגום: אם הוכחנו את הטענה עבור n כללי, אין עוד צורך להוכיח דבר; ואם כך, ניסוח זה של צעד האינדוקציה נכון באופן ריק, ולא ניתן להסיק ממנו דבר.

וריאציות[עריכת קוד מקור | עריכה]

  1. כדי להוכיח באינדוקציה שטענה מסוימת נכונה לכל המספרים הטבעיים ממספר K ואילך, אפשר להוכיח שהיא נכונה עבור K, ושמן הנכונות ל-n נובעת הנכונות ל- n+1. כך אפשר למשל להוכיח ש- \ 2^n>3n^{4} לכל \ n\geq 19 (למרות שהטענה אינה נכונה ל- \ n < 19).
  2. אינדוקציה שלמה. לפעמים הנכונות של טענה Q עבור n+1 אינה נובעת מן הנכונות עבור n, אלא מן הנכונות עבור כל המספרים 1,2,3 ועד n (לדוגמה, כשרוצים להוכיח שכל מספר שלם מתפרק לגורמים ראשוניים). במקרה כזה, אפשר להחליף את התכונה Q בתכונה P, המוגדרת לפי \ P(n) \iff \forall m (m \leq n \implies Q(m)) (הכוונה היא שניתן להחליף את התכונה Q בתכונה P, המוגדרת כך ש- \ P(n) אם ורק כל הטענות \ Q(1), Q(2), \dots, Q(n) נכונות) ולהפעיל את טיעון האינדוקציה הרגיל על P. שיטה זו נקראת "אינדוקציה שלמה" על התכונה Q.
  3. אינדוקציה כפולה (או משולשת וכן הלאה). כאשר הטענה היא על זוגות של מספרים \ P(n,m), אפשר להוכיח אותה לכל n באינדוקציה (רגילה) על הפרמטר m, כאשר בסיס האינדוקציה \ P(n,1) מוכח באינדוקציה על הפרמטר n. לחלופין, אפשר להיעזר בצעד האינדוקציה \ P(n-1,m) \and P(n,m-1) \implies P(n,m), כמו בדוגמה 3 להלן.
  4. עקרון האינדוקציה חל לא רק על המספרים הטבעיים, אלא על כל קבוצה סדורה היטב. כאשר מדובר בקבוצה שהסודר שלה גדול מזה של המספרים הטבעיים, קוראים לתהליך אינדוקציה טרנספיניטית.
  5. יש הוכחות הכרוכות ב"נסיגה אינסופית": מראים שאם הטענה נכונה עבור m, היא נכונה גם עבור ערך קטן יותר, עד שבסופו של דבר מסיקים שהיא נכונה גם עבור m=1. אוילר הראה באופן כזה שאם p ראשוני השקול ל- 1 מודולו 4, אז אפשר להציג את p כסכום של שני ריבועים (בסיס האינדוקציה במקרה זה הוא העובדה שאפשר להציג את \ mp כסכום כזה, אם m גדול מספיק, משום ש-\ -1 הוא שארית ריבועית מודולו p).
  6. אינדוקציה הפוכה. מראים שהטענה נכונה עבור סדרה עולה של מספרים (כגון המספרים \ 2^n), ואז מראים שמן הנכונות ל- m נובעת הנכונות ל- m-1. על שיטה זו מבוססת אחת ההוכחות הקלות לאי-השוויון בין הממוצע הגאומטרי והממוצע החשבוני.

דוגמאות[עריכת קוד מקור | עריכה]

דוגמה 1[עריכת קוד מקור | עריכה]

נוכיח באינדוקציה את הנוסחה \ 1+2+\cdots+n = \frac{n(n+1)}{2} (הנוסחה לסכום המספרים הטבעיים עד n):

ראשית, ברור כי הטענה נכונה ל- n=1, משום שבמקרה זה, הערך בשני האגפים הוא 1. שנית, נניח שהטענה נכונה עבור n, כלומר, \ 1+2+\cdots+n = \frac{n(n+1)}{2}.

עלינו להוכיח את השוויון \ 1+2+\cdots+n+(n+1) = \frac{(n+1)(n+2)}{2}.

אולם, לפי הנחת האינדוקציה, \ 1+2+\cdots+n+(n+1) = (1+2+\cdots + n)+(n+1) = \frac{n(n+1)}{2}+(n+1) =

ואזי \ \frac{(n^2+n)+(2n+2)}{2} = \frac{(n+1)(n+2)}{2} כפי שרצינו.

דוגמה 2[עריכת קוד מקור | עריכה]

מגדלי האנוי הינה חידה פופולרית שבה יש להעביר מגדל של דיסקיות מעמוד אחד לעמוד אחר, תוך שימוש בעמוד עזר ועל פי החוקים הבאים:

  • בכל תור מותר להזיז דיסקית אחת בלבד, מראש עמוד אחד לראש עמוד אחר.
  • אסור להניח דיסקית גדולה על גבי דיסקית קטנה ממנה.

ניתן להוכיח באינדוקציה שניתן לפתור את החידה, לא משנה כמה דיסקיות יש במגדל. כמובן שניתן לפתור את החידה עבור מגדל בעל דיסקית אחת בלבד, בעזרת מהלך אחד. עתה נניח שניתן להעביר מגדל בעל n דיסקיות ונראה שניתן להעביר מגדל בעל n+1 דיסקיות. ההעברה מתבצעת בשלושה שלבים. ראשית נעביר את n הדיסקיות העליונות אל עמוד העזר - דבר שניתן לעשות על פי הנחת האינדוקציה, שנית נעביר את הדיסקית התחתונה - ולבסוף נעביר שוב את n הדיסקיות שעל עמוד העזר אל מעל לדיסקית התחתונה.

דוגמה 3[עריכת קוד מקור | עריכה]

מספר רמזי \ R_{n,m} (עבור \ n,m\geq 2) הוא המספר הקטן ביותר בעל התכונה הבאה: בכל אירוע שבו נפגשים \ R_{n,m} אנשים, מוכרחים להיות n אנשים שכולם מכירים זה את זה, או m אנשים שאף אחד מהם אינו מכיר את רעהו. (יחס ההיכרות הוא יחס סימטרי: אם a מכיר את b, אז גם b מכיר את a). מלכתחילה לא ברור שהמספרים האלו קיימים (משום שייתכן, לכאורה, שאפשר להימנע מן הקבוצות המיוחדות גם באירועים המוניים).

נוכיח שמספרי רמזי קיימים, בכך שנראה ש- \ R_{n,m} \leq \binom{n+m-2}{n-1}, כאשר \ \binom{n+m-2}{n-1}=\frac{(n+m-2)!}{(n-1)!\ (m-1)!} הוא מקדם בינומי.

ראשית, \ R_{n,2} = n משום שאם אין אפילו זוג אנשים שאינם מכירים זה את זה, מוכרחים כולם להכיר את כולם. מאותה סיבה גם \ R_{2,m}=m, ולכן הטענה נכונה כאשר n=2 או m=2. זהו בסיס האינדוקציה. כעת נניח ש- \ n,m\geq 3. נניח שבאירוע משתתפים \ R_{n-1,m}+R_{n,m-1} אנשים. נתבונן במערך ההיכרויות של אחד ממשתתפי האירוע: או שהוא מכיר לפחות \ R_{n-1,m} משתתפים, או שהוא אינו מכיר לפחות \ R_{n,m-1} משתתפים. במקרה הראשון, לפי ההגדרה של \ R_{n-1,m}, יש בין האנשים שהוא מכיר n-1 מכרים-הדדית (ואז יש באירוע כולו קבוצה של n מכרים-הדדית), או שיש ביניהם קבוצה של m זרים-הדדית; במקרה השני, יש בין האנשים שהוא אינו מכיר קבוצה של n מכרים-הדדית, או שיש ביניהם קבוצה של m-1 זרים-הדדית (ואז יש m זרים-הדדית באירוע). הוכחנו שמספר המשתתפים גדול דיו כדי לחייב אחת משתי התוצאות שבהגדרה, ולכן \ R_{n,m} \leq R_{n-1,m}+R_{n,m-1}.

לפי הנחת האינדוקציה, \ R_{n,m} \leq \binom{n+m-3}{n-2}+\binom{n+m-3}{m-2} = \binom{n+m-2}{n-1}. (הערך המדויק של מספרי רמזי ידוע רק במקרים בודדים; אפילו הערך של \ R_{5,5} אינו ידוע).

דוגמה 4[עריכת קוד מקור | עריכה]

עץ בינארי הוא עץ מכוון, שבו לכל קודקוד יש לכל היותר שני בנים, ולכל קודקוד, פרט לקודקוד מיוחס הנקרא שורש, יש אב יחיד. קודקוד של עץ כזה נקרא גם צומת. עלה הוא צומת חסר בנים. עץ לא ריק הוא עץ שקיים בו שורש. צאצאים של כל צומת בעץ יוצרים ביחד איתו תת-עץ של העץ המקורי. נגדיר "צומת מלא" כצומת שיש לו שני בנים.

נוכיח באינדוקציה שבעץ בינארי לא ריק, שמספר העלים בעץ גדול ב-1 ממספר הצמתים המלאים בו.

עבור עץ עם צומת בודד הטענה מתקיימת: ישנו עלה אחד ואין צמתים מלאים. נניח שהטענה נכונה עבור כל עץ בינארי עם n צמתים, כאשר n חיובי. נוכיח שהטענה נכונה עבור עץ עם 1+n קודקודים: בהינתן עץ שאינו שורש עם n+1 צמתים, נסיר ממנו עלה כלשהו ונקבל עץ חדש עם n צמתים. נסמן את מספר העלים ב-N0 ואת מספר הצמתים המלאים ב-N2. על-פי הנחת על בעץ החדש מתקיים השוויון N0=N2+1.

נחזיר חזרה לעץ את העלה שהסרנו.

אם העלה שהוסר היה בן יחיד מספר העלים לאחר החזרתו לא השתנה: מצד אחד עלה אחד נוסף ומצד שני אותו הצומת שהוסיפו לו עלה הפך מעלה לאב יחיד. מספר הצמתים המלאים לא השתנה אף הוא ולכן השוויון נשמר.

אם העלה שהוסר לא היה בן יחיד אז מצד אחד מספר הצמתים המלאים בעץ לאחר החזרת העלה גדל ב-1, ומצד שני מספר העלים גדל ב-1 לאחר החזרת העלה. ולכן גם במקרה זה השוויון נשמר.

דוגמה 5[עריכת קוד מקור | עריכה]

ישנן גם הוכחות שגויות, המבוססות על גרסה שגויה של אקסיומת האינדוקציה או שיש בהן דילוג על שלב מהותי. למרות שברוב ההוכחות באינדוקציה הבדיקה לערך קטן של n היא קלה ומיידית, ישנם מקרים שבהם צעד האינדוקציה תקין והבעיה היא דווקא בערכים הקטנים. דוגמה מפורסמת לתופעה זו היא פרדוקס הסוסים, המתיימר להוכיח שכל הסוסים בעולם הם בעלי אותו צבע. מכיוון שמספר הסוסים בעולם סופי, אפשר להוכיח את הטענה באינדוקציה: בכל קבוצה בת n סוסים, לכולם יש אותו צבע. טענה זו נכונה כמובן ל-n=1. כעת נניח שהטענה נכונה ל-n, ונוכיח אותה ל-n+1: נבודד אחד מבין n+1 הסוסים, כך שישארו n סוסים, שכולם בעלי אותו צבע לפי הנחת האינדוקציה. נחליף את הסוס שהוצאנו קודם לכן בסוס אחר, ושוב נקבל שלכל הסוסים בקבוצה שלפנינו אותו צבע. לכן לכל n+1 הסוסים יש אותו צבע.

הטענה נכונה עבור n=1, אבל המעבר מ-n ל-n+1 תקין רק בתנאי ש-n>1, משום שכדי להסיק שלכל n+1 הסוסים אותו צבע, אנו מניחים שבשתי הקבוצות בגודל n יש סוסים משותפים, שאליהם אפשר להשוות את שני הסוסים שהוצאנו בתחילת הצעד ובסופו. אם הטענה הייתה נכונה עבור n=2 (לכל שני סוסים יש אותו צבע), באמת אפשר היה להוכיח אותה לכל n. אבל המעבר מ-n=1 ל-n=2 (אם לכל סוס יש הצבע שלו, אז לכל שני סוסים יש צבע משותף) שגוי, ולכן ההוכחה אינה תקפה.

תקפותה של הוכחה באינדוקציה[עריכת קוד מקור | עריכה]

לכאורה, מבוססת האינדוקציה המתמטית על הפעלה חוזרת של כלל הגזירה מודוס פוננס. לדוגמה, כדי להוכיח את הטענה \ P(4), די להוכיח את טענת הבסיס \ P(1), ואת הגרירות \ P(1)\implies P(2), \ P(2)\implies P(3) ו- \ P(3)\implies P(4): מן הגרירה הראשונה נובע (לפי טענת הבסיס) \ P(2), מן הגרירה השנייה נובע כעת \ P(3), ומן השלישית - \ P(4). מכיוון שבצעד האינדוקציה הוכחנו את כל הגרירות \ P(n) \implies P(n+1), אפשר להוכיח באופן הזה את כל הטענות \ P(n).

אם לדייק, מצאנו, לכל n, סדרה סופית של טיעונים, המוכיחה ש- \ P(n); אבל מספר הצעדים בכל הוכחה הולך וגדל. זהו מעין "אפקט דומינו": כל אבן מפילה את האבן שאחריה, וכל אבן תיפול בזמן סופי, אבל אם השרשרת אינסופית, הזמן עד שיפלו כולן הוא אינסופי. עקרון האינדוקציה הופך את הסדר: הוא נותן הוכחה בסדרה סופית של טיעונים, לכל אינסוף הטענות \ P(n).

יש שתי גישות להצדקת עקרון האינדוקציה. במערכת האקסיומות המגדירה את מערכת פאנו של המספרים הטבעיים, ישנה סכימת אקסיומות מיוחדת, הקובעת את חלות האינדוקציה. במסגרת הרחבה יותר של תורת הקבוצות האקסיומטית, המבוססת על אקסיומות צרמלו-פרנקל, נובע עקרון האינדוקציה מכך שקבוצת המספרים הטבעיים סדורה היטב (ראו עקרון הסדר הטוב): אם הטענה \ P(n) אינה מתקיימת לכל n, מוכרח להיות מספר קטן ביותר שעבורו היא אינה מתקיימת; מספר זה אינו יכול להיות 1, משום שבסיס האינדוקציה מאשר את הטענה \ P(1), והוא אינו יכול להיות גדול מ- 1, משום שבמקרה כזה הטענה \ P(n) נובעת מן הטענה \ P(n-1), הנכונה לפי המינימליות של n.

בתורה, העובדה שקבוצת המספרים הטבעיים סדורה היטב נובעת מאקסיומת האינסוף (הקובעת שקיימת קבוצה רקורסיבית אינסופית), ומאקסיומת היסוד.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ 1.0 1.1 Florian Cajori, ‏Origin of the name Mathematical Induction, American Mathematical Monthly 25 (1918), pp. 197--201, in JSTOR.‏
  2. ^ ‏Carl B. Boyer, A History of Mathematics, 2nd ed., p. 364‏
  3. ^ ‏ W.H. Bussey, "The Origin of Mathematical Induction", American Mathematical Monthly 24 (1917), pp. 199--207. ‏
  4. ^ ‏Nachum L. Rabinovitch, "Rabbi Levi Ben Gershon and the Origins of Mathematical Induction, Archive for the History of Exact Sciences, Vol. 6(3), (1970)‏
ערך מומלץ
Article MediumPurple.svg