עקרון האינדוקציה · אינדוקציה מתמטית · כיתה י״א

חשבו את הסכומים $1$ , $1+2$ , $1+2+3$ , $1+2+3+4$ וכן הלאה. יוצא $1, 3, 6, 10, 15$ . נראה שהסכום של $n$ המספרים הראשונים הוא $\frac{n(n+1)}{2}$ . בדקנו חמישה ערכים. אבל איך יודעים שהנוסחה נכונה גם עבור $n=1000$ , ועבור כל $n$ ?

כל סכום הוא הסכום הקודם ועוד המספר הבא:

S_{n+1}=S_n+(n+1)

. הקשר הזה בין סכום לסכום שאחריו הוא הבסיס של האינדוקציה.

מהו $S_6=1+2+\dots+6$ ? חשבו פעם מ- $S_5=15$ ופעם בנוסחה $\frac{n(n+1)}{2}$ .

להציג את התשובה והפתרון

$S_6=15+6=21$ , ובנוסחה $\frac{6 \cdot 7}{2}=21$ . שתי הדרכים נותנות אותו מספר: הנוסחה עברה מ- $5$ ל- $6$ .

שורה של אבני דומינו

דמיינו שורה אינסופית של אבני דומינו. כדי שכל האבנים ייפלו צריך שני דברים: שהאבן הראשונה תיפול, ושכל אבן שנופלת תפיל את הבאה אחריה. זה עקרון האינדוקציה המתמטית.

שלושת השלבים בכתיבה

1

בדיקה: מציבים $n=1$ בשני האגפים ומראים שהם שווים

2

הנחה: מניחים שהטענה נכונה עבור $n=k$ (הנחת האינדוקציה)

3

הוכחה: מוכיחים את הטענה עבור $n=k+1$ , בעזרת ההנחה

הוכחה: $1+2+\dots+n=\frac{n(n+1)}{2}$

$n$ מספר טבעי

$1+2+\dots+n=\frac{n(n+1)}{2}$ לכל $n$ טבעי

$n=1$ : אגף שמאל $1$ , אגף ימין $\frac{1 \cdot 2}{2}=1$

בדיקה עבור $n=1$

$1+2+\dots+k=\frac{k(k+1)}{2}$

הנחת האינדוקציה

$1+2+\dots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)$

מציבים את ההנחה במקום $k$ המחוברים הראשונים

$=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}$

מכנה משותף, ואז הוצאת הגורם המשותף $(k+1)$

$\frac{(k+1)(k+2)}{2}$ היא הנוסחה עבור $n=k+1$

מציבים $n=k+1$ ב- $\frac{n(n+1)}{2}$ ומקבלים אותו ביטוי

הבסיס והצעד הוכחו, ולכן לפי עקרון האינדוקציה הנוסחה נכונה לכל $n$ טבעי.

לפני שמתחילים את שלב 3, כותבים את המטרה. מהי הנוסחה עבור $n=k+1$ ?

להציג את התשובה והפתרון

$1+2+\dots+(k+1)=\frac{(k+1)(k+2)}{2}$ . מציבים $k+1$ במקום כל $n$ בנוסחה, גם בתוך הסוגריים: $n+1$ הופך ל- $k+2$ .

לכתוב את המטרה לפני החישוב

הטענה: $2+4+6+\dots+2n=n(n+1)$ . מה כותבים בשלב ההוכחה?

2+4+\dots+2k=k(k+1)

הנחת האינדוקציה

2+4+\dots+2k+2(k+1)=(k+1)(k+2)

המטרה: מציבים $n=k+1$ . האיבר החדש הוא $2(k+1)$

k(k+1)+2(k+1)=(k+1)(k+2)

מציבים את ההנחה ומוציאים גורם משותף $(k+1)$ . הגענו למטרה

הנחת האינדוקציה היא הנחה, לא מה שמוכיחים. בשלב 3 חייבים להשתמש בה. הוכחה שלא משתמשת בהנחה בכלל היא סימן שמשהו חסר. בבגרות הופיעו בעבר גם טענות על התחלקות (למשל ש- $4^n-1$ מתחלק ב- $3$ ), אבל השנה הן לא נלמדות. בפרק הזה נוכיח סכומים, נוסחאות של סדרות ונזהה הוכחות שגויות.

שתי הטעויות הנפוצות בשלב ההוכחה.

n=k+1: \ \frac{k(k+1)}{2}+1

n=k+1: \ \frac{(k+1)(k+2)}{2}

מציבים $k+1$ במקום $n$ בכל מקום בנוסחה. לא מוסיפים $1$ לתוצאה.

P(1),\ P(2),\ P(3) \ \checkmark \ \Rightarrow \ P(n)

P(1) \ \text{+} \ \big(P(k) \Rightarrow P(k+1)\big)

בדיקה של כמה ערכים, גם של מאה ערכים, אינה הוכחה. היא רק מחזקת את ההשערה.

תרגילים

תרגיל 1

מה צריך להוכיח בהוכחה באינדוקציה של טענה על כל $n$ טבעי?

שאם הטענה נכונה עבור $n=k$ אז היא נכונה עבור $n=k+1$
שהטענה נכונה עבור $n=k$
שהטענה נכונה עבור $n=1$ , $n=2$ ו- $n=3$
שהטענה נכונה עבור $n=1$ , ושאם היא נכונה עבור $n=k$ אז היא נכונה עבור $n=k+1$

להציג את התשובה והפתרון

התשובה: ד שהטענה נכונה עבור $n=1$ , ושאם היא נכונה עבור $n=k$ אז היא נכונה עבור $n=k+1$

הפתרון:

P(1)

הבסיס

P(k) \Rightarrow P(k+1)

הצעד

הנכונה: בסיס וצעד יחד. שלוש בדיקות אינן הוכחה. צעד בלי בסיס לא מתחיל. ו-«נכונה עבור $n=k$ » זו ההנחה, לא ההוכחה.

לבדוק את התשובה שלי ב-elev

תרגיל 2

הטענה היא $1+2+\dots+n=\frac{n(n+1)}{2}$ . מה צריך להוכיח עבור $n=k+1$ ?

$1+2+\dots+k=\frac{(k+1)(k+2)}{2}$
$1+2+\dots+(k+1)=\frac{k(k+1)}{2}+1$
$1+2+\dots+(k+1)=\frac{(k+1)k}{2}$
$1+2+\dots+(k+1)=\frac{(k+1)(k+2)}{2}$

להציג את התשובה והפתרון

התשובה: ד $1+2+\dots+(k+1)=\frac{(k+1)(k+2)}{2}$

הפתרון:

n \to k+1: \quad n+1 \to k+2

מציבים בכל מקום

הנכונה: $\frac{(k+1)(k+2)}{2}$ . מי שבחר $\frac{k(k+1)}{2}+1$ הוסיף $1$ לתוצאה במקום להציב. בתשובה האחרונה $n+1$ לא הפך ל- $k+2$ .

לבדוק את התשובה שלי ב-elev

תרגיל 3

לפי הנוסחה $1+2+\dots+n=\frac{n(n+1)}{2}$ , חשבו את $1+2+3+\dots+50$ .

להציג את התשובה והפתרון

התשובה: 1275

הפתרון:

n=50

יש 50 מחוברים

\frac{50 \cdot 51}{2}=1275

מציבים

הנוסחה שהוכחנו חוסכת חיבור של חמישים מספרים. הטעות הנפוצה: לשכוח לחלק ב- $2$ ולקבל $2550$ .

לבדוק את התשובה שלי ב-elev

תרגיל 4

הוכיחו או הפריכו: אם בדקנו שהטענה נכונה עבור $n=1, 2, 3, \dots, 100$ , היא נכונה לכל $n$ טבעי.

להציג את התשובה והפתרון

התשובה: לא נכון

הפתרון:

P(1), \dots, P(100)

מאה בדיקות

P(101) \ ?

שום דבר לא מבטיח את הבאה

הטענה לא נכונה. בדיקות רבות אינן מחליפות את הצעד. בשיעור על הוכחות שגויות נראה נוסחה שעוברת שלוש בדיקות ונכשלת ברביעית.

לבדוק את התשובה שלי ב-elev

תרגיל 5

הטענה: $2+4+\dots+2n=n(n+1)$ . השלימו את שלב ההוכחה עבור $n=k+1$ .

$2+4+\dots+2k+2(k+1)=k(k+1)+$ ____ $(k+1)=(k+1)(k+$ ____ $)$

להציג את התשובה והפתרון

התשובה: $2+4+\dots+2k+2(k+1)=k(k+1)+$ 2 $(k+1)=(k+1)(k+$ 2 $)$

הפתרון:

2+4+\dots+2k=k(k+1)

הנחת האינדוקציה

k(k+1)+2(k+1)

מוסיפים את האיבר החדש

=(k+1)(k+2)

גורם משותף $(k+1)$

$(k+1)(k+2)$ היא בדיוק $n(n+1)$ עבור $n=k+1$ . המלכודת: לפתוח סוגריים ל- $k^2+3k+2$ ולא לזהות את המטרה. גורם משותף מראה אותה מיד.

לבדוק את התשובה שלי ב-elev

תרגיל 6

מיינו כל משפט לשלב שבו הוא נכתב, בהוכחה של $1+3+5+\dots+(2n-1)=n^2$ .

