גרסה אחרונה מ־12:12, 8 בדצמבר 2019

תוכן עניינים

1 אינדוקציה מתמטית: רעיון בסיסי
2 הכללות
- 2.1 הכללה פשוטה ראשונה
- 2.2 הכללה פשוטה שנייה
  - 2.2.1 תרגיל (בד"כ נעשה בהרצאה)
  - 2.2.2 תרגיל
3 תרגילים יותר מעניינים

אינדוקציה מתמטית: רעיון בסיסי

אינדוקציה היא שיטה המאפשרת להוכיח שטענה מסוימת $P(n)$ נכונה עבור כל מספר טבעי (למשל $(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3$ ) בעזרת הסקה מן הפרט אל הכלל.

הוכחת הטענה $\forall nP(n)$ שקולה להוכחת שתי הטענות הבאות:

(בסיס האינדוקציה) הטענה מתקיימת עבור $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$ . כלומר נוכיח ש: $P(n) \to P(n+1)$

נוכיח:

$(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$

וסיימנו.

דוגמה:

הוכח כי לכל מספר טבעי $n$ מתקיים כי $2+4+6+\cdots +2n=n(n+1)$

פתרון:

עבור $n=1$ אכן מתקיים $2=1\cdot(1+1)$

כעת נניח שהטענה נכונה עבור $n$ ונוכיח את הטענה עבור $n+1$

$2+4+\cdots 2n+2(n+1)=\sum_{k=1}^{n+1}2\cdot k=\sum_{k=1}^{n}2\cdot k + 2(n+1) =$

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

$=n(n+1)+2(n+1)=(n+1)(n+2)$

שזה הטענה עבור $n+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+nx +x+nx^2 > 1+x+nx =1+ (n+1)x$

וסיימנו.

הכללה פשוטה שנייה

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

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

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

כלומר - אפשר להחליף את ההנחה שמתקיים עבור $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=\prod_{k=1}^l p_k,b=\prod_{i=1}^r q_i$ כאשר $p_k,q_i$ ראשוניים.

אזי $n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{i=1}^r q_i$ וסיימנו.

תרגיל

שאלת השוקולוד.

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

תרגיל

יהא $A$ פסוק. נגדיר בעזרת אינדוקציה פסוקים: $P_0 = A, P_n=(P_{n-1})\to A$

הוכיחו כי $P_{n}$ טאוטולוגיה כאשר $n$ אי-זוגי.

פתרון: נוכיח באינדוקציה כי לכל $n$ אי-זוגי, הפסוק $P_{n}$ הוא טאוטולוגיה. בדיקה: עבור $n=1$ , הפסוק הוא $A\to A$ . הוא אכן טאוטולוגיה.

צעד: כעת, נניח את נכונות הטענה עבור $n$ אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר $n+2$ .

מתקיים: $P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A$ נראה כי זו אכן טאוטולוגיה. ראשית, לפי ההנחה, $P_{n}\equiv T$ לכל ערך של $A$ .

אם $A=F$ , נקבל $(T\to F)\to F\equiv F\to F$ - אכן אמת.

אם $A=T$ , נקבל $(T\to T)\to T\equiv T\to T$ - אכן אמת.

וסיימנו באינדוקציה.

תרגיל

יהיו $A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n}$ מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחה $(A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j}$

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

עבור $m=1$ זה ההגדרה של כפל בין 2 מטריצות.

כעת, נניח שהטענה נכונה עבור $m$ כלשהו. נוכיח נכונות עבור $m+1$ .

$(A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j}$

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

$=\sum_{i_{m+1}=1}^n \underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j} =$

$= \underset{1\leq i_1,i_2,\dots i_m, i_{m+1} \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,i_{m+1}}(A_{m+2})_{i_{m+1},j}$

וסיימנו.

אזהרה

אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכון.

דוגמה מפורסמת להוכחת שגויה באינדוקציה היא הדוגמה הבאה:

טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.

"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.

עבור $n=1$ אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד.

כעת נניח כל קבוצה עם $n$ סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל $n+1$ .

תהא $H=\{h_1,h_2,\dots h_n,h_{n+1}\}$ קבוצה עם $n+1$ סוסים אזי לפי הנחת האינדוקציה $H_1 =\{h_1,h_2,\dots h_n\}$ ו- $H_2=\{h_2,\dots h_n,h_{n+1}\}$ הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל $n$ ), ולכן כל הסוסים ב- $H$ גם כן בעלי צבע יחיד (כי יש חפיפה בין $H_1$ ובין $H_2$ ).

חישבו איפה השגיאה (רמז: במעבר מ $n=1$ ל $n=2$ ).

