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

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

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

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

על-מנת להבין איך כדאי להתמודד עם סוג כזה של אינדוקציות, נביט על הטענה הבאה:

לכל $n$ טבעי, הביטוי $5^{n}-1$ מתחלק ב- $4$ ללא שארית.

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

• שלב א: בסיס האינדוקציה: נציב $n=1$ בביטוי שלמעלה, ונקבל: ${\frac {5^{1}-1}{4}}={\frac {5-1}{4}}=1$ : קיבלנו 1 שהוא מספר שלם.
• שלב ב': הנחת האינדוקציה: מניחים של- $n=k$ כללי הביטוי ${\frac {5^{k}-1}{4}}$ הוא מספר שלם.
• שלב ג': צעד האינדוקציה: עבור $n=k+1$ , עלינו להוכיח שהביטוי ${\frac {5^{k+1}-1}{4}}$ הוא מספר שלם.

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

נתבונן בביטוי ${\frac {5^{k+1}-1}{4}}$ : אפשר לפרק אותו ל- ${\frac {5\cdot 5^{k}-1}{4}}$ . בנוסף, מתקיים: $5=4+1$ , ואז מה שצריך להוכיח הוא שהביטוי ${\frac {5^{k}\cdot \left(4+1\right)-1}{4}}$ נותן מספר שלם.
נפתח סוגרים: ${\frac {4\cdot {5}^{k}+5^{k}-1}{4}}=\underbrace {\frac {5^{k}-1}{4}} _{\star }+{\frac {4\cdot {5^{k}}}{4}}$. קיבלנו את הנחת האינדוקציה (מסומנת ב- $\star$ , שהיא שלמה לכל מספר טבעי (כך הנחנו), ואת הביטוי $5^{k}$, שהוא שלם לכל $k$ טבעי.

לסיכום: קיבלנו סכום של שני מספרים שלמים, וסכום כזה תמיד יתן מספר שלם. מש"ל.

לתרגול עצמי

1. נתונה הנוסחא $a^{n}-1$ כאשר $a$ הוא מספר טבעי. הוכח שלכל $n$ טבעי ו- $a$ אי-זוגי, הביטוי ${\frac {a^{n}-1}{2}}$ הוא שלם.