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






