הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5"
אחיה בר-און (שיחה | תרומות) (←הכללה פשוטה 1) |
אחיה בר-און (שיחה | תרומות) (←רעיון בסיסי - אינדוקציה על הטבעיים) |
||
שורה 5: | שורה 5: | ||
בשביל להוכיח שטענה מסוימת <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>n=1</math> כלומר <math>P(1)</math> מתקיים |
− | * '''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\Rightarrow P(n+1)</math>. | + | * (צעד האינדוקציה)'''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\Rightarrow P(n+1)</math>. |
למה זה מספיק? | למה זה מספיק? | ||
שורה 47: | שורה 47: | ||
נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי | נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי | ||
− | + | <math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) +1+x > 1+x+nx =1+ (n+1)x </math> | |
− | + | ||
וסיימנו | וסיימנו |
גרסה מ־11:50, 17 ביולי 2014
תוכן עניינים
רעיון בסיסי - אינדוקציה על הטבעיים
בשביל להוכיח שטענה מסוימת נכונה עבור כל מספר טבעי
(למשל
) מספיק להוכיח את הבאים:
- (בסיס האינדוקציה) הטענה מתקיימת עבור
כלומר
מתקיים
- (צעד האינדוקציה)אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר
.
למה זה מספיק?
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור כלומר
מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור
(שזה אכן כך) אז הטענה נכונה גם עבור
כלומר
. אה! אז עכשיו זה נכון עבור
אז לפי אותה טענה זה נכון גם עבור
! ומה עכשיו? אם זה נכון עבור
זה נכון עבור
. וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר
נכון לכל
דוגמא:
נוכיח באינדוקציה כי הטענה
נכונה לכל
טבעי
הוכחה:
עבור אכן מתקיים כי
כעת נניח כי הטענה עבור כלשהוא, כלומר מתקיים
ונוכיח כי הטענה נכונה עבור
, כלומר
דוגמא נוספת:
עיקרון הסדר הטוב
הכללות
הכללה פשוטה 1
הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה ש:
- הטענה מתקיימת עבור
מסוים כלומר
מתקיים
- אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר
.
אז באופן דומה הטענה נכונה נכונה עבור
כלומר - במקום להוכיח עבור ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור
ואז הטענה מתקיים החל מ-k
דוגמא:
הוכח כי לכל מתקיים
לכל
פתרון:
עבור נקבל
כי
כעת נניח כי הטענה נכונה עבור כלשהוא, כלומר מתקיים
נוכיח עבור מהנחת האינדוקציה נקבל כי
וסיימנו
הכללה פשוטה 2
אם נוכיח עבור טענה ש:
- הטענה מתקיימת עבור
מסוים כלומר
מתקיים
- אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים
(כלומר מתקיים
עבור
) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר
מתקיים).
אז באופן דומה הטענה נכונה נכונה עבור
כלומר - אפשר להחליף את ההנחה שמתקיים עבור ולהוכיח עבור
בהנחה שמתקיים עבור כל מי שקטן שווה
ולהוכיח עבור
הכללה מעמיקה
תהא קבוצה סדורה היטב בת מניה אז אפשר לעשות שם אינדוקציה
הערה: אפשר לעשות אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה) הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים.
תרגילים יותר מעניינים
כפל n מטריצות הפרש סימטרי של n קבוצות