@@ שורה 1: / שורה 1: @@
-=רעיון בסיסי - אינדוקציה על הטבעיים=
+חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
-בשביל להוכיח שטענה מסוימת  <math>P(n)</math> נכונה עבור כל מספר טבעי
+=אינדוקציה מתמטית: רעיון בסיסי=
-(למשל <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>) מספיק להוכיח את הבאים:
-* (בסיס האינדוקציה) הטענה מתקיימת עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים
-* (צעד האינדוקציה)'''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\Rightarrow P(n+1)</math>.
-למה זה מספיק?
+אינדוקציה היא שיטה המאפשרת להוכיח שטענה מסוימת <math>P(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>\forall nP(n)</math> שקולה להוכחת שתי הטענות הבאות:
+* (בסיס האינדוקציה) הטענה מתקיימת עבור <math>n=1</math>. כלומר <math>P(1)</math> נכון.
+* (צעד האינדוקציה) '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</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\in \mathbb{N} </math> טבעי.
 הוכחה:
-עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>
+עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>.
 כעת נראה שאם הטענה נכונה עבור <math>n</math> כלשהוא, כלומר אם מתקיים
@@ שורה 25: / שורה 28: @@
 <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^3 +2^3 + \cdots +n^3 +2\cdot (1+2+\cdots +n)(n+1)+(n+1)^2 </math>
@@ שורה 32: / שורה 35: @@
 <math>=1^3 +2^3 + \cdots +n^3 +(1+n)(n+1)^2=1^3 +2^3 + \cdots +n^3+(n+1)^3</math>
-וסיימנו
+וסיימנו.
-דוגמא נוספת:
+'''דוגמה:'''
 הוכח כי לכל מספר טבעי <math>n</math> מתקיים כי <math>2+4+6+\cdots +2n=n(n+1)</math>
@@ שורה 53: / שורה 55: @@
 שזה הטענה עבור <math>n+1</math> וסיימנו.
-==הכללות==
+=הכללות=
-===הכללה פשוטה 1===
+==הכללה פשוטה ראשונה==
-הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:
-* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
-* '''אם''' הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\Rightarrow P(n+1)</math>.
-אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>
+הכללה ישירה שבה יש שינוי רק בבסיס האינדוקציה: אם נוכיח עבור טענה <math>P(n)</math> כי:
+* הטענה מתקיימת עבור <math>n=k</math> מסוים. כלומר <math>P(k)</math> נכונה.
+* '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>.
-כלומר - במקום להוכיח עבור <math>n=1</math> ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור <math>n=k</math> ואז הטענה מתקיים החל מ-k
+אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>.
+כלומר - במקום להוכיח עבור <math>n=1</math> ואז הטענה מתקיימת החל מ-<math>1</math> ניתן להוכיח עבור <math>n=k</math> ואז הטענה מתקיים החל מ-<math>k</math>.
-דוגמא:
+'''דוגמה:'''
+הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>.
-הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>
 פתרון:
-עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math>
+עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math> .
-כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהוא, כלומר מתקיים <math>(1+x)^n > 1+nx</math>
+כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math>.
 נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי
-<math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)=   1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x </math>
+<math>(1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)</math>
+<math>=1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x</math>
+וסיימנו.
-וסיימנו
+==הכללה פשוטה שנייה==
-===הכללה פשוטה 2 ===
+הכללה שבה יש שינוי בצעד האינדוקציה, הנקראת אינדוקציה שלמה: אם נוכיח עבור טענה <math>P(n)</math> כי:
-אם נוכיח עבור טענה <math>P(n)</math> ש:
+* הטענה מתקיימת עבור <math>n=1</math>. כלומר <math>P(1)</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 1</math>
+אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq 1</math>.
 כלומר -  אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
-בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>
+בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>.
+====תרגיל (בד"כ נעשה בהרצאה)====
-דוגמא:
+כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים.
-כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים
 הוכחה:
@@ שורה 97: / שורה 99: @@
 עבור <math>n=2</math> זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.
-כעת נניח שהטענה נכונה לכל <math>1<k\leq n</math> ונוכיח עבור <math>n+1</math>
+כעת נניח שהטענה נכונה לכל <math>1<k\leq n</math> ונוכיח עבור <math>n+1</math>.
 אם <math>n+1</math> ראשוני - סיימנו כי אז הוא הפירוק של עצמו.
@@ שורה 103: / שורה 105: @@
 אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
 לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים
-<math>a=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים
+<math>a=\prod_{k=1}^l p_k,b=\prod_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים.
-ואז <math>n+1=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math>
+אזי <math>n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{i=1}^r q_i</math> וסיימנו.
-וסיימנו.
+====תרגיל====
+שאלת השוקולוד.
-== תרגילים יותר מעניינים ==
+=תרגילים יותר מעניינים=
-===תרגיל ===
+==תרגיל ==
 יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:
 <math>P_0 = A, P_n=(P_{n-1})\to A</math>
-הוכיחו כי <math>P_{n}</math>
-טואוטולוגיה כאשר <math>n</math> אי-זוגי.
-פתרון: נוכיח באינדוקציה כי לכל <math>n</math> אי-זוגי, הפסוק <math>P_{n}</math>
+הוכיחו כי <math>P_{n}</math> טאוטולוגיה כאשר <math>n</math> אי-זוגי.
-הוא טואוטולוגיה.בדיקה: עבור <math>n=1</math>, הפסוק הוא <math>A\to A</math>. הוא אכן טואוטולוגיה.
+פתרון:
+נוכיח באינדוקציה כי לכל <math>n</math> אי-זוגי, הפסוק <math>P_{n}</math>
+הוא טאוטולוגיה. בדיקה: עבור <math>n=1</math>, הפסוק הוא <math>A\to A</math>. הוא אכן טאוטולוגיה.
 צעד: כעת, נניח את נכונות הטענה עבור <math>n</math> אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר <math>n+2</math>.
-מתקיים:<math>P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A</math> נראה כי זו אכן טואוטולוגיה. ראשית, לפי ההנחה, <math>P_{n}\equiv T</math>
+מתקיים:<math>P_{n+2}=P_{n+1}\to A=(P_{n}\to A)\to A</math> נראה כי זו אכן טאוטולוגיה. ראשית, לפי ההנחה, <math>P_{n}\equiv T</math>
 לכל ערך של <math>A</math>.
-• אם <math>A=F</math>, נקבל <math>(T\to F)\to F\equiv F\to F</math>- אכן אמת.
+* אם <math>A=F</math>, נקבל <math>(T\to F)\to F\equiv F\to F</math>- אכן אמת.
-• אם <math>A=T</math>, נקבל  <math> (T\to T)\to T\equiv T\to T</math> - אכן אמת.
+* אם <math>A=T</math>, נקבל  <math> (T\to T)\to T\equiv T\to T</math> - אכן אמת.
 וסיימנו באינדוקציה.
-===תרגיל:===
+==תרגיל==
-יהיו <math>A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n}</math> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא
+יהיו <math>A_1,A_2\dots A_{m+1} \in \mathbb{F}^{n\times n}</math> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחה
 <math>(A_1A_2\cdots A_{m+1})_{i,j}=\underset{1\leq i_1,i_2,\dots i_m \leq n}{\sum}(A_1)_{i,i_1}(A_2)_{i_1,i_2}\dots (A_{m+1})_{i_m,j}</math>
 הוכחה (באינדוקציה על מספר המטריצות):
-עבור <math>m=1</math> זה ההגדרה של כפל בין 2 מטריצות
+עבור <math>m=1</math> זה ההגדרה של כפל בין 2 מטריצות.
-כעת, נניח שהטענה נכונה עבור <math>m</math> כל שהוא. נוכיח נכונות עבור <math>m+1</math>
+כעת, נניח שהטענה נכונה עבור <math>m</math> כלשהו. נוכיח נכונות עבור <math>m+1</math>.
 <math>(A_1A_2\cdots A_{m+1}A_{m+2})_{i,j}=\sum_{i_{m+1}=1}^n (A_1A_2\cdots A_{m+1})_{i,i_{m+1}}(A_{m+2})_{i_{m+1},j}</math>
@@ שורה 153: / שורה 156: @@
 ==אזהרה==
-אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכונה.
+אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכון.
-דוגמא מפורסמת להוכחת שגויה באינדוקציה היא הדוגמא הבא:
+דוגמה מפורסמת להוכחת שגויה באינדוקציה היא הדוגמה הבאה:
 טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.
@@ שורה 161: / שורה 164: @@
 "הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.
-עבור <math>n=1</math> אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד
+עבור <math>n=1</math> אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד.
-כעת נניח כל קבוצה עם <math>n</math> סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל <math>n+1</math>
+כעת נניח כל קבוצה עם <math>n</math> סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל <math>n+1</math>.
 תהא <math>H=\{h_1,h_2,\dots h_n,h_{n+1}\}</math> קבוצה עם <math>n+1</math> סוסים אזי לפי הנחת האינדוקציה
-<math>H_1 =\{h_1,h_2,\dots h_n\}</math> ו <math>H_2=\{h_2,\dots h_n,h_{n+1}\}</math> הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל <math>n</math>)
+<math>H_1 =\{h_1,h_2,\dots h_n\}</math> ו-<math>H_2=\{h_2,\dots h_n,h_{n+1}\}</math> הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל <math>n</math>),
-ולכן כל הסוסים ב <math>H</math> ג"כ בעלי צבע יחיד (כי יש חפיפה בין <math>H_1</math> ובין <math>H_2</math>.
+ולכן כל הסוסים ב-<math>H</math> גם כן בעלי צבע יחיד (כי יש חפיפה בין <math>H_1</math> ובין <math>H_2</math>).
-חישבו איפה השגיאה (רמז: במעבר מ <math>n=1</math> ל <math>n=2</math>)
+חישבו איפה השגיאה (רמז: במעבר מ <math>n=1</math> ל <math>n=2</math>).

הבדלים בין גרסאות בדף "תרגול 4 תשעז"

גרסה אחרונה מ־12:12, 8 בדצמבר 2019

תוכן עניינים

אינדוקציה מתמטית: רעיון בסיסי

הכללות

הכללה פשוטה ראשונה

הכללה פשוטה שנייה

תרגיל (בד"כ נעשה בהרצאה)

תרגיל

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

תרגיל

תרגיל

אזהרה

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים