גרסה מ־09:01, 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{ (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]

דוגמא נוספת:

עיקרון הסדר הטוב

הכללות

הכללה פשוטה1

הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה [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] ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור [math]\displaystyle{ n=k }[/math] ואז הטענה מתקיים החל מ-k

הכללה פשוטה 2

אם נוכיח עבור טענה [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 k }[/math]

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

הכללה מעמיקה

תהא [math]\displaystyle{ A }[/math] קבוצה סדורה היטב בת מניה אז אפשר לעשות שם אינדוקציה

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

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

כפל n מטריצות הפרש סימטרי של n קבוצות

@@ שורה 10: / שורה 10: @@
 למה זה מספיק?
 בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <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>n\in \mathbb{N} </math> טבעי
+הוכחה:
+עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>
+כעת נניח כי הטענה עבור <math>n</math> כלשהוא, כלומר מתקיים <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math> ונוכיח כי הטענה נכונה עבור <math>n+1</math>, כלומר
+<math>(1+2+\cdots +n+n+1)^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3</math>
+דוגמא נוספת:
+==עיקרון הסדר הטוב ==
 ==הכללות==
-===הכללה פשוטה===
+===הכללה פשוטה1===
 הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:
 * הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
@@ שורה 18: / שורה 33: @@
 אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>
+כלומר - במקום להוכיח עבור <math>n=1</math> ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור <math>n=k</math> ואז הטענה מתקיים החל מ-k
+===הכללה פשוטה 2 ===
+אם נוכיח עבור טענה <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>P(n)</math> נכונה עבור <math>n\geq k</math>
+כלומר -  אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
+בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>
 === הכללה מעמיקה ===
-תהא <math>A</math> קבוצה סדורה היטב
+תהא <math>A</math> קבוצה סדורה היטב בת מניה אז אפשר לעשות שם אינדוקציה
+הערה: אפשר לעשות אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)
+הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים.
+== תרגילים יותר מעניינים ==
+כפל n מטריצות
+הפרש סימטרי של n קבוצות