88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5: הבדלים בין גרסאות בדף
אחיה בר-און (שיחה | תרומות) אין תקציר עריכה |
אחיה בר-און (שיחה | תרומות) אין תקציר עריכה |
||
| שורה 9: | שורה 9: | ||
למה זה מספיק? | למה זה מספיק? | ||
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <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>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>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> | |||
== הכללה מעמיקה == | |||
גרסה מ־08:31, 17 ביולי 2014
רעיון בסיסי - אינדוקציה על הטבעיים
בשביל להוכיח שטענה מסוימת [math]\displaystyle{ P(n) }[/math] נכונה עבור כל מספר טבעי (למשל [math]\displaystyle{ (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3 }[/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{ 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]