תרגול 4 תשעז

חזרה לדף מערכי התרגול.

אינדוקציה מתמטית: רעיון בסיסי

אינדוקציה היא שיטה המאפשרת להוכיח שטענה מסוימת $P(n)$ נכונה עבור כל מספר טבעי (למשל $(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3$) בעזרת הסקה מן הפרט אל הכלל.

הוכחת הטענה $\forall nP(n)$ שקולה להוכחת שתי הטענות הבאות:

• (בסיס האינדוקציה) הטענה מתקיימת עבור $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$ וסיימנו.

הכללות

הכללה פשוטה ראשונה

הכללה ישירה שבה יש שינוי רק בבסיס האינדוקציה: אם נוכיח עבור טענה $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$

וסיימנו.

הכללה פשוטה שנייה

הכללה שבה יש שינוי בצעד האינדוקציה, הנקראת אינדוקציה שלמה: אם נוכיח עבור טענה $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=\prod_{k=1}^l p_k,b=\prod_{i=1}^r q_i$ כאשר $p_k,q_i$ ראשוניים.

אזי $n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{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$).