מבוא למתמטיקה אוניברסיטאית/אינדוקציה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ הוספת קטגוריה:מבוא למתמטיקה אוניברסיטאית באמצעות HotCat |
אין תקציר עריכה |
||
שורה 1:
{{מבוא למתמטיקה אוניברסיטאית}}
ה''
===דוגמא===
דוגמה לשימוש באינדוקציה: נוכיח את ה'''''טענה''''' הבאה: <math>\forall n\in\
נוכיח, כאמור, באינדוקציה. <u>שלב א'</u>: ''בסיס האינדוקציה'': נבדוק את נכונות הטענה עבור <math>\ n=1 </math>: ▼
<math>\sum_{k=1}^n \underbrace{ = }_{*} \sum_{k=1}^1 \left( 2\times k-1 \right) =2\times 1-1=1=n^2</math>.▼
כאשר בשלב * אנו מציבים <math>\ n=1 </math>. כלומר, אנו רואים ש-<math>\ n=1 </math> מקיים את הטענה.</br>▼
<u>שלב ב'</u>: ''הנחת האינדוקציה'': נניח שלכל מספר הקטן מ- <math>\ n </math> מסויים, הטענה נכונה. מותר לנו להניח זאת, משום שהוכחנו שקיים מספר <math>\ \left( 1 \right) </math> שלגביו הטענה נכונה, ותמיד נוכל לטעון שאנו מתייחסים למספר זה בהנחת האינדוקציה. כלומר, הנחת האינדוקציה הינה: קיים <math>n\in\mathbb{N}</math>, כך שעבור כל <math>\ n </math> הקטן ממנו, וגם עבורו עצמו, מתקיים:▼
(הערה: נכון הוא שהשימוש הרב באותו סימון, <math>\ n </math>, עלול להיות מבלבל. עם זאת, זוהי הדרך המקובלת לסימון, לכן כדאי שהקורא יתרגל לכך כבר בשלב זה).</br>▼
▲:<math>\sum_{
<u>שלב ג'</u>: ''צעד האינדוקציה'': בשלב זה נוכיח, שהנחת האינדוקציה עבור <math>\ n-1 </math> גוררת את נכונות הטענה גם עבור <math>\ n </math>. או בכתיב מתמטי: ▼
<math>\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</math>.▼
▲כאשר בשלב * אנו מציבים <math>
▲<u>שלב ב'</u>: ''הנחת האינדוקציה'': נניח
:<math>\sum_{n=1}^k(2n-1)=k^2</math> .
▲(הערה: נכון הוא שהשימוש הרב באותו סימון, <math>
▲<u>שלב ג'</u>: ''צעד האינדוקציה'': בשלב זה נוכיח, שהנחת האינדוקציה עבור <math>
▲:<math>\sum_{
ונוכיח באופן הבא: מתקיים:
:<math>\sum_{n=1}^{k+1}(2n-1)=\underbrace{\sum_{n=1}^k(2n-1)}_{(*)}+(2k-1)</math>
כעת: האבר (*) שווה, לפי הנחת האינדוקציה, ל- <math>k^2</math> . כלומר, נוכל לכתוב:
:<math>\sum_{n=1}^{k+1}(2n-1)=\sum_{n=1}^k(2n-1)+\big(2(k+1)-1\big)=k^2+\big(2(k+1)-1\big)=k^2+2k+2-1=k^2+2k+1=(k+1)^2</math>
ובזאת סיימנו את ההוכחה. <math>\blacksquare</math>
==אינדוקציה שלמה==
לעתים זקוקים לטענה חזקה יותר בהנחת האינדוקציה. למשל, בטענה "נניח שלמספר <math>n=k</math> מסוים הטענה נכונה" אין כלל חשיבות מאיזה מספר מתחילים, כלומר גם אם היינו מתחילים את בסיס האינדוקציה מהמספר 2 בבדיקת הסכום <math>\sum_{m=1}^n(2m-1)=n^2</math> היינו מקבלים תוצאה נכונה.
למעשה, ניסוח האינדוקציה הוא כך:
'''כיון שאנו כבר יודעים שהטענה <math>P</math> נכונה עבור מספר כלשהו <math>n=k</math> , נבדוק אם זה גורר נכונות <math>P</math> עבור העוקב <math>n=k+1</math> ― באם והתשובה חיובית, אזי הטענה נכונה לכל <math>n\in\N_{\ge k}</math>''' .
הדבר דומה למשחק דומינו: "אם נתון כי '''כל אבן הנופלת''' מפילה '''רק את זו שאחריה''' (ללא יוצא מן-הכלל), ובנוסף נתון כי אכן '''נפלה אבן כלשהיא''', נובע מכך שכל האבנים שאחריה תיפולנה אף הן".
לטיעון החזק יותר קוראים "אינדוקציה שלמה".
הניסוח: '''נניח כי הטענה <math>P</math> נכונה לכל המקרים <math>n\in\big\{1,\ldots,k\big\}</math> , ונבדוק אם נכונותה לכל אלה גוררת נכונות <math>P</math> עבור <math>n=k+1</math> ― באם התשובה חיובית, אזי הטענה נכונה לכל <math>n\in\N</math>''' .
טיעון הדומינו כאן שונה: "אם נתון כי '''כל האבנים הנופלות בזו אחר זו''' מפילות '''את האבן הבאה בתור''' (ללא יוצא מן-הכלל), ובנוסף נתון כי אכן '''נפלה שורת אבנים בזו אחר זו''', נובע מכך שהאבן הבאה אחריהן תיפול אף היא ― ומכאן שכולן תיפולנה בסופו של דבר".
שימושים באינדוקציה שלמה הם כגון בהוכחות מודרניות ל"משפט היסודי של האריתמטיקה".
{{מבוא למתמטיקה אוניברסיטאית|מוגבל=כן}}
|