תרגול 4 תשעז

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

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

הכללות

הכללה פשוטה 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$ כי $x>0$

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

נוכיח עבור $n+1$ מהנחת האינדוקציה נקבל כי $(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$

וסיימנו

הכללה פשוטה 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$ פסוק. נגדיר בעזרת אינדוקציה פסוקים: $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_{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$)