מתמטיקה תיכונית/אלגברה תיכונית/אינדוקציה מתמטית/אינדוקציה על פי נוסחאות הנסיגה (רקורסיה)

נסיגה

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

איך מתבצעת הוכחה?

1. מבצעים בדיקה עבור $n=1$ - בבדיקה זו אנו בודקים שהנוסחא הכללית של הסדרה ($a_n$) והתנאי הראשוני ($n=1$) נכונים.
2. הנחה - נניח כי $a_n$ נכון עבור כל מספר טבעי.
3. צריך להוכיח - נניח כי הטענה נכונה עבור המספר עוקב הבא, כלומר נציב נוסחא הכללית את $n+1$.
4. על פי כלל הנסיגה - נציג את שידועה לנו (הנוסחא $a_{n+1}$) כאשר אנו מציבים בה את הנעלם $k$.
5. עח פי הנחת האינדוקציה - בשלב זה אנו מציבים בנוסחא הנתון את $a_n$ (נתון) ו-$a_{n+1}$ (שקיבלנו באינדוקציה)
6. הוכחה - מוכיחים ששני צדי משוואה שווים.
7. סיכום.

דוגמא

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

פתרון
בדיקה עבור $n=1$ - נבדוק שהאיבר הראשוני של הסדרה הוא הכן $n=1$. על ידי הצבה בנוסחא הכללית של הסדרה את המיקום $n=1$	$\begin{array}{cc}& a_n=3n^2-n-1\\ & a_1=3*1^2-1-1\\ & a_1=3-2\\ & a_1=1\\ & 1=1\\ \end{array}$
נניח כי הטענה נכונה עבור $n=k$ כאשר $k$ טבעי	$\begin{array}{cc}& a_k=3k^2-k-1\\ \end{array}$
נניח כי הטענה נכונה עבור $n=k+1$	$\begin{array}{cc}& a_{k+1}=3(k+1{)}^2-(k+1)-1\\ & =3k^2+6k+3-k-1-1\\ & =3k^2+5k+1\\ \end{array}$
על פי כלל הנסיגה	$\begin{array}{cc}& a_{n+1}=a_n+6n+2\\ & a_{k+1}=a_k+6k+2\\ \end{array}$
על פי הנחת האינדוקציה	$\begin{array}{cc}& a_{n+1}=a_n+6n+2\\ & 3k^2+5k+1=3k^2-k-1+6k+2\\ \end{array}$
הוכחה	$\begin{array}{cc}& 3k^2+5k+1=3k^2-k-1+6k+2\\ & 3k^2+5k+1=3k^2+5k+1\\ \end{array}$
האינדוקציה נכונה על פי שלושת שלבי האינדוקציה.

מצבים

התחלקות ונסיגה

את כלל ההתחלקות פגשנו עוד לפני. במצבים בהם נתונים שני הכללים יהיה עלינו ל"תרגם" את הבקשה לנוסחא מתמטית.
למשל, סדרה המקיימת את כלל הנסיגה $a_1=9$, $a_{n+1}=a_n+11^n-5^n$. הוכח באינדוציה ש-$a_n$ מתחלק ב-$5$ ללא שארית.
כלומר, נבצע את האינדוקציה על $\frac{a_k}{5}$. תבנית:להשלים