אינדוקציה וסדרות

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

• $\displaystyle {a_1}={3}={b_1}$; $\displaystyle {a_2}={8}$ ו-$\displaystyle {b_2}={3+5}={8}$; $\displaystyle {a_3}={15}$ ו-$\displaystyle {b_3}={8+7}={15}$.
• האם $\displaystyle {a_n}={b_n}$ לכל $\displaystyle n$? בדיקה של מקרים אינה הוכחה. ההוכחה שלפניכם מוכיחה זאת באינדוקציה: אם האיברים שווים במקום $\displaystyle k$, הם שווים גם במקום $\displaystyle k+1$.

בשיעור על כלל נסיגה ניחשנו שהסדרה $\displaystyle {a_1}={3}$, $\displaystyle {a_{n+1}}={2a_n-1}$ היא $\displaystyle {a_n}={2^n+1}$. עכשיו נוכיח זאת:

• שלב הבסיס: $\displaystyle {2^1+1}={3}={a_1}$.
• שלב הצעד: נניח ש-$\displaystyle {a_k}={2^k+1}$. לפי כלל הנסיגה $\displaystyle {a_{k+1}}={2a_k-1}={2(2^k+1)-1}={2^{k+1}+1}$ – הנוסחה עבור $\displaystyle k+1$.
• שלב ההסקה: לפי עקרון האינדוקציה, $\displaystyle {a_n}={2^n+1}$ לכל $\displaystyle n$ טבעי.

גם הנוסחה $\displaystyle {a_n}={a_1+(n-1)d}$ מוכחת באינדוקציה מכלל הנסיגה $\displaystyle {a_{n+1}}={a_n+d}$:

• שלב הבסיס: $\displaystyle {a_1+0\cdot d}={a_1}$.
• שלב הצעד: אם $\displaystyle {a_k}={a_1+(k-1)d}$, אז $\displaystyle {a_{k+1}}={a_k+d}={a_1+kd}$ – הנוסחה עבור $\displaystyle k+1$.

ההסבר “מוסיפים $\displaystyle d$ בדיוק $\displaystyle n-1$ פעמים” הוא אותה הוכחה, בלי השלבים בשמם.

המספר המשולש $\displaystyle T_n$ הוא מספר הנקודות במשולש שבשורה התחתונה שלו $\displaystyle n$ נקודות.

• משולש $\displaystyle n+1$ הוא משולש $\displaystyle n$ ועוד שורה של $\displaystyle n+1$ נקודות: $\displaystyle {T_1}={1}$, $\displaystyle {T_{n+1}}={T_n+(n+1)}$.
• הנוסחה לפי מקום: $\displaystyle {T_n}={\frac{n(n+1)}{2}}$ – וההוכחה באינדוקציה היא ההוכחה של סכום המספרים הטבעיים.

סדרה מוגדרת בכלל הנסיגה $\displaystyle {a_1}={2}$, $\displaystyle {a_{n+1}}={a_n+4n+2}$.
הוכיחו באינדוקציה ש-$\displaystyle {a_n}={2n^2}$ לכל $\displaystyle n$ טבעי.

לפי כלל הנסיגה והנחת האינדוקציה $\displaystyle {a_{k+1}}={2k^2+4k+2}$. פרקו לגורמים, והגיעו ל-$\displaystyle 2(k+1)^2$:

סדרה מוגדרת בכלל הנסיגה $\displaystyle {a_1}={3}$, $\displaystyle {a_{n+1}}={3a_n-2}$.

כתבו את ארבעת האיברים הראשונים, ונחשו נוסחה לפי מקום. (רמז: החסירו 1 מכל איבר.)

הוכיחו את הניחוש באינדוקציה. בשלב הצעד הציבו את ההנחה בכלל הנסיגה:

המספרים המחומשים: $\displaystyle {P_1}={1}$, $\displaystyle {P_{n+1}}={P_n+3n+1}$ (כלומר $\displaystyle 1, 5, 12, 22, \ldots$).
הוכיחו באינדוקציה ש-$\displaystyle {P_n}={\frac{n(3n-1)}{2}}$ לכל $\displaystyle n$ טבעי.

לפי כלל הנסיגה והנחת האינדוקציה $\displaystyle {P_{k+1}}={\frac{k(3k-1)}{2}+3k+1}$. הגיעו ל-$\displaystyle \frac{(k+1)(3k+2)}{2}$:

$\displaystyle L(n)$ הוא מספר החלקים שאליהם $\displaystyle n$ ישרים מחלקים את המישור, כשאין בהם שני ישרים מקבילים ואין שלושה שעוברים בנקודה אחת.

ספרו את $\displaystyle L(1)$, $\displaystyle L(2)$, $\displaystyle L(3)$ בציור, ומצאו את $\displaystyle L(4)$.

הישר ה-$\displaystyle (n+1)$ חותך את $\displaystyle n$ הישרים הקודמים ב-$\displaystyle n$ נקודות, ולכן הוא עובר ב-$\displaystyle n+1$ חלקים וחוצה כל אחד מהם לשניים. כתבו כלל נסיגה ל-$\displaystyle L(n)$.

הוכיחו באינדוקציה ש-$\displaystyle {L(n)}={1+\frac{n(n+1)}{2}}$. בשלב הצעד:

סדרה מוגדרת בכלל הנסיגה $\displaystyle {a_1}={1}$, $\displaystyle {a_{n+1}}={\frac{a_n}{1+a_n}}$.
חשבו את $\displaystyle a_2$ ו-$\displaystyle a_3$, נחשו נוסחה לפי מקום, והוכיחו אותה באינדוקציה. בשלב הצעד: