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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(תרגילים יותר מעניינים)
(לפעמים כדאי להניח הנחות חזקות יותר)
(40 גרסאות ביניים של 6 משתמשים אינן מוצגות)
שורה 19: שורה 19:
 
עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>  
 
עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>  
  
כעת נניח כי הטענה עבור <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>P(n) \to P(n+1)</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>
  
 
לפי הנחת האינדוקציה אפשר להמשיך הלאה
 
לפי הנחת האינדוקציה אפשר להמשיך הלאה
שורה 54: שורה 54:
  
 
שזה הטענה עבור <math>n+1</math> וסיימנו.
 
שזה הטענה עבור <math>n+1</math> וסיימנו.
 +
=== לפעמים כדאי להניח הנחות חזקות יותר ===
 +
תרגיל:
  
==עיקרון הסדר הטוב ==
+
נגדיר <math>a_0 =0 , a_{n+1}=a_n^2 +1/4</math>.
  
הגדרה:
+
הוכח כי לכל n מתקיים <math>a_n<1</math>
  
תהא <math>A</math> קבוצה עם יחס סדר חלקי <math>R</math> על <math>A</math>.
+
פתרון: נוכיח משהו יותר חזק - לכל n מתקיים <math>a_n<1/2</math>
  
<math>R</math> יקרא סדר טוב אם לכל <math>\emptyset \neq B\subseteq A</math> קיים איבר מינימום/הכי קטן/ראשון ב <math>B</math>.
+
אכן: עבור <math>a_0</math> זה מתקיים. כעת נניח שנכון עבור n ונראה עבור n+1
  
מינוח: נאמר כי <math>A</math> סדורה היטב.
+
<math>a_{n+1}=a_n^2+1/4<(1/2)^2+1/4 =1/2</math>
  
דוגמא (אינטואיטיבית):
+
==סדר טוב - העשרה מתקדמת ביותר, לא להעביר לשנה א ==
  
נסתכל על <math>\mathbb{N}</math> קבוצת הטבעיים עם יחס הסדר "קטן שווה" הסטנדרטי.
+
הגדרה: יהי <math>R</math> יחס סדר חלקי על קבוצה <math>A</math>.
  
אזי אכן מתקיים כי לכל קבוצה לא ריקה של טבעיים קיים איבר מינימום בקבוצה.
+
<math>R</math> יקרא '''סדר טוב''' אם לכל <math>\emptyset \neq B\subseteq A</math> קיים איבר מינימום/הכי קטן/ראשון ב <math>B</math>.
  
 +
מינוח: נאמר כי <math>A</math> '''סדורה היטב'''.
 +
 +
דוגמא: הקס"ח <math>(\{1,2,3\},\le)</math> היא סדורה היטב - תתי הקבוצות הלא ריקות שלה הן <math>\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}</math> והאיבר הראשון בכל תת קבוצה הוא בהתאמה <math>1,2,3,1,2,1,1</math>.
 +
 +
 +
 +
===עקרון הסדר הטוב===
 +
נסתכל על <math>(\mathbb{N},\le)</math> - קבוצת הטבעיים עם יחס הסדר "קטן שווה" הסטנדרטי.
 +
 +
אינטואיטיבית, אכן מתקיים כי לכל קבוצה לא ריקה של טבעיים קיים איבר ראשון - "אם 1 שם, הוא הקטן ביותר; אם 2 שם, הוא הקטן ביותר; ''ממשיכים כך'' עד שמגיעים לאיבר כלשהו (כי הקבוצה לא ריקה), והוא הקטן ביותר".
 +
 +
פורמלית, טענה זו, הנקראת '''עקרון הסדר הטוב''', והיא '''שקולה''' לטענת (/אקסיומת) האינדוקציה.
  
דוגמא נוספת:
 
  
ניתן להגדיר אל <math>\mathbb{Q}_+</math> יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)
+
דוגמא נוספת: ניתן להגדיר אל <math>\mathbb{Q}_+</math> יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)
  
 
[[קובץ:NutualSquareEqNutural.jpeg]]
 
[[קובץ:NutualSquareEqNutural.jpeg]]
שורה 84: שורה 97:
  
  
===עיקרון הסדר הטוב===
+
===משפט הסדר הטוב===
עיקרון הסדר הטוב הוא פשוט הטענה שלכל קבוצה <math>A</math> קיים סדר טוב
+
משפט הסדר הטוב קובע שלכל קבוצה <math>A</math> קיים סדר טוב.
 +
 
 +
 
 +
תרגיל:
 +
 
 +
