מבוא למתמטיקה אוניברסיטאית/אינדוקציה

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

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

דוגמא

דוגמה לשימוש באינדוקציה: נוכיח את הטענה הבאה: $\forall n\in \mathbb {N} \ ,\ \sum _{m=1}^{n}(2m-1)=n^{2}$ .

הוכחה

נוכיח, כאמור, באינדוקציה.

שלב א': בסיס האינדוקציה: נבדוק את נכונות הטענה עבור $n=1$ :

$\sum _{m=1}^{n}\underbrace {=} _{*}\sum _{m=1}^{1}(2m-1)=2\times 1-1=1=n^{2}$

כאשר בשלב * אנו מציבים $n=1$ . כלומר, אנו רואים ש- $n=1$ מקיים את הטענה.

שלב ב': הנחת האינדוקציה: נניח שלמספר $n=k$ מסוים הטענה נכונה. מותר לנו להניח זאת, משום שהוכחנו שקיים מספר ($1$) שלגביו הטענה נכונה, ותמיד נוכל לטעון שאנו מתייחסים למספר זה בהנחת האינדוקציה. כלומר, הנחת האינדוקציה הנה: קיים $k\in \mathbb {N}$ , כך שעבורו מתקיים:

$\sum _{n=1}^{k}(2n-1)=k^{2}$ .

(הערה: נכון הוא שהשימוש הרב באותו סימון, $n$ , עלול להיות מבלבל. עם זאת, זוהי הדרך המקובלת לסימון, לכן כדאי שהקורא יתרגל לכך כבר בשלב זה).

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

$\sum _{n=1}^{k}(2n-1)=k^{2}\ \Rightarrow \ \sum _{n=1}^{k+1}(2n-1)=(k+1)^{2}$

ונוכיח באופן הבא: מתקיים:

$\sum _{n=1}^{k+1}(2n-1)=\underbrace {\sum _{n=1}^{k}(2n-1)} _{(*)}+(2(k+1)-1)$

כעת: האבר (*) שווה, לפי הנחת האינדוקציה, ל- $k^{2}$ . כלומר, נוכל לכתוב:

${\sum _{n=1}^{k+1}(2n-1)=\sum _{n=1}^{k}(2n-1)+{\bigl (}2(k+1)-1{\bigr )}=k^{2}+{\bigl (}2(k+1)-1{\bigr )}=k^{2}+2k+2-1=k^{2}+2k+1=(k+1)^{2}}$

ובזאת סיימנו את ההוכחה. $\blacksquare$

אינדוקציה שלמה

לעתים זקוקים לטענה חזקה יותר בהנחת האינדוקציה. למשל, בטענה "נניח שלמספר $n=k$ מסוים הטענה נכונה" אין כלל חשיבות מאיזה מספר מתחילים, כלומר גם אם היינו מתחילים את בסיס האינדוקציה מהמספר 2 בבדיקת הסכום $\sum _{m=1}^{n}(2m-1)=n^{2}$ היינו מקבלים תוצאה נכונה.

למעשה, ניסוח האינדוקציה הוא כך:

כיון שאנו כבר יודעים שהטענה $P$ נכונה עבור מספר כלשהו $n=k$ , נבדוק אם זה גורר נכונות $P$ עבור העוקב $n=k+1$ ― באם והתשובה חיובית, אזי הטענה נכונה לכל $n\in \mathbb {N} _{\geq k}$ .

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

לטיעון החזק יותר קוראים "אינדוקציה שלמה".

הניסוח: נניח כי הטענה $P$ נכונה לכל המקרים $n\in {\big \{}1,\ldots ,k{\big \}}$ , ונבדוק אם נכונותה לכל אלה גוררת נכונות $P$ עבור $n=k+1$ ― באם התשובה חיובית, אזי הטענה נכונה לכל $n\in \mathbb {N}$ .

טיעון הדומינו כאן שונה: "אם נתון כי כל האבנים הנופלות בזו אחר זו מפילות את האבן הבאה בתור (ללא יוצא מן־הכלל), ובנוסף נתון כי אכן נפלה שורת אבנים בזו אחר זו, נובע מכך שהאבן הבאה אחריהן תיפול אף היא ― ומכאן שכולן תיפולנה בסופו של דבר".

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

הפרק הקודם: הגדרות וסימונים נוספים

אינדוקציה

הפרק הבא: הוכחה בשלילה