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

תוכן עניינים

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

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

בשביל להוכיח שטענה מסוימת $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 קבוצות

@@ שורה 21: / שורה 21: @@
 כעת נניח כי הטענה עבור <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>
+<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>
 לפי הנחת האינדוקציה אפשר להמשיך הלאה

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

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

תוכן עניינים

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

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

הכללות

הכללה פשוטה 1

הכללה פשוטה 2

הכללה מעמיקה

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים