מתמטיקה תיכונית/אלגברה תיכונית/אינדוקציה מתמטית/הקדמה - אינדוקציה

מעט רקע היסטורי

דיוויד יום

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

1. סמיכות מקום - למשל "העפרון נפל בגלל שהיד והעפרון היו באותו מקום".
2. סמיכות זמן - למשל "העפרון התגלגל בגלל שהיד והעפרון היו באותה העת".
3. סמיכות לוגית - למשל "לא היה גורם אחר שגרם לעפרון להתגלגל". לא תמיד אנו יכולים להוכיח סעיף זה ולכן, האינדוקציה לא תקפה.

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

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

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

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

מה עושים בשלב	הפעולה	מה רושמים בפועל	דוגמא
תחילה, בדיקת נכונות התכונה עבור המספר הטבעי הראשון, 1. כאמור, האינדוקציה לא תמיד נכונה ולכן, גם לא תמיד נכונה מתמטית. לכן, אנו נעזרים באינדוקציה בשביל להוכיח תכונה, אקסיומת ("עקרון מובן מאליו") המיוחסות לקבוצת מספרים טבעיים בלבד, על מנת להוכיח שהן נכונות לכלל המספרים הטבעים בלבד.	בשלב זה נציב את $n=1$ בכל צד של המשוואה. נציין מתי אנו מציבים בצד שמאל ומתי בימין. נכונות הטענה בהתאם לסימן בין שני חלקיה: גדול, קטן ו/או שווה. יתכן מקרה בשלב זה.	בדיקת נכונות הטענה עבור $n=1$ נציין מתי אנו מציבים בצד שמאל ומתי בימין. נכונות הטענה בהתאם לסימן בין שני חלקיה: גדול, קטן ו/או שווה. $L_{eft}$ - צד שמאל של המשוואה. $R_{ight}$ - צד ימין של המשוואה. הערה: מקרה 1 - כשהבדיקה יוצאת שגויה	${\begin{aligned}&L_{eft}:n=1\\&R_{ight}={\frac {n(n+1)}{2}}={\frac {1(1+1)}{2}}=1\\\end{aligned}}$
שנית, שהתכונה נכונה עבור כלל האברים הטבעיים ולא רק למספר טבעי אחד.	במקום n נציב k.	נניח כי הטענה נכונה עבור $n=k$ טבעי	$1+\cdots +k={\frac {k(k+1)}{2}}$
התכונה נכונה גם לאבר הטבעי הבא - כפי שטענו אנו רוצים להוכיח שמה שנכון ל- $n$ נכון גם ל- $k+1$ . מספר מקרים יכולים לחול בשלב זה, ראה פירוט כאן	נציב $n=k+1$ .	נוכיח כי הטענה נכונה עבור $n=k+1$	$1+\cdots +k+(k+1)={\frac {(k+1)(k+2)}{2}}$
(שלב בניינים) על-פי ההנחה	בשלב זה אנו מציבים את ההנחה במקום הסדרה המוצגת להקלה על פתרון התרגיל. סימנו בסוגרים, כדי שתשמו לב שבשלב זה אנו מציבים את ההנחה במקום הסדרה, כיון שעל-פי ההנחה (שלב ב') הסדרה שווה לסכום הבא : $1+\cdots +k={\frac {k(k+1)}{2}}$ בתרגיל.		${\begin{aligned}&\underbrace {1+\cdots +k} _{\frac {k(k+1)}{2}}+(k+1)={\frac {(k+1)(k+2)}{2}}\\&{\frac {k(k+1)}{2}}+k+1={\frac {(k+1)(k+2)}{2}}\\\end{aligned}}$
פתירת התרגיל			${\begin{aligned}&{\frac {k(k+1)}{2}}+k+1={\frac {(k+1)(k+2)}{2}}\\&k(k+1)+2k+2=(k+1)(k+2)\\&k^{2}+k+2k+2=k^{2}+3k+2\\&0=0\\\end{aligned}}$
סיום התרגיל.		הטענה נכונה עבור כל n טבעי, ע"פ שלושת שלבי האינדוקציה.

פעולות מתמטיות ואינדוקציה

חשיבות לפעולות המתמטיות הנמצאות בתרגיל:

1. אינדוקציה סכום - אינדוקציה בה הפעולה בין כל אבר היא חיבור.
2. אינדוקציה מכפלה - אינדוקציה בה הפעולה בין כל אבר היא כפל.
3. אינדוקציה עם שברים.
4. אינדוקצית חזקה - חוקי חזקות חשובים לאינדוקציה. ניתן דוגמאות לחוקים חשובים:
   • $7^{k+4}=7^{k}\cdot 7^{4}=7^{k}(7^{2}+7^{2})=7^{k}(49+49)$
   • אחת בחזקת כל מספר טבעי שווה לאחת, כך למשל, $1^{2k}=1$
5. אינדוקציה עם עצרת.
6. אינדוקציה עם סמנים מתחליפים.

תרגול

תרגילים להפנמת הנושא: בני גורן 006 ע"מ 91 תרגיל 1, בני גורן 006, ע"מ 91 תרגיל 7.

תרגול : 92/26, 92/41, 94/59, 96/80, 96/87.

בהמשך נלמד להשים לב למקרים המתרחשים במהלך פתרון האינדוקציה

מושגים בסיסים מסדרות

1. סדרה כללית ($a_{n}$) - קבוצה סדורה של עצמים.
2. מיקום ($n$) - לכל מספר יש מקום, מקום ראשון ($n=1$), מקום שני ($n=2$)...
3. אברי סדרה - כל עצם בסדרה נקרא אבר. אם נציב את $n$ בנוסחא ל-$a_{n}$ נוכל לקבל הצגה של המספר: מספר ראשון ($a_{1}$), שני ($a_{2}$)...
4. האבר עצמו - זהו המספר העומד במקום. למשל, $a_{1}=6$ ; המספר שש הוא המספר הראשון בסדרה.
5. סכום הסדרה/טור ($S_{n}$) - סכום הסדרה מתקבל באופנים שונים, למשל בסדרה חשבונית הוא חיבור כלל אברי הסדרה. בתום הצגת הסדרה, פעמים רבות יוצג בפניו סכומה (אינדוקציה על סכומים), ובהצגה כללית כך : $a_{1}+a_{2}+a_{3}+\cdots +a_{n}=S_{n}$ .