בסיס (בדיקה)
צעד (הנחה והוכחה)

$1=1^2$
$k^2+(2k+1)=(k+1)^2$
מציבים $n=1$ בשני האגפים
נוכיח עבור $n=k+1$
נניח $1+3+\dots+(2k-1)=k^2$

להציג את התשובה והפתרון

התשובה: $1=1^2$ — בסיס (בדיקה) · מציבים $n=1$ בשני האגפים — בסיס (בדיקה) · נניח $1+3+\dots+(2k-1)=k^2$ — צעד (הנחה והוכחה) · $k^2+(2k+1)=(k+1)^2$ — צעד (הנחה והוכחה) · נוכיח עבור $n=k+1$ — צעד (הנחה והוכחה)

הפתרון:

1=1^2

$n=1$ : הבסיס

k^2+2k+1=(k+1)^2

הצעד

הבסיס הוא מספרים, בלי $k$ . הצעד עובד עם $k$ כללי. המלכודת: לחשוב שהבסיס הוא הנחה. הבסיס נבדק בחישוב.

לבדוק את התשובה שלי ב-elev

תרגיל 7

לפניכם שלב ההוכחה של $1+2+\dots+n=\frac{n(n+1)}{2}$ . שורה אחת שגויה. מצאו אותה.

1+2+\dots+k=\frac{k(k+1)}{2}

1+2+\dots+(k+1)=\frac{k(k+1)}{2}+(k+1)

=\frac{k(k+1)+(k+1)}{2}

=\frac{(k+1)(k+2)}{2}

להציג את התשובה והפתרון

התשובה: $=\frac{k(k+1)+(k+1)}{2}$ → $=\frac{k(k+1)+2(k+1)}{2}$

הפתרון:

(k+1)=\frac{2(k+1)}{2}

מכנה משותף

כדי לחבר $(k+1)$ לשבר שמכנהו $2$ , כופלים את $(k+1)$ ב- $2$ . השורה האחרונה נכונה, אבל היא לא נובעת מהשורה השגויה.

לבדוק את התשובה שלי ב-elev

תרגיל 8

סדרו את שלבי ההוכחה של $2+4+\dots+2n=n(n+1)$ .

בודקים עבור $n=1$ : $2=1 \cdot 2$
כותבים את המטרה: $2+4+\dots+2(k+1)=(k+1)(k+2)$
מוציאים גורם משותף ומקבלים $(k+1)(k+2)$
מניחים: $2+4+\dots+2k=k(k+1)$
מציבים את ההנחה: $k(k+1)+2(k+1)$

להציג את התשובה והפתרון

התשובה: בודקים עבור $n=1$ : $2=1 \cdot 2$ · מניחים: $2+4+\dots+2k=k(k+1)$ · כותבים את המטרה: $2+4+\dots+2(k+1)=(k+1)(k+2)$ · מציבים את ההנחה: $k(k+1)+2(k+1)$ · מוציאים גורם משותף ומקבלים $(k+1)(k+2)$

הפתרון:

P(1)

בסיס

P(k)

הנחה

P(k+1)

מטרה, ואז חישוב

קודם בסיס, אחר כך הנחה, ורק אז החישוב. המלכודת: להתחיל מהמטרה ולהגיע ממנה ל- $0=0$ . כך לא מוכיחים שוויון.

לבדוק את התשובה שלי ב-elev

תרגיל 9

הוכיחו באינדוקציה: לכל $n$ טבעי, $2+4+6+\dots+2n=n(n+1)$ . כתבו בכל שורה טענה ונימוק.

$n$ מספר טבעי

$2+4+\dots+2n=n(n+1)$

להציג את התשובה והפתרון

$2=1 \cdot 2$ — בדיקה עבור $n=1$
$2+4+\dots+2k=k(k+1)$ — הנחת האינדוקציה
$2+4+\dots+2k+2(k+1)=k(k+1)+2(k+1)$ — מוסיפים את האיבר ה- $(k+1)$ ומציבים את ההנחה
$k(k+1)+2(k+1)=(k+1)(k+2)$ — הוצאת גורם משותף $(k+1)$
$2+4+\dots+2(k+1)=(k+1)(k+2)$ — כלל המעבר: זו הטענה עבור $n=k+1$

הפתרון:

2=1 \cdot 2

בסיס

k(k+1)+2(k+1)=(k+1)(k+2)

צעד

האיבר ה- $(k+1)$ הוא $2(k+1)$ , לא $2$ . המלכודת: להוסיף רק את המספר $2$ .

לבדוק את התשובה שלי ב-elev

שורה של אבני דומינו

שלושת השלבים בכתיבה

תרגילים

השיעור הבא מחכה ב-elev