תהא <math>A</math> קבוצה בת מנייה. הוכח כי ניתן לסדר אותה היטב (בהינתן עקרון הסדר הטוב).
 +
 
 +
פתרון:
 +
 
 +
לפי הנתון קיימת פונקציה חח"ע ועל <math>f:A\to \mathbb{N} </math>.
 +
נגדיר את היחס הבא על <math>A</math> כך: <math>x\leq y \iff f(x)\leq f(y) </math>. זהו יחס סדר (השתכנעו!).
 +
בנוסף, <math>A</math> סדורה היטב על ידו: תהא <math>B\subseteq A</math> תת קבוצה לא ריקה. אזי <math>f(B)\subseteq\mathbb{N}</math> תת קבוצה לא ריקה ולכן קיים בה איבר מינימום נסמנו <math>n</math>. בדקו כי
 +
<math>f^{-1}(n)\in B</math> איבר מינימום.
  
 
==הכללות==
 
==הכללות==
שורה 104: שורה 129:
 
פתרון:
 
פתרון:
  
עבור <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>n</math> כלשהוא, כלומר מתקיים <math>(1+x)^n > 1+nx</math>  
 
כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהוא, כלומר מתקיים <math>(1+x)^n > 1+nx</math>  
  
 
נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי
 
נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי
<math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) +1+x > 1+x+nx =1+ (n+1)x </math>
+
<math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)\stackrel{*}{>}(1+nx) (1+x)=  1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x </math>
 +
 
 +
כאשר המעבר <math>*</math> נובע מכך ש- <math>x>0</math>.
  
 
וסיימנו
 
וסיימנו
שורה 118: שורה 145:
 
* '''אם''' הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים <math>n</math> (כלומר מתקיים <math>P(m)</math> עבור <math>m\leq n</math>) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר <math>P(n+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>P(n)</math> נכונה עבור <math>n\geq 1</math>
  
 
כלומר -  אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
 
כלומר -  אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
שורה 137: שורה 164:
 
אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
 
אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math>
 
לפי הנחת האינדוקציה <math>a,b</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=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים
  
ואז <math>n=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math>
+
ואז <math>n+1=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math>
  
 
וסיימנו
 
וסיימנו
  
 
=== הכללה מעמיקה ===
 
=== הכללה מעמיקה ===
תהא <math>A</math> קבוצה סדורה היטב (נסמן את היחס שלה ב<math>\leq</math>) בת מניה אז ניתן להוכיח שטענה <math>P</math> מתקיימת לכל <math>a\in A</math> ע"י הוכחת הטענה הבא:
+
תהא <math>A</math> קבוצה סדורה היטב (נסמן את היחס שלה ב<math>\leq</math>) אזי:
* '''אם''' הטענה <math>P </math>  נכונה עבור <math>m<n</math> אז הטענה נכונה עבור <math>n</math>.
+
* '''אם''' <math>\forall n ([\forall m<n P(m)] \to P(n))</math>
 +
*אז <math>P</math> מתקיימת לכל <math>a\in A</math>
 +
  
  
שורה 151: שורה 180:
  
 
נניח בשלילה כי הטענה <math>P</math> לא מתקיימת לכל <math>a\in A</math>  
 
נניח בשלילה כי הטענה <math>P</math> לא מתקיימת לכל <math>a\in A</math>  
אזי נגדיר <math>D:=\{a\in A | P(a)=FALSE \}</math> - קבוצת כל האיברים ב <math>A</math> שעבורם הטענה אינה נכונה.
+
אזי נגדיר <math>D:=\{a\in A | P(a)=FALSE \}</math> - קבוצת כל האיברים ב <math>A</math> שעבורם הטענה אינה נכונה. מהנחת השלילה <math>D\neq \emptyset</math>.
 
   
 
   
 
כיוון ש <math>A</math> סדורה היטב אזי קיים ב <math>D</math> מינימום, נסמנו <math>d</math>. לפי הגדרת מינימום והגדרת <math>D</math> נובע כי לכל <math>m<d</math> הטענה נכונה (אם היה <math>m<d</math> שהטענה לא נכונה לגביו אזי הוא היה בקבוצה <math>D</math> ואז זה היה סתירה לכך ש <math>d</math> מינימום של קבוצה זאת).
 
כיוון ש <math>A</math> סדורה היטב אזי קיים ב <math>D</math> מינימום, נסמנו <math>d</math>. לפי הגדרת מינימום והגדרת <math>D</math> נובע כי לכל <math>m<d</math> הטענה נכונה (אם היה <math>m<d</math> שהטענה לא נכונה לגביו אזי הוא היה בקבוצה <math>D</math> ואז זה היה סתירה לכך ש <math>d</math> מינימום של קבוצה זאת).
שורה 160: שורה 189:
  
 
הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)
 
הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)
 
הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים.
 
  
 
== תרגילים יותר מעניינים ==
 
== תרגילים יותר מעניינים ==
 +
===תרגיל ===
 +
יהא <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>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>A</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_1,A_2,\dots A_n </math> קבוצות אזי <math>A_1 \triangle A_2 \triangle \dots  \triangle A_n =\{x| x \; \; \text{in odd number of sets} \}</math>
 +
 +
הוכחה:
 +
 +
עבור <math>n=2</math> זה נכון כי הפרש סימטרי של 2 קבוצות זה כל ה <math>x</math> - ים שנמצאים או בראשונה בלבד או בשניה בלבד.
 +
 +
נניח כי הטענה נכונה עבור <math>n</math> קבוצות. נוכיח עבור <math>n+1</math> קבוצות:
 +
 +
<math>A_1 \triangle A_2 \triangle \dots  \triangle A_n \triangle A_{n+1} = B\cup C </math>
 +
כאשר <math>B=\{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\backslash A_{n+1} \} = \{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \land x\not\in A_{n+1} \}
 +
, \; \\ C= \{ x \; | \; x \in A_{n+1} \backslash (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \} = \{x \; | \; x \in A_{n+1} \land x\not\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\}</math>
 +
 +
לפי הנחת האינדוקציה מתקיים <math>A_1 \triangle A_2 \triangle \dots  \triangle A_n =\{x| x \; \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \}</math> ולכן ניתן להמשיך כך
 +
 +
<math>B\cup C = \{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \; \land \; x\not\in A_{n+1}\} \cup \{x \; | \; x \in A_{n+1} \; \land \; x\not\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\} = </math>
 +
 +
<math>\{x \; | \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \; \land \; x\not\in A_{n+1} \} \cup \{x \; | \; x \in A_{n+1} \; \land \; x\not\in \text{in odd number of sets from}\; A_1,A_2\dots A_n \}  =  </math>
 +
 +
<math>\{x \; | x\not\in A_{n+1} \; \land \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \} \cup \{x \; | \; x \in A_{n+1} \; \land \; x \in \text{in even number of sets from}\; A_1,A_2\dots A_n \}=</math>
 +
 +
<math>\{x \; | \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n, A_{n+1} \}</math>
 +
 +
 +
 +
לכן, הטענה נכונה גם עבור <math>n+1</math> וסיימנו
 +
 +
===תרגיל:===
 +
הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע)  בן <math>n \geq 3</math> צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)
 +
ושיש בשילוש <math>n-3</math> אלכסונים.
 +
 +
פתרון:
 +
עבור <math>n=3</math>: מצולע קמור בן 3 צלעות חייב להיות משולש (ייתכן בעיוות כלשהוא) ולכן הוא ניתן לשילוש ע"י
 +
<math>n-3=0</math> אלכסונים.
 +
 +
כעת נניח שהטענה נכונה עבור כל מצולע קמור בן <math>3\leq k \leq n</math> ונוכיח את הטענה עבור מצלוע קמור בן <math>n+1</math> צלעות (כלומר שכל מצולע קמור בן <math>n+1</math> ניתן לשילוש עם <math>(n+1)-3</math> אלכסונים). יהא מצולע קמור <math>M</math> בן <math>n+1</math> צלעות. נמתח קו בין שני קודקודים שלו. כעת המצולע שהתחלנו איתו התחלק לשני מצולעים קמורים, נסמנם <math>M_1,M_2</math>. נסמן את מספר הצלעות של <math>M_1</math> ב <math>k</math> (כלומר יש לו <math>k-1</math> צלעות משותפות עם <math>M</math> + הצלע שהוספנו. מספר הצלעות של <math>M</math> הוא <math>n+1</math> ולכן מספר הצלעות המשותפות בין <math>M</math> ל <math>M_2</math> הוא
 +
<math>n+1-(k-1)=n-k+2</math> ולכן מספר הצלעות של <math>M_2</math> הוא <math>n-k+3</math>.
 +
כיוון ש <math>3\leq k,n-k+3\leq n+1</math> ניתן להפעיל את הנחת האינדוקציה על <math>M_1,M_2</math> ולהסיק כי <math>M_1,M_2</math> ניתן לשילוש ע"י <math>k-3,n-k+3 - 3</math> אלכסונים.
 +
צירוף השילושים של <math>M_1,M_2</math> יתן שילוש של <math>M</math> עם <math>(k-3) + (n-k)+1=(n+1)-3 </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</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>
 +
 +
לפי הנחת האינדוקציה נמשיך:
 +
 +
<math>=\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} = </math>
 +
 +
