מבוא למתמטיקה אוניברסיטאית/אינדוקציה: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 1:
{{מבוא למתמטיקה אוניברסיטאית}}
===מהי אינדוקצייה=אינדוקציה==
ה''אינדוקצייהאינדוקציה'' הינההנה כלי מתמטי חשוב מאוד. באינדוקצייהבאינדוקציה אנו מוכיחים טענה "אינסופית" (כלומר, כזו הנכונה עבור אינסוף מספרים) באופן הבא: ראשית אנו מראים את נכונות הטענה עד מספר טבעי מסוייםמסוים, ולאחר מכן אנו מראים כיצד נכונות הטענה עבור מספר זה גוררת את נכונותה גם עבור המספר הבא בתור.
 
===דוגמא===
דוגמה לשימוש באינדוקציה: נוכיח את ה'''''טענה''''' הבאה: <math>\forall n\in\mathbb{N}\ ,\ \sum_{km=1}^{n} \left( 2\times k2m-1 \right) =n^2</math> .
''''';הוכחה''''':
נוכיח, כאמור, באינדוקציה.</br>
<u>שלב א'</u>: ''בסיס האינדוקציה'': נבדוק את נכונות הטענה עבור <math>\ n=1 </math>:
 
<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>\sum_{k=1}^{n-1}\left( 2\times k-1 \right) = \left( n-1 \right) ^2</math>.
(הערה: נכון הוא שהשימוש הרב באותו סימון, <math>\ n </math>, עלול להיות מבלבל. עם זאת, זוהי הדרך המקובלת לסימון, לכן כדאי שהקורא יתרגל לכך כבר בשלב זה).</br>
 
:<math>\sum_{km=1}^n \underbrace{ = }_{*} \sum_{km=1}^1 \left( 2\times k2m-1 \right) =2\times 1-1=1=n^2</math>.
<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>\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) </math>.
כעת: האיבר (*) שווה, לפי הנחת האינדוקציה, ל- <math>\left( n-1 \right) ^2</math>. כלומר, נוכל לכתוב:</br> <math>\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) =</math>
<math>= \left( n^2 -2n +1 \right) +2n-1 =n^2 -2n+1+2n-1 =n^2 </math>.</br>ובזאת סיימנו את ההוכחה. במתמטיקה, נהוג לסמן בסוף הוכחה ריבוע קטן: ▪.
 
כאשר בשלב * אנו מציבים <math>\ n=1 </math> . כלומר, אנו רואים ש- <math>\ n=1 </math> מקיים את הטענה.</br>
<table id=toc width = 75% border = 1 align="center">
<tr>
 
<u>שלב ב'</u>: ''הנחת האינדוקציה'': נניח שלכל מספר הקטן מ-שלמספר <math>\ n =k</math> מסויים,מסוים הטענה נכונה. מותר לנו להניח זאת, משום שהוכחנו שקיים מספר (<math>\ \left( 1 \right) </math>) שלגביו הטענה נכונה, ותמיד נוכל לטעון שאנו מתייחסים למספר זה בהנחת האינדוקציה. כלומר, הנחת האינדוקציה הינההנה: קיים <math>nk\in\mathbb{N}</math> , כך שעבור כל <math>\ n </math> הקטן ממנו, וגם עבורו עצמו,שעבורו מתקיים:
:<math>\sum_{n=1}^k(2n-1)=k^2</math> .
(הערה: נכון הוא שהשימוש הרב באותו סימון, <math>\ n </math> , עלול להיות מבלבל. עם זאת, זוהי הדרך המקובלת לסימון, לכן כדאי שהקורא יתרגל לכך כבר בשלב זה).</br>
 
<u>שלב ג'</u>: ''צעד האינדוקציה'': בשלב זה נוכיח, שהנחת האינדוקציה עבור <math>\ n-1 =k</math> גוררת את נכונות הטענה גם עבור העוקב <math>\ n =k+1</math> . או בכתיב מתמטי:
 
:<math>\sum_{kn=1}^{n-1} \leftk( 2\times k2n-1 \right) =\left( n-1 \right) k^2\ \Rightarrow\ \sum_{kn=1}^n \left{k+1}( 2\times k2n-1 \right) = n(k+1)^2</math>.
 
ונוכיח באופן הבא: מתקיים:
 
:<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>''' .
 
טיעון הדומינו כאן שונה: "אם נתון כי '''כל האבנים הנופלות בזו אחר זו''' מפילות '''את האבן הבאה בתור''' (ללא יוצא מן-הכלל), ובנוסף נתון כי אכן '''נפלה שורת אבנים בזו אחר זו''', נובע מכך שהאבן הבאה אחריהן תיפול אף היא ― ומכאן שכולן תיפולנה בסופו של דבר".
 
 
שימושים באינדוקציה שלמה הם כגון בהוכחות מודרניות ל"משפט היסודי של האריתמטיקה".
 
{{מבוא למתמטיקה אוניברסיטאית|מוגבל=כן}}