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

אינדוקציות על סכומים

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

דוגמא

טענה: לכל $n$ , סכומם של כל המספרים הטבעיים עד $n$ נתון באמצעות הנוסחא: ${\frac {n(n+1)}{2}}$

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

הוכחה: עלינו להוכיח שמתקיים: $1+\cdots +n={\frac {n(n+1)}{2}}$ .

• שלב א: בסיס האינדוקציה: נבדוק את נכונות הטענה עבור $n=1$ :

$1={\frac {1(1+1)}{2}}={\frac {2}{2}}=1$ , כלומר קיבלנו $1=1$ לכן הטענה נכונה עבור $n=1$ .

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

$1+\cdots +k={\frac {k(k+1)}{2}}$ עד ל- $k$ מסוים.

• שלב ג: צעד האינדוקציה: נוכיח עבור $n=k+1$ . במילים אחרות, עלינו להוכיח שמתקיים:

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

כעת: ניעזר בהנחת האינדוקציה, ונכתוב: $1+\cdots +k+(k+1)={\frac {k(k+1)}{2}}+(k+1)$ , כלומר למעשה עלינו להוכיח שמתקיים:

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

אם $\star$ , הרי שמתקיים גם: $\star \star \ k(k+1)+2(k+1)=(k+1)(k+2)$

וכן נשים לב שמתקיים: $(k+1)(k+2)=k(k+1)+2(k+1)$ , לכן מ- $\star \star$ נקבל: $k(k+1)+2(k+1)=k(k+1)+2(k+1)$ . וקיבלנו שוויון.

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

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

1. לנסח את מה שצריך להוכיח נכון.
2. לסמן את הנחת האינדוקציה ולהציב אותה בשלב האינדוקציה (לעתים יותר מפעם אחת!).
3. לבצע מספר פעולות חשבוניות עד לקבלת התוצאה המיוחלת.

יש לשים לב שמותר ואף רצוי לעתים לנצל את הנחת האינדוקציה כמה פעמים.

הפרק הקודם: אינדוקציה של טענה כללית

אינדוקציה על סכומים תרגילים

הפרק הבא: אינדוקציה על אי-שוויונות