תרגול 4 תשעז: הבדלים בין גרסאות בדף

מתוך Math-Wiki
שורה 1: שורה 1:
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].


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


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


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


דוגמא:
למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=1</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=2</math>כלומר <math>P(2)</math>. אה! אז עכשיו זה נכון עבור <math>n=2</math> אז לפי אותה טענה זה נכון גם עבור <math>n=3</math>! ומה עכשיו? אם זה נכון עבור <math>n=3</math> זה נכון עבור <math>n=4</math> . וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר <math>P(n)</math> נכון '''לכל''' <math>n</math>.
 
'''דוגמה:'''
נוכיח באינדוקציה כי הטענה <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>  
נוכיח באינדוקציה כי הטענה <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>  
נכונה לכל <math>n\in \mathbb{N} </math> טבעי
נכונה לכל <math>n\in \mathbb{N} </math> טבעי.


הוכחה:
הוכחה:


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


כעת נראה שאם הטענה נכונה עבור <math>n</math> כלשהוא, כלומר אם מתקיים  
כעת נראה שאם הטענה נכונה עבור <math>n</math> כלשהוא, כלומר אם מתקיים  
שורה 27: שורה 28:
<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+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 (1+2+\cdots +n)(n+1)+(n+1)^2 </math>
שורה 34: שורה 35:
<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>=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</math> מתקיים כי <math>2+4+6+\cdots +2n=n(n+1)</math>
שורה 55: שורה 55:
שזה הטענה עבור <math>n+1</math> וסיימנו.
שזה הטענה עבור <math>n+1</math> וסיימנו.


