שינויים
/* תרגיל: */
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <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</math> מתקיים כי <math>2+4+6+\cdots +2n=n(n+1)</math>
שזה הטענה עבור <math>n+1</math> וסיימנו.
==== תרגיל ====
הוכיחו שלכל <math>n</math> טבעי מתקיים <math>\sum_{k=1}^{n}(2k-1)=n^{2}</math>
=== לפעמים כדאי להניח הנחות חזקות יותר ===
תרגיל:
נגדיר <math>a_0 =0 , a_{n+1}=סדר טוב ==a_n^2 +1/4</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</math>ים מתקיים <math>n^{2}<2^{n}</math>
===הכללה פשוטה 2 ===
אחרת <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>
וסיימנו
עוד תרגילים [[מכינה למתמטיקה קיץ תשעב/תרגילים/4]]
[https://www.weizmann.ac.il/sci-tea/benari/sites/sci-tea.benari/files/uploads/softwareAndLearningMaterials/induction-he.pdf מדריך אינדוקציה של מכון ויצמן]
== תרגילים יותר מעניינים (לא בסגנון "בני גורן". אם יש את הרקע המספק)==
===תרגיל ===
יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:
<math>P_0 = A, P_n=(P_{n-1})\to A</math>
הוכיחו כי <math>P_{n}</math>
טואוטולוגיה כאשר <math>n</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_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</math> טבעי מתקיים:כל טבלה ריבועית בגודל <math>2^{n}\times2^{n}</math> שהוצאנו ממנה משבצת, ניתן לכסות ב "י" (3 משבצות בצורת האות יוד) הוכחה: באינדוקציה. בסיס <math>n=1</math>: טבלה ריבועית בגודל 2 על 2, ואכן כל משבצת שנוציא נשאר עם צורה "יוד" בודדת. צעד: נניח נכונות עבור <math>n</math> ונוכיח נוכונות עבור <math>n+1</math>. תהא טבלה בגודל <math>2^{n+1}\times2^{n+1}</math> שהוצאנו משבצת. את הטבלה הזאת נחלק ל 4 טבלאות קטנות יותר בגודל <math>2^{n}\times2^{n}</math> שאחת מהן חסרה משבצת. את הטבלה הזאת ניתן לכסות ב"יוד" ים לפי הנחת האינדוקציה. בנוסף ניתן להוציא "יוד" נוספת כך ששלושת הטבלאות האחרות יהיו חסרות משבצת אחת בדיוק ואז גם אותם ניתן לכסות ב"יוד" ים לפי הנחת האינדוקציה. מסקנה: לכל <math>n</math> טבעי מתקיים ש 3 מחלק את <math>\left(2^{n}\right)^{2}-1</math>.=== תרגיל ===תהא טבלת שוקולד עם <math>m</math> שורות ו <math>n</math> עמודות. חיתוך של טבלת שוקולד הוא שבירת הטבלה לשתי טבלאות קטנות לאורך או לרוחב הטבלה המקורית. הוכיחו כי בהינתן טבלה עם <math>N</math> קוביות שוקולד, צריך בדיוק <math>N-1</math> חיתוכים על מנת להפריד כל קוביה בנפרד (כלומר לקבל <math>N</math> טבלאות שכל אחת מגודל 1 על 1). הוכחה: באינדוקציה שלמה. אם הטבלה בגודל 1 על 1 סיימנו. אחרת, נבצע חיתוך שרירותי, נקבל 2 טבלאות קטנות יותר, נפעיל עליהם את הנחת האינדוקציה וסיימנו.===תרגיל===
הוכיחו בעזרת אינדוקציה כי כל מצולע קמור (כלומר הצלע בין כל שני קודקודים נמצאת בפנים המצולע) בן <math>n \geq 3</math> צלעות ניתן לשילוש (כלומר ניתן לחלק אותו למשולשים)
ושיש בשילוש <math>n-3</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>n=1</math> ל <math>n=2</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> יחס סדר חלקי לפי התמונה הבא (כאשר מזהים כל שבר עם זוג סדור ומבטלים את החזרות המיותרות)
[[קובץ:NutualSquareEqNutural.jpeg]]
התבוננו והשתכנעו שזה גם סדר טוב.
הערה: זה בניגוד לסדר "קטן שווה" הרגיל על השברים שאינו סדר טוב כי לקבוצה
<math>\{x\in \mathbb{Q}_+ | \sqrt{2}<x \}</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> איבר מינימום.
==== הכללה עקרון האינדוקציה בעזרת קבוצות סדורות היטב ====
תהא <math>A</math> קבוצה סדורה היטב (נסמן את היחס שלה ב<math>\leq</math>) אזי:
* '''אם''' <math>\forall n ([\forall m<n P(m)] \to P(n))</math>
*אז <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\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>d</math> כן מתקיים. סתירה. ולכן הטענה נכונה לכל <math>a\in A</math>
הערה: אפשר לעשות אינדוקציה הנקראת אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)