<math> = \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}</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</math> ג"כ בעלי צבע יחיד (כי יש חפיפה בין <math>H_1</math> ובין <math>H_2</math>.
  
תרגיל:
 
  
יהיו <math>A_1,A_2\dots A_m \in \mathbb{F}^{n\times n}</math> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא
+
חישבו איפה השגיאה (רמז: במעבר מ <math>n=1</math> ל <math>n=2</math>)
כפל n מטריצות
+
הפרש סימטרי של n קבוצות
+

גרסה מ־09:18, 15 ביולי 2019

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

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

בשביל להוכיח שטענה מסוימת 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. כלומר נוכיח ש: 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 וסיימנו.

לפעמים כדאי להניח הנחות חזקות יותר

תרגיל:

נגדיר a_0 =0 , a_{n+1}=a_n^2 +1/4.

הוכח כי לכל n מתקיים a_n<1

פתרון: נוכיח משהו יותר חזק - לכל n מתקיים a_n<1/2

אכן: עבור a_0 זה מתקיים. כעת נניח שנכון עבור n ונראה עבור n+1

a_{n+1}=a_n^2+1/4<(1/2)^2+1/4 =1/2

סדר טוב - העשרה מתקדמת ביותר, לא להעביר לשנה א

הגדרה: יהי R יחס סדר חלקי על קבוצה A.

R יקרא סדר טוב אם לכל \emptyset \neq B\subseteq A קיים איבר מינימום/הכי קטן/ראשון ב B.

מינוח: נאמר כי A סדורה היטב.

דוגמא: הקס"ח (\{1,2,3\},\le) היא סדורה היטב - תתי הקבוצות הלא ריקות שלה הן \{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\} והאיבר הראשון בכל תת קבוצה הוא בהתאמה 1,2,3,1,2,1,1.


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

נסתכל על (\mathbb{N},\le) - קבוצת הטבעיים עם יחס הסדר "קטן שווה" הסטנדרטי.

אינטואיטיבית, אכן מתקיים כי לכל קבוצה לא ריקה של טבעיים קיים איבר ראשון - "אם 1 שם, הוא הקטן ביותר; אם 2 שם, הוא הקטן ביותר; ממשיכים כך עד שמגיעים לאיבר כלשהו (כי הקבוצה לא ריקה), והוא הקטן ביותר".

פורמלית, טענה זו, הנקראת עקרון הסדר הטוב, והיא שקולה לטענת (/אקסיומת) האינדוקציה.


דוגמא נוספת: ניתן להגדיר אל \mathbb{Q}_+ יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)

NutualSquareEqNutural.jpeg

התבוננו והשתכנעו שזה גם סדר טוב.

הערה: זה בניגוד לסדר "קטן שווה" הרגיל על השברים שאינו סדר טוב כי לקבוצה \{x\in \mathbb{Q}_+ | \sqrt{2}<x \} אין איבר מינימום.


משפט הסדר הטוב

משפט הסדר הטוב קובע שלכל קבוצה A קיים סדר טוב.


תרגיל:

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

פתרון:

לפי הנתון קיימת פונקציה חח"ע ועל f:A\to \mathbb{N} . נגדיר את היחס הבא על A כך: x\leq y \iff f(x)\leq f(y) . זהו יחס סדר (השתכנעו!). בנוסף, A סדורה היטב על ידו: תהא B\subseteq A תת קבוצה לא ריקה. אזי f(B)\subseteq\mathbb{N} תת קבוצה לא ריקה ולכן קיים בה איבר מינימום נסמנו n. בדקו כי f^{-1}(n)\in B איבר מינימום.

הכללות

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

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

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

כאשר המעבר * נובע מכך ש- x>0.

וסיימנו

הכללה פשוטה 2

אם נוכיח עבור טענה 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=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i כאשר p_k,q_i ראשוניים

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

וסיימנו

הכללה מעמיקה

תהא A קבוצה סדורה היטב (נסמן את היחס שלה ב\leq) אזי:

  • אם \forall n ([\forall m<n P(m)] \to P(n))
  • אז P מתקיימת לכל a\in A


למה זה עובד?

נניח בשלילה כי הטענה P לא מתקיימת לכל a\in A אזי נגדיר D:=\{a\in A | P(a)=FALSE \} - קבוצת כל האיברים ב A שעבורם הטענה אינה נכונה. מהנחת השלילה D\neq \emptyset.