==הכללות==
=הכללות=
===הכללה פשוטה 1===
==הכללה פשוטה ראשונה==
הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:
* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
* '''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>.
 
אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>


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


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


דוגמא:
כלומר - במקום להוכיח עבור <math>n=1</math> ואז הטענה מתקיימת החל מ-<math>1</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>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>


שורה 74: שורה 73:
עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</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</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math>  


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


וסיימנו
וסיימנו.


===הכללה פשוטה 2 ===
==הכללה פשוטה שנייה==
אם נוכיח עבור טענה <math>P(n)</math> ש:
 
* הטענה מתקיימת עבור <math>n=1</math> מסוים כלומר <math>P(1)</math> מתקיים
הכללה שבה יש שינוי בצעד האינדוקציה, הנקראת אינדוקציה שלמה: אם נוכיח עבור טענה <math>P(n)</math> כי:
* הטענה מתקיימת עבור <math>n=1</math>. כלומר <math>P(1)</math> נכונה.
* '''אם''' הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים <math>n</math> (כלומר מתקיים <math>P(m)</math> עבור <math>m\leq n</math>) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר <math>P(n+1)</math> מתקיים).  
* '''אם''' הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים <math>n</math> (כלומר מתקיים <math>P(m)</math> עבור <math>m\leq n</math>) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר <math>P(n+1)</math> מתקיים).  


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


כלומר -  אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
כלומר -  אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>
בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>.


 
'''דוגמה:'''
דוגמא:
כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים.
כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים


הוכחה:
הוכחה:
שורה 99: שורה 98:
עבור <math>n=2</math> זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.
עבור <math>n=2</math> זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.


כעת נניח שהטענה נכונה לכל <math>1<k\leq n</math> ונוכיח עבור <math>n+1</math>
כעת נניח שהטענה נכונה לכל <math>1<k\leq n</math> ונוכיח עבור <math>n+1</math>.


אם <math>n+1</math> ראשוני - סיימנו כי אז הוא הפירוק של עצמו.
אם <math>n+1</math> ראשוני - סיימנו כי אז הוא הפירוק של עצמו.
שורה 105: שורה 104:
אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים  
לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים  
<math>a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים
<math>a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים.


ואז <math>n+1=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math>
אזי <math>n+1=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math> וסיימנו.


וסיימנו.
=תרגילים יותר מעניינים=
 
==תרגיל ==
== תרגילים יותר מעניינים ==
===תרגיל ===
יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:  
יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:  
<math>P_0 = A, P_n=(P_{n-1})\to A</math>
<math>P_0 = A, P_n=(P_{n-1})\to A</math>
הוכיחו כי <math>P_{n}</math>
טואוטולוגיה כאשר <math>n</math> אי-זוגי.


פתרון: נוכיח באינדוקציה כי לכל <math>n</math> אי-זוגי, הפסוק <math>P_{n}</math>
הוכיחו כי <math>P_{n}</math> טאוטולוגיה כאשר <math>n</math> אי-זוגי.
הוא טואוטולוגיה.בדיקה: עבור <math>n=1</math>, הפסוק הוא <math>A\to A</math>. הוא אכן טואוטולוגיה.


פתרון:
נוכיח באינדוקציה כי לכל <math>n</math> אי-זוגי, הפסוק <math>P_{n}</math>
הוא טאוטולוגיה. בדיקה: עבור <math>n=1</math>, הפסוק הוא <math>A\to A</math>. הוא אכן טאוטולוגיה.


צעד: כעת, נניח את נכונות הטענה עבור <math>n</math> אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר <math>n+2</math>.  
צעד: כעת, נניח את נכונות הטענה עבור <math>n</math> אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר <math>n+2</math>.  


מתקיים:<math>P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A</math> נראה כי זו אכן טואוטולוגיה. ראשית, לפי ההנחה, <math>P_{n}\equiv T</math>
מתקיים:<math>P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A</math> נראה כי זו אכן טאוטולוגיה. ראשית, לפי ההנחה, <math>P_{n}\equiv T</math>
לכל ערך של <math>A</math>.
לכל ערך של <math>A</math>.


אם <math>A=F</math>, נקבל <math>(T\to F)\to F\equiv F\to F</math>- אכן אמת.
* אם <math>A=F</math>, נקבל <math>(T\to F)\to F\equiv F\to F</math>- אכן אמת.


אם <math>A=T</math>, נקבל  <math> (T\to T)\to T\equiv T\to T</math> - אכן אמת.
* אם <math>A=T</math>, נקבל  <math> (T\to T)\to T\equiv T\to T</math> - אכן אמת.


וסיימנו באינדוקציה.
וסיימנו באינדוקציה.


===תרגיל:===
==תרגיל==


יהיו <math>A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n}</math> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא
יהיו <math>A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n}</math> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחה
<math>(A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j}</math>
<math>(A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j}</math>


הוכחה (באינדוקציה על מספר המטריצות):
הוכחה (באינדוקציה על מספר המטריצות):


עבור <math>m=1</math> זה ההגדרה של כפל בין 2 מטריצות
עבור <math>m=1</math> זה ההגדרה של כפל בין 2 מטריצות.


כעת, נניח שהטענה נכונה עבור <math>m</math> כל שהוא. נוכיח נכונות עבור <math>m+1</math>
כעת, נניח שהטענה נכונה עבור <math>m</math> כלשהו. נוכיח נכונות עבור <math>m+1</math>.


<math>(A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j}</math>
<math>(A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j}</math>
שורה 155: שורה 152:


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


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


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


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


כעת נניח כל קבוצה עם <math>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=\{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_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>H</math> גם כן בעלי צבע יחיד (כי יש חפיפה בין <math>H_1</math> ובין <math>H_2</math>).
 


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

גרסה מ־02:34, 11 בנובמבר 2017

חזרה לדף מערכי התרגול.

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

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

הוכחת הטענה [math]\displaystyle{ \forall nP(n) }[/math] שקולה להוכחת שתי הטענות הבאות:

  • (בסיס האינדוקציה) הטענה מתקיימת עבור [math]\displaystyle{ n=1 }[/math]. כלומר [math]\displaystyle{ P(1) }[/math] נכון.
  • (צעד האינדוקציה) אם הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר [math]\displaystyle{ P(n)\rightarrow P(n+1) }[/math].

למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור [math]\displaystyle{ n=1 }[/math] כלומר [math]\displaystyle{ P(1) }[/math] מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור [math]\displaystyle{ n=1 }[/math] (שזה אכן כך) אז הטענה נכונה גם עבור [math]\displaystyle{ n=2 }[/math]כלומר [math]\displaystyle{ P(2) }[/math]. אה! אז עכשיו זה נכון עבור [math]\displaystyle{ n=2 }[/math] אז לפי אותה טענה זה נכון גם עבור [math]\displaystyle{ n=3 }[/math]! ומה עכשיו? אם זה נכון עבור [math]\displaystyle{ n=3 }[/math] זה נכון עבור [math]\displaystyle{ n=4 }[/math] . וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר [math]\displaystyle{ P(n) }[/math] נכון לכל [math]\displaystyle{ n }[/math].

דוגמה: נוכיח באינדוקציה כי הטענה [math]\displaystyle{ (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3 }[/math] נכונה לכל [math]\displaystyle{ n\in \mathbb{N} }[/math] טבעי.

הוכחה:

עבור [math]\displaystyle{ n=1 }[/math] אכן מתקיים כי [math]\displaystyle{ 1^2=1^3 }[/math].

כעת נראה שאם הטענה נכונה עבור [math]\displaystyle{ n }[/math] כלשהוא, כלומר אם מתקיים [math]\displaystyle{ (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3 }[/math] אזי הטענה נכונה עבור [math]\displaystyle{ n+1 }[/math], כלומר [math]\displaystyle{ (1+2+\cdots +n+(n+1))^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3 }[/math]. כלומר נוכיח ש: [math]\displaystyle{ P(n) \to P(n+1) }[/math]

נוכיח:

[math]\displaystyle{ (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]\displaystyle{ =1^3 +2^3 + \cdots +n^3 +2\cdot (1+2+\cdots +n)(n+1)+(n+1)^2 }[/math] [math]\displaystyle{ =1^3 +2^3 + \cdots +n^3 +2 \cdot \frac{n(n+1)}{2}(n+1)+(n+1)^2 }[/math] [math]\displaystyle{ =1^3 +2^3 + \cdots +n^3 +n(n+1)^2+(n+1)^2 }[/math] [math]\displaystyle{ =1^3 +2^3 + \cdots +n^3 +(1+n)(n+1)^2=1^3 +2^3 + \cdots +n^3+(n+1)^3 }[/math]

וסיימנו.

דוגמה:

הוכח כי לכל מספר טבעי [math]\displaystyle{ n }[/math] מתקיים כי [math]\displaystyle{ 2+4+6+\cdots +2n=n(n+1) }[/math]

פתרון:

עבור [math]\displaystyle{ n=1 }[/math] אכן מתקיים [math]\displaystyle{ 2=1\cdot(1+1) }[/math]

כעת נניח שהטענה נכונה עבור [math]\displaystyle{ n }[/math] ונוכיח את הטענה עבור [math]\displaystyle{ n+1 }[/math]

[math]\displaystyle{ 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]\displaystyle{ =n(n+1)+2(n+1)=(n+1)(n+2) }[/math]

שזה הטענה עבור [math]\displaystyle{ n+1 }[/math] וסיימנו.

הכללות

הכללה פשוטה ראשונה

הכללה ישירה שבה יש שינוי רק בבסיס האינדוקציה: אם נוכיח עבור טענה [math]\displaystyle{ P(n) }[/math] כי:

  • הטענה מתקיימת עבור [math]\displaystyle{ n=k }[/math] מסוים. כלומר [math]\displaystyle{ P(k) }[/math] נכונה.
  • אם הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר [math]\displaystyle{ P(n)\rightarrow P(n+1) }[/math].

אז באופן דומה הטענה נכונה [math]\displaystyle{ P(n) }[/math] נכונה עבור [math]\displaystyle{ n\geq k }[/math].

כלומר - במקום להוכיח עבור [math]\displaystyle{ n=1 }[/math] ואז הטענה מתקיימת החל מ-[math]\displaystyle{ 1 }[/math] ניתן להוכיח עבור [math]\displaystyle{ n=k }[/math] ואז הטענה מתקיים החל מ-[math]\displaystyle{ k }[/math].

דוגמה: הוכח כי לכל [math]\displaystyle{ x\gt 0 }[/math] מתקיים [math]\displaystyle{ (1+x)^n \gt 1+nx }[/math] לכל [math]\displaystyle{ n\geq 2 }[/math]

פתרון:

עבור [math]\displaystyle{ n=2 }[/math] נקבל [math]\displaystyle{ (1+x)^2 = 1+2x+x^2\gt 1+2x }[/math] כי [math]\displaystyle{ x\gt 0 }[/math]

כעת נניח כי הטענה נכונה עבור [math]\displaystyle{ n }[/math] כלשהו, כלומר מתקיים [math]\displaystyle{ (1+x)^n \gt 1+nx }[/math]

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

וסיימנו.

הכללה פשוטה שנייה

הכללה שבה יש שינוי בצעד האינדוקציה, הנקראת אינדוקציה שלמה: אם נוכיח עבור טענה [math]\displaystyle{ P(n) }[/math] כי:

  • הטענה מתקיימת עבור [math]\displaystyle{ n=1 }[/math]. כלומר [math]\displaystyle{ P(1) }[/math] נכונה.
  • אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים [math]\displaystyle{ n }[/math] (כלומר מתקיים [math]\displaystyle{ P(m) }[/math] עבור [math]\displaystyle{ m\leq n }[/math]) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר [math]\displaystyle{ P(n+1) }[/math] מתקיים).

אז באופן דומה הטענה נכונה [math]\displaystyle{ P(n) }[/math] נכונה עבור [math]\displaystyle{ n\geq 1 }[/math].

כלומר - אפשר להחליף את ההנחה שמתקיים עבור [math]\displaystyle{ n }[/math] ולהוכיח עבור [math]\displaystyle{ n+1 }[/math] בהנחה שמתקיים עבור כל מי שקטן שווה [math]\displaystyle{ n }[/math] ולהוכיח עבור [math]\displaystyle{ n+1 }[/math].

דוגמה: כל מספר טבעי [math]\displaystyle{ 1\lt n }[/math] ניתן להציגו כמכפלה של מספרים ראשוניים.

הוכחה:

עבור [math]\displaystyle{ n=2 }[/math] זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.

כעת נניח שהטענה נכונה לכל [math]\displaystyle{ 1\lt k\leq n }[/math] ונוכיח עבור [math]\displaystyle{ n+1 }[/math].

אם [math]\displaystyle{ n+1 }[/math] ראשוני - סיימנו כי אז הוא הפירוק של עצמו.

אחרת [math]\displaystyle{ n+1 }[/math] מתפרק למכפלה [math]\displaystyle{ n+1=ab }[/math] כאשר [math]\displaystyle{ 1\lt a,b\lt n+1 }[/math] לפי הנחת האינדוקציה [math]\displaystyle{ a,b }[/math] מתפרקים למכפלה של מספרים ראשוניים [math]\displaystyle{ a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i }[/math] כאשר [math]\displaystyle{ p_k,q_i }[/math] ראשוניים.

אזי [math]\displaystyle{ n+1=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i }[/math] וסיימנו.

תרגילים יותר מעניינים

תרגיל

יהא [math]\displaystyle{ A }[/math] פסוק. נגדיר בעזרת אינדוקציה פסוקים: [math]\displaystyle{ P_0 = A, P_n=(P_{n-1})\to A }[/math]

הוכיחו כי [math]\displaystyle{ P_{n} }[/math] טאוטולוגיה כאשר [math]\displaystyle{ n }[/math] אי-זוגי.

פתרון: נוכיח באינדוקציה כי לכל [math]\displaystyle{ n }[/math] אי-זוגי, הפסוק [math]\displaystyle{ P_{n} }[/math] הוא טאוטולוגיה. בדיקה: עבור [math]\displaystyle{ n=1 }[/math], הפסוק הוא [math]\displaystyle{ A\to A }[/math]. הוא אכן טאוטולוגיה.

צעד: כעת, נניח את נכונות הטענה עבור [math]\displaystyle{ n }[/math] אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר [math]\displaystyle{ n+2 }[/math].

מתקיים:[math]\displaystyle{ P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A }[/math] נראה כי זו אכן טאוטולוגיה. ראשית, לפי ההנחה, [math]\displaystyle{ P_{n}\equiv T }[/math] לכל ערך של [math]\displaystyle{ A }[/math].

  • אם [math]\displaystyle{ A=F }[/math], נקבל [math]\displaystyle{ (T\to F)\to F\equiv F\to F }[/math]- אכן אמת.
  • אם [math]\displaystyle{ A=T }[/math], נקבל [math]\displaystyle{ (T\to T)\to T\equiv T\to T }[/math] - אכן אמת.

וסיימנו באינדוקציה.

תרגיל

יהיו [math]\displaystyle{ A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n} }[/math] מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחה [math]\displaystyle{ (A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j} }[/math]

הוכחה (באינדוקציה על מספר המטריצות):

עבור [math]\displaystyle{ m=1 }[/math] זה ההגדרה של כפל בין 2 מטריצות.

כעת, נניח שהטענה נכונה עבור [math]\displaystyle{ m }[/math] כלשהו. נוכיח נכונות עבור [math]\displaystyle{ m+1 }[/math].

[math]\displaystyle{ (A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j} }[/math]

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

[math]\displaystyle{ =\sum_{i_{m+1}=1}^n \underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j} = }[/math]

[math]\displaystyle{ = \underset{1\leq i_1,i_2,\dots i_m, i_{m+1} \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j} }[/math]

וסיימנו.

אזהרה

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

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

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

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

עבור [math]\displaystyle{ n=1 }[/math] אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד.

כעת נניח כל קבוצה עם [math]\displaystyle{ n }[/math] סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל [math]\displaystyle{ n+1 }[/math].

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

חישבו איפה השגיאה (רמז: במעבר מ [math]\displaystyle{ n=1 }[/math] ל [math]\displaystyle{ n=2 }[/math]).