שינויים
/* לפעמים כדאי להניח הנחות חזקות יותר */
שזה הטענה עבור <math>n+1</math> וסיימנו.
=== לפעמים כדאי להניח הנחות חזקות יותר ===
תרגיל:
נגדיר <math>a_0 =0 , a_{n+1}=a_n^2 +1/4</math>. הוכח כי לכל n מתקיים <math>a_n<1</math> פתרון: נוכיח משהו יותר חזק - לכל n מתקיים <math>a_n<1/2</math> אכן: עבור <math>a_0</math> זה מתקיים. כעת נניח שנכון עבור n ונראה עבור n+1 <math>a_{n+1}=a_n^2+1/4<(1/2)^2+1/4 =1/2</math> ==סדר טוב - העשרה מתקדמת ביותר, לא להעביר לשנה א ==
הגדרה: יהי <math>R</math> יחס סדר חלקי על קבוצה <math>A</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>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+1</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>.
וסיימנו
אחרת <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)iq_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>\forall n ([\forall m<n P (m)] \to P(n))</math> *אז נכונה עבור <math>m<nP</math> אז הטענה נכונה עבור מתקיימת לכל <math>na\in A</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>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>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>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> מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחא
