שינויים
/* תרגיל */
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <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>(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>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>R</math> יקרא סדר טוב אם לכל <math>\emptyset \neq B\subseteq A</math> קיים איבר מינימום/הכי קטן/ראשון ב <math>Ba_0</math>זה מתקיים.כעת נניח שנכון עבור n ונראה עבור n+1
==הכללות==
פתרון:
עבור <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</math> (כלומר מתקיים <math>P(m)</math> עבור <math>m\leq n</math>) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר <math>P(n+1)</math> מתקיים).
אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k1</math>
כלומר - אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>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=\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,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>a</math> מספר ממשי המקיים כי <math>a+\frac{1}{a}</math> מספר שלם. הוכיחו כי לכל <math>n</math> טבעי מתקיים כי <math>a^n+\frac{1}{a^n}</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=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>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>)