כיוון ש A סדורה היטב אזי קיים ב D מינימום, נסמנו d. לפי הגדרת מינימום והגדרת D נובע כי לכל m<d הטענה נכונה (אם היה m<d שהטענה לא נכונה לגביו אזי הוא היה בקבוצה D ואז זה היה סתירה לכך ש d מינימום של קבוצה זאת).

אבל אם זה כך אז לפי הטענה שמוכיחים זה גורר כי d כן מתקיים. סתירה. ולכן הטענה נכונה לכל a\in A


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

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

תרגיל

יהא 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_n קבוצות אזי A_1 \triangle A_2 \triangle \dots  \triangle A_n =\{x| x \; \; \text{in odd number of sets} \}

הוכחה:

עבור n=2 זה נכון כי הפרש סימטרי של 2 קבוצות זה כל ה x - ים שנמצאים או בראשונה בלבד או בשניה בלבד.

נניח כי הטענה נכונה עבור n קבוצות. נוכיח עבור n+1 קבוצות:

A_1 \triangle A_2 \triangle \dots  \triangle A_n \triangle A_{n+1} = B\cup C כאשר עיבוד הנוסחה נכשל (שגיאת תחביר): B=\{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots \triangle A_n )\backslash A_{n+1} \} = \{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots \triangle A_n ) \land x\not\in A_{n+1} \} , \; \\ C= \{ x \; | \; x \in A_{n+1} \backslash (A_1 \triangle A_2 \triangle \dots \triangle A_n ) \} = \{x \; | \; x \in A_{n+1} \land x\not\in (A_1 \triangle A_2 \triangle \dots \triangle A_n )\}


לפי הנחת האינדוקציה מתקיים A_1 \triangle A_2 \triangle \dots  \triangle A_n =\{x| x \; \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \} ולכן ניתן להמשיך כך

B\cup C = \{x \; | \; x\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n ) \; \land \; x\not\in A_{n+1}\} \cup \{x \; | \; x \in A_{n+1} \; \land \; x\not\in (A_1 \triangle A_2 \triangle \dots  \triangle A_n )\} =

\{x \; | \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \; \land \; x\not\in A_{n+1} \} \cup \{x \; | \; x \in A_{n+1} \; \land \; x\not\in \text{in odd number of sets from}\; A_1,A_2\dots A_n \}  =

\{x \; | x\not\in A_{n+1} \; \land \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n \} \cup \{x \; | \; x \in A_{n+1} \; \land \; x \in \text{in even number of sets from}\; A_1,A_2\dots A_n \}=

\{x \; | \; x\in  \; \text{in odd number of sets from}\; A_1,A_2\dots A_n, A_{n+1} \}


לכן, הטענה נכונה גם עבור n+1 וסיימנו

תרגיל:

הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן n \geq 3 צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים) ושיש בשילוש n-3 אלכסונים.

פתרון: עבור n=3: מצולע קמור בן 3 צלעות חייב להיות משולש (ייתכן בעיוות כלשהוא) ולכן הוא ניתן לשילוש ע"י n-3=0 אלכסונים.

כעת נניח שהטענה נכונה עבור כל מצולע קמור בן 3\leq k \leq n ונוכיח את הטענה עבור מצלוע קמור בן n+1 צלעות (כלומר שכל מצולע קמור בן n+1 ניתן לשילוש עם (n+1)-3 אלכסונים). יהא מצולע קמור M בן n+1 צלעות. נמתח קו בין שני קודקודים שלו. כעת המצולע שהתחלנו איתו התחלק לשני מצולעים קמורים, נסמנם M_1,M_2. נסמן את מספר הצלעות של M_1 ב k (כלומר יש לו k-1 צלעות משותפות עם M + הצלע שהוספנו. מספר הצלעות של M הוא n+1 ולכן מספר הצלעות המשותפות בין M ל M_2 הוא n+1-(k-1)=n-k+2 ולכן מספר הצלעות של M_2 הוא n-k+3. כיוון ש 3\leq k,n-k+3\leq n+1 ניתן להפעיל את הנחת האינדוקציה על M_1,M_2 ולהסיק כי M_1,M_2 ניתן לשילוש ע"י k-3,n-k+3 - 3 אלכסונים. צירוף השילושים של M_1,M_2 יתן שילוש של M עם (k-3) + (n-k)+1=(n+1)-3 אלכסונים כנדרש.


תרגיל:

יהיו 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)