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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מתמטיקה תיכונית | אלגברה תיכונית | אינדוקציה מתמטית

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

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

[עריכה] דוגמא

טענה

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

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

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

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

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

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

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

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

$\ 1+...+k+(k+1)=\frac{ \left(k+1 \right) \left( k+2\right)}{2}$
כעת: ניעזר בהנחת האינדוקציה, ונכתוב: $\ 1+...+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)$ .
וקיבלנו שיוויון. מכאן, על פי משפט ההוכחה באינדוקציה, הטענה נכונה לכל מספר טבעי