הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏הכללות)
(←‏רעיון בסיסי - אינדוקציה על הטבעיים)
שורה 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>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>P(n)</math> ש:
 
* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
 
* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
שורה 18: שורה 33:
  
 
אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>
 
אז באופן דומה הטענה נכונה <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 קבוצות

גרסה מ־09:01, 17 ביולי 2014

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

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

בשביל להוכיח שטענה מסוימת P(n) נכונה עבור כל מספר טבעי (למשל (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3) מספיק להוכיח את הבאים:

  • הטענה מתקיימת עבור n=1 כלומר P(1) מתקיים
  • אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר P(n)\Rightarrow P(n+1).

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

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

הוכחה:

עבור n=1 אכן מתקיים כי 1^2=1^3

כעת נניח כי הטענה עבור n כלשהוא, כלומר מתקיים (1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3 ונוכיח כי הטענה נכונה עבור n+1, כלומר (1+2+\cdots +n+n+1)^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3

דוגמא נוספת:

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

הכללות

הכללה פשוטה1

הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה P(n) ש:

  • הטענה מתקיימת עבור n=k מסוים כלומר P(k) מתקיים
  • אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר P(n)\Rightarrow P(n+1).

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

כלומר - במקום להוכיח עבור n=1 ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור n=k ואז הטענה מתקיים החל מ-k

הכללה פשוטה 2

אם נוכיח עבור טענה P(n) ש:

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

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

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


הכללה מעמיקה

תהא A קבוצה סדורה היטב בת מניה אז אפשר לעשות שם אינדוקציה

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

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

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

מקור: https://math-wiki.com/index.php?title=88-195_בדידה_לתיכוניסטים_תשעא/מערך_שיעור/שיעור_1.5&oldid=42536