שינויים
/* רעיון בסיסי - אינדוקציה על הטבעיים */
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
=אינדוקציה מתמטית: רעיון בסיסי - אינדוקציה על הטבעיים=
נוכיח באינדוקציה כי הטענה <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>
נכונה לכל <math>n\in \mathbb{N} </math> טבעי.
הוכחה:
עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math> .
כעת נראה שאם הטענה נכונה עבור <math>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>=1^3 +2^3 + \cdots +n^3 +2\cdot (1+2+\cdots +n)(n+1)+(n+1)^2 </math>
<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>
שזה הטענה עבור <math>n+1</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>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)>(1+nx) (1+x)= 1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x </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>n</math> ולהוכיח עבור <math>n+1</math>
בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>.
הוכחה:
עבור <math>n=2</math> זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.
כעת נניח שהטענה נכונה לכל <math>1<k\leq n</math> ונוכיח עבור <math>n+1</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_i</math> ראשוניים.
יהא <math>A</math> פסוק. נגדיר בעזרת אינדוקציה פסוקים:
<math>P_0 = A, P_n=(P_{n-1})\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>A</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>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>n=1</math> ל <math>n=2</math>).
