אינדוקציה – הסבר ודוגמאות

אינדוקציה

אינדוקציה מתמטית היא שיטה המוכיחה שתכונה מסוימת מתקיימת לכל המספרים הטבעיים (=שלמים וחיוביים). לרוב, מציינים מספר טבעי במשתנה n, ורוב ההוכחות באינדוקציה יהיו להוכחת משוואות ואי-שוויונים במשתנה n. 

כך אינדוקציה עובדת:

1. בסיס האינדוקציה: בודקים שהמשוואה (או האי-שוויון) מתקיימים עבור ה-n (הטבעי) הכי קטן. בדרך כלל, זה יהיה המספר 1, אלא אם כן נאמר אחרת בתרגיל.
2. הנחת האינדוקציה: מניחים שהמשוואה (או האי-שוויון) מתקיימים עבור n מסוים, כלומר מניחים שהמשוואה (או האי-שוויון) שצריך להוכיח כבר נכון.
3. צעד האינדוקציה: מוכיחים – בעזרת הנחת האינדוקציה – שהמשוואה (או האי-שוויון) מתקיימים עבור n+1, כלומר ניקח את המשוואה (או האי-שוויון) מהנחת האינדוקציה ובכל מקום שמופיע n נכתוב n+1. את המשוואה (או האי-שוויון) שנקבל נוכיח בעזרת המשוואה (או האי-שוויון) מהנחת האינדוקציה.

אם הצלחנו לבצע את שלושת השלבים, אפשר להסיק שהמשוואה או האי-שוויון מתקיימים לכל n.

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

דוגמה 1

הוכיחו את המשוואה:

1+2+3+...+n=\frac{n(n+1)}{2}

לכל n.

פתרון

נוכיח את נכונות המשוואה לכל n בעזרת אינדוקציה. לשם כך, נעשה את 3 השלבים של הוכחת אינדוקציה.

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

n=1

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

1=\frac{1\cdot (1+1)}{2}

1=1

קיבלנו שוויון, וזה אומר שהמשוואה נכונה עבור n=1.

הנחת האינדוקציה: נניח שהמשוואה נכונה עבור n מסוים. כלומר, נניח שהמשוואה:

1+2+3+...+n=\frac{n(n+1)}{2}

נכונה.

צעד האינדוקציה: נוכיח שהמשוואה נכונה עבור n+1. לשם כך, ניקח את המשוואה מהשלב הקודם, ובכל מקום שמופיע n, נכתוב n+1. כך נקבל את המשוואה:

1+2+3+...+n+(n+1)=\frac{(n+1)(n+1+1)}{2}

1+2+3+...+n+(n+1)=\frac{(n+1)(n+2)}{2}

כעת, נשתמש במשוואה מהנחת האינדוקציה, כדי להוכיח את המשוואה שקיבלנו. נתחיל מאגף שמאל ונגיע – בעזרת הנחת האינדוקציה – לאגף ימין.

1+2+3+...+n+(n+1)=

נשתמש בהנחת האינדוקציה ונקבל:

=\frac{n(n+1)}{2}+(n+1)=

נעשה מכנה משותף:

=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}=

=\frac{n(n+1)+2(n+1)}{2}=

נוציא גורם משותף:

=\frac{(n+1)(n+2)}{2}

לסיכום, קיבלנו:

1+2+3+...+n+(n+1)=\frac{(n+1)(n+2)}{2}

הצלחנו להוכיח את המשוואה עם n+1 (של צעד האינדוקציה), וזה מוכיח את המשוואה המקורית בתרגיל לפי שיטת האינדוקציה.

מ.ש.ל.

דוגמה 2

הוכיחו את האי-שוויון:

n<2^n

לכל n.

פתרון

נוכיח את נכונות האי-שוויון לכל n בעזרת אינדוקציה. לשם כך, נעשה את 3 השלבים של הוכחת אינדוקציה.

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

n=1

נציב את זה באי-שוויון. ההצבה נותנת לנו את האי-שוויון:

1<2^1

1<2

קיבלנו שהאי-שוויון נכון עבור n=1.

הנחת האינדוקציה: נניח שהאי-שוויון נכון עבור n מסוים. כלומר, נניח שהאי-שוויון:

n<2^n

נכון.

צעד האינדוקציה: נוכיח שהאי-שוויון נכון עבור n+1. לשם כך, ניקח את האי-שוויון מהשלב הקודם, ובכל מקום שמופיע n, נכתוב n+1. כך נקבל את האי-שוויון:

n+1<2^{n+1}

כעת, נשתמש באי-שוויון מהנחת האינדוקציה, כדי להוכיח את האי-שוויון שקיבלנו. נתחיל מאגף ימין ונגיע – בעזרת הנחת האינדוקציה – לאגף שמאל:

2^{n+1}=2\cdot 2^n

נשתמש בהנחת האינדוקציה ונקבל:

2\cdot 2^n>2\cdot n

נפרק את הביטוי שקיבלנו:

2n=n+n

ומכיוון שמתקיים:

n+n>n+1

מקבלים את האי-שוויון:

n+1<2^{n+1}

כנדרש. הצלחנו להוכיח את המשוואה עם n+1 (של צעד האינדוקציה), וזה מוכיח את המשוואה המקורית בתרגיל לפי שיטת האינדוקציה.

מ.ש.ל.

לתרגילים ופתרונות המשתמשים באינדוקציה לחצו כאן

עזרתי לך להבין את החומר? מצאת טעות? יש לך שאלה בנוגע לפתרון זה? כתב/י תגובה למטה ואשמח לענות 🙂