הצגת המקור של הדף "קומבינטוריקה להנדסה תרגול 3 - אינדוקציה"

=אינדוקציה מתמטית: רעיון בסיסי=

אינדוקציה היא שיטה המאפשרת להוכיח שטענה מסוימת <math>P(n)</math> נכונה עבור כל מספר טבעי 
(למשל <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>) בעזרת הסקה מן הפרט אל הכלל.

הוכחת הטענה <math>\forall nP(n)</math> שקולה להוכחת שתי הטענות הבאות:
* (בסיס האינדוקציה) הטענה מתקיימת עבור <math>n=0</math>. כלומר <math>P(0)</math> נכון.
* (צעד האינדוקציה) '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>\forall n\in \mathbb{N}:(P(n)\rightarrow P(n+1))</math>.

למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=0</math> כלומר <math>P(0)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=0</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=1</math>. כלומר <math>P(1)</math>. אה! אז עכשיו כיון שזה נכון עבור <math>n=1</math>, אז לפי אותה טענה זה נכון גם עבור <math>n=2</math>! ומה עכשיו? אם זה נכון עבור <math>n=2</math>, זה נכון עבור <math>n=3</math>. וכן הלאה באותה הדרך. אפשר להשתכנע שבסופו של דבר <math>P(n)</math> נכון '''לכל''' <math>n</math>.

===תרגיל===
נוכיח באינדוקציה כי הטענה <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math> 
נכונה לכל <math>n\in \mathbb{N} </math> טבעי.

====הוכחה====

עבור <math>n=0</math> אכן מתקיים כי <math>0^2=0^3</math>.

כעת נראה ש <math>\forall n\in \mathbb{N}:(P(n)\rightarrow P(n+1))</math>:

יהי <math>n</math> כלשהוא, ונניח שמתקיים 
<math>(0+1+2+\cdots +n)^2 =0^3+1^3 +2^3 + \cdots +n^3</math>. צריך להראות שהטענה נכונה עבור <math>n+1</math>, כלומר שמתקיים 
<math>(0+1+2+\cdots +n+(n+1))^2 =0^3+1^3 +2^3 + \cdots +n^3 + (n+1)^3</math>. (שימו לב שה-0 פה לא תורם כלום אז נייתן להתעלם ממנו).

נוכיח: 

<math>(1+2+\cdots +n+(n+1))^2=(1+2+\cdots +n)^2+2\cdot(1+2+\cdots +n)(n+1)+(n+1)^2 </math>

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

<math>=1^3 +2^3 + \cdots +n^3 +2\cdot (1+2+\cdots +n)(n+1)+(n+1)^2 </math>
<math>=1^3 +2^3 + \cdots +n^3 +2 \cdot \frac{n(n+1)}{2}(n+1)+(n+1)^2 </math>
<math>=1^3 +2^3 + \cdots +n^3 +n(n+1)^2+(n+1)^2</math>
<math>=1^3 +2^3 + \cdots +n^3 +(1+n)(n+1)^2=1^3 +2^3 + \cdots +n^3+(n+1)^3</math>

וסיימנו.

'''דוגמה:'''
 
הוכח כי לכל מספר טבעי <math>n</math> מתקיים כי <math>2+4+6+\cdots +2n=n(n+1)</math>

פתרון:

עבור <math>n=1</math> אכן מתקיים <math>2=1\cdot(1+1)</math>

כעת נניח שהטענה נכונה עבור <math>n</math> ונוכיח את הטענה עבור <math>n+1</math>

<math>2+4+\cdots 2n+2(n+1)=\sum_{k=1}^{n+1}2\cdot k=\sum_{k=1}^{n}2\cdot k + 2(n+1) = </math>

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

<math>=n(n+1)+2(n+1)=(n+1)(n+2)</math>

שזה הטענה עבור <math>n+1</math> וסיימנו.

==הכללות==
===הכללה פשוטה ראשונה===
לא חייבים להתחיל מ-0, ניתן להתחיל מהטבעי הראשון עבורו הטענה נכונה.


פורמלית: אם נוכיח עבור טענה <math>P(n)</math> כי:
* הטענה מתקיימת עבור <math>n=k</math> מסוים. כלומר <math>P(k)</math> נכונה.
* לכל מספר טבעי החל מ-<math>k</math> מתקיים: '''אם''' הטענה נכונה עבורו, אז היא נכונה גם עבור המספר הבא אחריו. כלומר, <math>\forall k\leq n\in \mathbb{N}:(P(n)\rightarrow P(n+1))</math>.

אז באופן דומה הטענה <math>P(n)</math> נכונה לכל <math>n\geq k</math>.

כלומר - במקום להוכיח ידנית עבור <math>n=0</math>, ואז הטענה מתקיימת החל מ-<math>0</math> ניתן להוכיח עבור <math>n=k</math> ואז הטענה מתקיים החל מ-<math>k</math>.

====תרגיל====
הוכיחו כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>.

=====פתרון=====

עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math> .

כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math>.

נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי
<math>(1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)</math>
<math>=1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x</math>

וסיימנו.

===הכללה שנייה - אינדוקציה שלימה===

הכללה שבה יש שינוי בצעד האינדוקציה, הנקראת אינדוקציה שלמה: אם נוכיח עבור טענה <math>P(n)</math> כי:
* הטענה מתקיימת עבור <math>n=0</math>. כלומר <math>P(0)</math> נכונה.
* לכל <math>n\in \mathbb{N}</math> מתקיים: '''אם''' הטענה נכונה עבור כל המספרים עד <math>n</math>, אזי היא נכונה גם עבור <math>n+1</math>. כלומר,
<math>\forall n\in \mathbb{N}:((\forall k\leq n P(k))\Rightarrow P(n+1))</math>

אז באופן דומה הטענה <math>P(n)</math> נכונה לכל <math>n\in \mathbb{N}</math>.

כלומר -  אפשר להחליף את הצעד ממספר מסויים לבא אחריו, בצעד מכל אלו שהיו עד כה לבא אחריהם.

====תרגיל====
שאלת השוקולוד: טבלת שוקולד <math>T_n</math> היא אוסף של <math>n</math> ריבועים המחוברים בצלעות (בצורה קשירה - אם מרימים ריבוע כל הטבלה מורמת). הטבלה היא לאו דוקא מלבן, למשל יכול להיות מלבן עם עוד ריבוע אחד יוצא החוצה איפשהו.

חיתוך של הטבלה זה חיתוך אורך שלם או רוחב שלם. בידוד של הטבלה זה הבאתה לריבועים בודדים.

הוכיחו שלכל טבלה <math>T_n,n\geq 1</math> מתקיים: בעזרת <math>n-1</math> חיתוכים ניתן לבודד את הטבלה.

====פתרון=====

בסיס: עבור <math>n-1</math> אכן כן.

יהי <math>n</math>, ונניח נכונות לכל <math>k\leq n</math>. ועכשיו נקבל טבלה <math>T_{n+1}</math>. נחתוך אותה איפשהו, ונקבל שתי טבלאות: <math>T_k,T_{n+1-k}</math>. מהנחת האינדוקציה את הטבלה <math>T_k</math> ניתן לבודד בעזרת <math>k-1</math> חיתוכים, ואת <math>T_{n+1-k}</math> ניתן לבודד בעזרת <math>n+1-k-1=n-k</math> חיתוכים. ביחד בודדנו את <math>T_{n+1}</math> בעזרת <math>1+(k-1)+(n-k)=n</math> חיתוכים.

שימו לב שאין דרך ידועה לחתוך את הטבלה לריבוע בודד ועוד טבלה <math>T_n</math>, ולכן חייבים כאן אינדוקציה שלימה.

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

דוגמה מפורסמת להוכחת שגויה באינדוקציה היא הדוגמה הבאה:

טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.

"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.

עבור <math>n=1</math> אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד.

כעת נניח כל קבוצה עם <math>n</math> סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל <math>n+1</math>.

תהא <math>H=\{h_1,h_2,\dots h_n,h_{n+1}\}</math> קבוצה עם <math>n+1</math> סוסים אזי לפי הנחת האינדוקציה 
<math>H_1 =\{h_1,h_2,\dots h_n\}</math> ו-<math>H_2=\{h_2,\dots h_n,h_{n+1}\}</math> הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל <math>n</math>),
ולכן כל הסוסים ב-<math>H</math> גם כן בעלי צבע יחיד (כי יש חפיפה בין <math>H_1</math> ובין <math>H_2</math>).

חישבו איפה השגיאה (רמז: במעבר מ <math>n=1</math> ל <math>n=2</math>).