שגיאות בהוכחה באינדוקציה

סדרות ואינדוקציה, כיתה י"א (5 יח"ל) שיעור 21 מתוך 23לימוד

שגיאות בהוכחה באינדוקציה

צעד בלי בסיס

שתי סדרות מוגדרות באותו כלל, $\displaystyle {a_{n+1}}={a_n+2}$ ו- $\displaystyle {b_{n+1}}={b_n+2}$ , אבל $\displaystyle {a_1}={1}$ ו- $\displaystyle {b_1}={2}$ .

שלב הצעד נכון: אם $\displaystyle {a_k}={b_k}$ , אז $\displaystyle {a_{k+1}}={a_k+2}={b_k+2}={b_{k+1}}$ .
שלב הבסיס אינו נכון: $\displaystyle a_1\neq b_1$ .
והסדרות אכן שונות: $\displaystyle 1, 3, 5, \ldots$ ו- $\displaystyle 2, 4, 6, \ldots$ – אין להן אף איבר משותף.

דוגמה נוספת: $\displaystyle {a_n}={1+2+\ldots+n}$ ו- $\displaystyle {b_n}={\frac{n^2}{2}+\frac{n}{2}+\frac{1}{2}}$ . אם $\displaystyle {a_k}={b_k}$ , אז $\displaystyle {a_{k+1}}={b_k+k+1}={b_{k+1}}$ – הצעד עובד. אבל $\displaystyle {a_1}={1}$ ו- $\displaystyle {b_1}={\frac{3}{2}}$ , ולמעשה $\displaystyle {b_n}={a_n+\frac{1}{2}}$ תמיד.

בסיס בלי צעד

שתי סדרות: $\displaystyle {a_1}={b_1}={2}$ , $\displaystyle {a_{n+1}}={2a_n}$ ו- $\displaystyle {b_{n+1}}={b_n+2n}$ .

$\displaystyle a_n$ : $\displaystyle 2, 4, 8, 16, \ldots$ ; $\displaystyle b_n$ : $\displaystyle 2, 4, 8, 14, \ldots$
שלושת האיברים הראשונים שווים, והרביעי כבר לא.
התחלה משותפת – גם ארוכה – אינה מוכיחה ששתי סדרות שוות. בלי שלב הצעד אין הוכחה.

הנחה של מה שמוכיחים

“הוכחה”: “נניח שהטענה נכונה לכל $\displaystyle n$ טבעי. אז היא נכונה בפרט עבור $\displaystyle k+1$ , ולכן היא נכונה לכל $\displaystyle n$ .”

זו אינה הוכחה: ההנחה היא בדיוק הטענה שצריך להוכיח.
הנחת האינדוקציה היא על $\displaystyle k$ אחד, ומשתמשים בה כדי להוכיח את הטענה עבור $\displaystyle k+1$ – לא מניחים את הטענה עבור $\displaystyle k+1$ .

איך בודקים הוכחה

האם שלב הבסיס נבדק, ונכון?
האם הנחת האינדוקציה היא על $\displaystyle k$ אחד, והאם כתוב מה צריך להוכיח עבור $\displaystyle k+1$ ?
האם כל מעבר בשלב הצעד נכון, והאם ההנחה בשימוש?
האם ההוכחה מגיעה בדיוק לטענה עבור $\displaystyle k+1$ ?
האם כתוב שלב ההסקה?

תרגיל 1

דני כתב: “הטענה: $\displaystyle {1+5+9+\ldots+(4n-3)}={2n^2-n+1}$ . נניח שהטענה נכונה עבור $\displaystyle k$ . אז $\displaystyle {1+5+\ldots+(4k-3)+(4k+1)}={2k^2-k+1+4k+1}={2(k+1)^2-(k+1)+1}$ , ולכן הטענה נכונה לכל $\displaystyle n$ .”

בדקו בכרטיס את החישוב של דני.

/ – קו שבר · Tab או החצים – בין המונה למכנה, ואחר כך פתק מעל או מתחת · Enter – בדיקה ושורה חדשה · * – כפל · ^ – חזקה, ↓ – סוף החזקה

/ – קו שבר · Tab או החצים – בין המונה למכנה, ואחר כך פתק מעל או מתחת · Enter – שורה חדשה · * – כפל · ^ – חזקה, ↓ – סוף החזקה

מה חסר בהוכחה? האם הטענה נכונה? מהי הנוסחה הנכונה לסכום?

תרגיל 2

מיכל כתבה: “הטענה: $\displaystyle n^2+5n$ אי־זוגי לכל $\displaystyle n$ טבעי. נניח ש- $\displaystyle k^2+5k$ אי־זוגי. $\displaystyle {(k+1)^2+5(k+1)}={(k^2+5k)+2k+6}$ , וזה אי־זוגי ועוד זוגי – אי־זוגי. לכן הטענה נכונה.”
מצאו את השגיאה. האם הטענה נכונה?

תרגיל 3

על מעגל מסמנים $\displaystyle n$ נקודות ומחברים כל שתיים במיתר, כך שאין שלושה מיתרים שעוברים בנקודה אחת. מספר החלקים של העיגול עבור $\displaystyle {n}={1, 2, 3, 4, 5}$ : $\displaystyle 1, 2, 4, 8, 16$ .
יואב טוען שמספר החלקים הוא $\displaystyle 2^{n-1}$ לכל $\displaystyle n$ . עבור $\displaystyle {n}={6}$ מתקבלים 31 חלקים. מה השגיאה בדרך שבה יואב הגיע לטענה?

תרגיל 4

רון כתב: “הטענה: $\displaystyle 3^n-1$ מתחלק ב-4 לכל $\displaystyle n$ טבעי. נניח ש- $\displaystyle {3^k-1}={4m}$ . $\displaystyle {3^{k+1}-1}={3(3^k-1)+2}={12m+2}$ . לכן הטענה נכונה.”

בדקו בכרטיס את המעבר $\displaystyle {3^{k+1}-1}={3(3^k-1)+2}$ .

האם $\displaystyle 12m+2$ מתחלק ב-4? מצאו את כל השגיאות של רון, ובדקו את הטענה עבור $\displaystyle {n}={1}$ ו- $\displaystyle {n}={2}$ .

נוסחאות: סדרות ואינדוקציה, כיתה י"א (5 יח"ל)

פתיחה בעמוד

סדרה וסכום האיברים הראשונים

האיבר מהסכום – $\displaystyle S_n$ סכום $\displaystyle n$ האיברים הראשונים
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle S_n-S_{n-1}$ $\displaystyle n\geq2$
האיבר הראשון הוא הסכום של איבר אחד
$\displaystyle a_1$ $\displaystyle =$ $\displaystyle S_1$

סדרה חשבונית

כלל הנסיגה – $\displaystyle d$ הפרש הסדרה
$\displaystyle a_{n+1}=a_n+d$
האיבר הכללי
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle a_1+(n-1)d$
הממוצע החשבוני של השכנים
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle \frac{a_{n-1}+a_{n+1}}{2}$ $\displaystyle n\geq2$
סכום $\displaystyle n$ האיברים הראשונים
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{n(a_1+a_n)}{2}$
הסכום בלי האיבר האחרון
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{n\left[2a_1+(n-1)d\right]}{2}$

סדרה הנדסית

כלל הנסיגה – $\displaystyle q$ מנת הסדרה
$\displaystyle a_{n+1}=a_n\cdot q$
האיבר הכללי
$\displaystyle a_n$ $\displaystyle =$ $\displaystyle a_1\cdot q^{n-1}$
הממוצע ההנדסי: הריבוע של איבר הוא מכפלת שכניו
$\displaystyle a_n^2$ $\displaystyle =$ $\displaystyle a_{n-1}\cdot a_{n+1}$ $\displaystyle n\geq2$
סכום $\displaystyle n$ האיברים הראשונים
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{a_1(q^n-1)}{q-1}$ $\displaystyle q\neq1$

סדרה הנדסית אינסופית

סכום הסדרה המתכנסת
$\displaystyle S$ $\displaystyle =$ $\displaystyle \frac{a_1}{1-q}$ $\displaystyle -1<q<1,\ q\neq0$

חוקי החזקות

מכפלת חזקות עם אותו בסיס
$\displaystyle a^m\cdot a^n$ $\displaystyle =$ $\displaystyle a^{m+n}$
מנת חזקות עם אותו בסיס
$\displaystyle \frac{a^m}{a^n}$ $\displaystyle =$ $\displaystyle a^{m-n}$ $\displaystyle a\neq0$
חזקה של חזקה
$\displaystyle \left(a^m\right)^n$ $\displaystyle =$ $\displaystyle a^{mn}$
חזקה עם מעריך 0
$\displaystyle a^0$ $\displaystyle =$ $\displaystyle 1$ $\displaystyle a\neq0$
חזקה עם מעריך שלילי
$\displaystyle a^{-n}$ $\displaystyle =$ $\displaystyle \frac{1}{a^n}$ $\displaystyle a\neq0$

סכומים שהוכחו באינדוקציה

סכום המספרים הטבעיים
$\displaystyle 1+2+3+\ldots+n$ $\displaystyle =$ $\displaystyle \frac{n(n+1)}{2}$
סכום המספרים האי־זוגיים
$\displaystyle 1+3+5+\ldots+(2n-1)$ $\displaystyle =$ $\displaystyle n^2$
סכום הריבועים
$\displaystyle 1^2+2^2+3^2+\ldots+n^2$ $\displaystyle =$ $\displaystyle \frac{n(n+1)(2n+1)}{6}$
סכום החזקות השלישיות
$\displaystyle 1^3+2^3+3^3+\ldots+n^3$ $\displaystyle =$ $\displaystyle \frac{n^2(n+1)^2}{4}$