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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

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

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

דוגמה לשימוש באינדוקציה: נוכיח את הטענה הבאה: $\forall n\in\mathbb{N} , \sum_{k=1}^{n} \left( 2\times k-1 \right) =n^2$ . הוכחה: נוכיח, כאמור, באינדוקציה.
שלב א': בסיס האינדוקציה: נבדוק את נכונות הטענה עבור $\ n=1$ :

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

שלב ג': צעד האינדוקציה: בשלב זה נוכיח, שהנחת האינדוקציה עבור $\ n-1$ גוררת את נכונות הטענה גם עבור $\ n$ . או בכתיב מתמטי: $\sum_{k=1}^{n-1} \left( 2\times k-1 \right) =\left( n-1 \right) ^2 \Rightarrow \sum_{k=1}^n \left( 2\times k-1 \right) = n^2$ . ונוכיח באופן הבא: מתקיים: $\sum_{k=1}^n \left( 2\times k-1 \right)=\underbrace{ \sum_{k=1}^{n-1} \left( 2\times k-1 \right) }_{ \left( * \right )} + \left( 2\times n-1 \right)$ . כעת: האיבר (*) שווה, לפי הנחת האינדוקציה, ל- $\left( n-1 \right) ^2$ . כלומר, נוכל לכתוב:
$\sum_{k=1}^n \left( 2\times k-1 \right) =\sum_{k=1}^{n-1} \left( 2\times k-1 \right) + \left( 2\times n-1 \right) = \left( n-1 \right) ^2 + \left( 2\times n-1 \right) =$ $= \left( n^2 -2n +1 \right) +2n-1 =n^2 -2n+1+2n-1 =n^2$ .
ובזאת סיימנו את ההוכחה. במתמטיקה, נהוג לסמן בסוף הוכחה ריבוע קטן: ▪.