|
==מהי אינדוקציה?==
======
באינדוקציה,אינדוקציה צריךהינה בדרך-כללכלי להוכיחמתמטי. בעזרתה מוכיחים טענה מסוימת או תכונה של קבוצת מספרים. היופי שלה הוא ששבליבה נמצא "אפקט הדומינו" הוא מה שנמצא בלב האינדוקציה- אנחנו מוכיחים טענה עבור מספר כלשהו, <math>\ k </math> (שיכול להיות כל מספר טבעי שהוא), ועבור המספר העוקב שלו, <math>\ k+1 </math> . ההגדרההגדרה הזוזו מכסה את כל המספרים הטבעיים החל ממקום מסויים, ובהוכחה עבור מקרה כללי (שהוא יותר אמין ויותר פרקטי) כיסינו את כל המקרים שיכולים להיות.
* הערה חשובה-: בפרק הזה אנינעבוד אעבודעם האות עם <math>\ k </math> , למרות שניתן להשתמש בסימונים אחרים, כמו <math>\ p,m,n </math> או כל אות לטינית אחרת. שחף_ו
אני'''ידע כותבקודם אתדרוש''': הספרעל הזההקורא בתוךלהכיר הנחה,את שהקוראהנושאים כבר מכיר אתהבאים: פעולות החשבון, סדרות, הצבה בנוסחה ומספר מיומנויות אנליטיות כמו פתרון משוואה ריבועית.
אם לא- כדאי והכרחי להבין את הנושאים האלו, כי בלעדיהם יהיה קשה להבין את החומר.
בהוכחות באינדוקציה, יש מבנה קבוע ומוגדר מראש שצריך לעקוב אחריו. המבנהמבנה זה עוזר, לדעתי, ב"ראיית" ההוכחה ומסדר את הטיעונים הדרושים להוכחת הטענה. להלן תמצית המבנה עם דוגמה לפתרון:
<u>להלן תמצית המבנה עם דוגמה לפתרון<u\>:
הוכח שהביטוי <math>2n^2+3n-4</math> חיובי לכל n טבעי. ▼
שלב א'- בדיקה (זהו מקרה פרטי של הנוסחה!!) עבור n=1. מציבים במקום nבטענה את המספר המבוקש, ואחרי הצבה מקבלים 1 שהוא מספר חיובי. הבדיקה התקבלה.
שלבהוכח ב'- הנחת האינדוקציה- עבור n=k, הביטוישהביטוי <math>2k\ 2n^2+3k3n-4</math> חיובי לכל <math>\ n </math> טבעי.</br>
פתרון:
שלב ג'- צ"ל, שעבור n=k+1 מתקיים- <div style="text-align:left; direction:ltr;">
* שלב א': בדיקה עבור <math>\ n=1 </math> (אם בתרגיל עלינו להוכיח שהטענה מתקיימת החל ממספר מסויים <math>\ p </math>, מתחילים את הבדיקה עבור <math>\ n=p </math>. מציבים במקום <math>\ n </math> בטענה את המספר עבורו בודקים, ולאחר ההצבה מקבלים: <math>\ 2n^2+3n-4= 2*1^2+3*1-4= 2+3-4=1</math> שהוא מספר חיובי. כלומר, הטענה נכונה עבור המקרה הפרטי של <math>\ n=1 </math>.
<math>2(k+1)^2+3(k+1)-4>0</math>. ▼* שלב ב': הנחת האינדוקציה: אנו מניחים שעבור <math>\ n=k </math> , הביטוי <math>\ 2k^2+3k-4</math> חיובי. על מה מתבססת ההנחה שלנו? - על השלב הקודם, בו הראינו שהטענה נכונה עבור <math>\ n </math> מסויים.
* שלב ג: צ"ל (צריך להוכיח), שעבור <math>\ n=k+1 </math> מתקיים- <math>\ 2(k+1)^2+3(k+1)-4>0</math>.
</div>
נפתח סוגריים, ונפשטנפשט את הביטוי ונקבל- :<div/br> style="text-align:left; direction:ltr;">
<math>\ = 2(k^2+2k+1)+3(k+1)-4=2k^2+4k+2+3k+3-4=2k^2+7k+1 </math>
▲<math> 2(k+1)\ =2k^2+ 3(k7k+1 )-4>0</math> .
</div>, כלומר מספיק להוכיח שהביטוי <math>2k^2+7k+1</math> חיובי לכל k טבעי.
▲הוכח</br>כלומר, מספיק להוכיח שהביטוי <math> 2n\ 2k^2+ 3n-47k+1</math> חיובי לכל n<math>\ k </math> טבעי.
בשבילעל הפתרון,מנת להוכיח זאת ניעזר בהנחת האינדוקציה (במקרים אחרים היא הדרך היחידה לפתרון נכון), ונפרק את הביטוי <math>\ 2k^2+7k+1</math>, כך שיהיהשנקבל את הנחת האינדוקציה ועוד איבר/ים מסוים/מים(או איברים). ואז, כל שיוותר לנו הוא להוכיח עבור האיברים הנוספים. נקבל:</br>
משם נותר להוכיח רק לגבי האיבר/ים שהתווספו. נקבל: <math>2k^2+7k+1=2k^2+3k+4k-4+5=2k^2+3k-4+4k+5>0</math>.
<math>\ 2k^2+7k+1=2k^2+3k+4k-4+5=2k^2+3k-4+4k+5>0</math>.
הביטוי <math>\ 2k^2+3k-4</math> הוא הנחת האינדוקציה והוא חיובי לכל <math>\ k </math> טבעי (נובע מההנחה).
קל להוכיח, שהביטוי <math>\ 4k+5 </math> הוא ביטוי חיובי לכל <math>\ k </math> טבעי. <br\>
<nowiki> * </nowiki>מסקנה-: קיבלנו סכום של שני ביטויים חיוביים-, שהוא תמיד חיובי. מש"ל.
לסיכום- בהוכחות באינדוקציה ישנם שלושה שלבים:
*שלב א'-: בדיקת הנוסחה למקרה/יםלמקרהם פרטי (או למקרים פרטיים), שבהםשבו רואים שהטענהאת נכונהנכונות אוהטענה החלעבורו מאיזה מספר היא(או נכונהעבורם).
*שלב ב'-: הנחת האינדוקציה-: בהתבסס על השלב הקודם, '''מניחים''' שעבור מספר כלשהו,<math>\ n=k </math>, הטענה נכונה ומנסחים את הטענה עבור אותו מספר.
*שלב ג'-: '''מוכיחים'''מנסחים שהטענהאת נכונההטענה עבור המספר העוקב, כלומר עבור<math>\ n=k+1 </math>, ומנסחים את הטענהו'''מוכיחים''' עבורואותה. ניתן להעזר בהנחה לצורך ההוכחה, ובהרבהוברוב מקרים-המקרים היא הכרחית.
אחרילאחר ההוכחה, רושמים את המסקנה. ניתן לסיים אותה בכל דרך שתרצו (כמו מ.ש.ל או מש"ל, Q.E.D, שרטוט ריבוע קטן וכולי).
===אינדוקציות של סכומים===
| 