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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(רעיון בסיסי - אינדוקציה על הטבעיים)
(רעיון בסיסי - אינדוקציה על הטבעיים)
שורה 21: שורה 21:
 
כעת נניח כי הטענה עבור <math>n</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)^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>
+
<math>(1+2+\cdots +n+(n+1))^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3</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+2+\cdots +n+(n+)1)^2=(1+2+\cdots +n)^2+2\cdot(1+2+\cdots +n)(n+1)+(n+1)^2 </math>
  
 
לפי הנחת האינדוקציה אפשר להמשיך הלאה
 
לפי הנחת האינדוקציה אפשר להמשיך הלאה

גרסה מ־12:09, 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+2+\cdots +n+(n+)1)^2=(1+2+\cdots +n)^2+2\cdot(1+2+\cdots +n)(n+1)+(n+1)^2

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

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


דוגמא:

הוכח כי לכל x>0 מתקיים (1+x)^n > 1+nx לכל n\geq 2

פתרון:

עבור n=2 נקבל (1+x)^2 = 1+2x+x^2>1+2x כי x>0

כעת נניח כי הטענה נכונה עבור n כלשהוא, כלומר מתקיים (1+x)^n > 1+nx

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

וסיימנו

הכללה פשוטה 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


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

הוכחה:

עבור n=2 זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.

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

אם n+1 ראשוני - סיימנו כי אז הוא הפירוק של עצמו.

אחרת n+1 מתפרק למכפלה n+1=ab כאשר 1<a,b<n+1 לפי הנחת האינדוקציה a,b מתפרקים למכפלה של מספרים ראשוניים a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i כאשר p_k,q)i ראשוניים

ואז n=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i

וסיימנו

הכללה מעמיקה

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

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

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

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