עיקרון האינדוקציה: שלב הבסיס ושלב הצעד

מבוא

מטרות השיעור

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

הרעיון המרכזי

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

עיקרון האינדוקציה

כדי להוכיח שטענה מתקיימת לכל מספר טבעי n, די להוכיח שתי דרישות:

שלב הבסיס: הטענה מתקיימת עבור n=1.
שלב הצעד: אם הטענה מתקיימת עבור מספר טבעי כלשהו k, אז היא מתקיימת גם עבור העוקב k+1.

מקיומן של שתי הדרישות נובע (שלב ההסקה) שהטענה מתקיימת לכל מספר טבעי.

בדיקה מהירה

בהוכחה באינדוקציה מהם שני השלבים שצריך להוכיח?

כדי לבדוק, סמנו או הקלידו תשובה קודם

דימוי הדומינו

דמיינו שורה אינסופית של אבני דומינו. אנו רוצים שכולן ייפלו.

שלב הבסיס = להפיל את האבן הראשונה.
שלב הצעד = להבטיח שכל אבן שנופלת מפילה את האבן הבאה אחריה.

אם שני אלה מתקיימים — האבן הראשונה נופלת, ולכן השנייה, ולכן השלישית, וכן הלאה לכל אורך השורה. בדיוק זו הלוגיקה של האינדוקציה.

דוגמאות מפורטות

דוגמה 1: זיהוי שלב הבסיס

מהו שלב הבסיס בהוכחת $1+2+\ldots+n = \frac{n(n+1)}{2}$ ?

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

שלב 1 — מהו המקרה הראשון

המספר הטבעי הראשון הוא

n=1

בדיקה מהירה

בהוכחה באינדוקציה של הטענה 'לכל n טבעי מתקיים $1+2+\ldots+n = \frac{n(n+1)}{2}'$ , מהו שלב הבסיס?

כדי לבדוק, סמנו או הקלידו תשובה קודם

דוגמה 2: ניסוח שלב הצעד

כיצד מנסחים את שלב הצעד עבור $1+2+\ldots+n = \frac{n(n+1)}{2}$ ?

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

שלב 1 — הנחת האינדוקציה

מניחים שעבור k מסוים מתקיים

1+2+\ldots+k = \frac{k(k+1)}{2}

בדיקה מהירה

מהי ההבחנה הנכונה בין 'הטענה הכללית שמוכיחים' לבין 'ההנחה בשלב הצעד'?

כדי לבדוק, סמנו או הקלידו תשובה קודם

דוגמה 3: הוכחה ויזואלית — משולש נקודות

במשולש נקודות, שורה i מכילה i נקודות. הוכיחו שב-n השורות הראשונות יש $\frac{n(n+1)}{2}$ נקודות

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

בייצוג הויזואלי הזה ההוספה של שורה אחת מתאימה באופן טבעי למעבר מ-k ל-k+1.

שלב הבסיס $(n=1)$

שורה אחת מכילה נקודה אחת. הנוסחה נותנת

1 \cdot \frac{2}{2} = 1

. מתאים.

דוגמה 4: צעד תקין אך בסיס שנכשל

מדוע ההוכחה ש- $2+4+\ldots+2n = n^{2}+n+1$ פסולה?

2 + 4 + \dots + 2 n = n (n + 1) = n^{2} + n \neq = n^{2} + n + 1

זו הדגמה ששני השלבים אינם תלויים זה בזה — צעד תקין בלבד אינו מספיק.

שלב 1 — בודקים את שלב הצעד

נניח

2+4+\ldots+2k = k^{2}+k+1

. מוסיפים

2(k+1): k^{2}+k+1 + 2k+2 = k^{2}+3k+3

בדיקה מהירה

תלמיד 'הוכיח' את הטענה $2+4+6+\ldots+2n = n^{2}+n+1$ . הוא הראה נכון את שלב הצעד, אך לא בדק את שלב הבסיס. בדקו את $n=1:$ אגף שמאל $= 2$ , אגף ימין $= 1+1+1 = 3$ . מה המסקנה הנכונה?

כדי לבדוק, סמנו או הקלידו תשובה קודם

טעויות נפוצות

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

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

למה זה קורה?

תלמידים בודקים

n=1,2,3,4

ומסיקים שהטענה נכונה לכל n.

איך מתקנים?

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

טעות נפוצה: מדלגים על שלב הבסיס

בטענה $2 + 4 + \dots + 2 n = n^{2} + n + 1$ שלב הצעד תקין, אך הבסיס נכשל ( $2 \neq = 3$ ), והטענה שגויה לכל n.

למה זה קורה?

תלמידים מניחים שדי בשלב הצעד כדי לסיים את ההוכחה.

איך מתקנים?

בלי בסיס תקין אין 'אבן ראשונה'. ייתכן ששלב הצעד נכון אך הטענה שגויה לכל n.

טעות נפוצה: מבלבלים בין ההנחה לבין הטענה הכללית

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

למה זה קורה?

חושבים שהנחת הצעד ('נכון עבור k') זהה לטענה שמוכיחים ('נכון לכל n'), ולכן זו 'הנחת המבוקש'.

איך מתקנים?

'לכל n' ו'עבור k אחד מסוים' הן טענות שונות. בשלב הצעד מניחים מקרה יחיד ומוכיחים גרירה — לא מניחים את כל מה שרוצים.

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

עבור הטענה $n^{2} < n$ , כבר ב-n=1 מקבלים 1<1 שאינו נכון — אין אפילו בסיס.

למה זה קורה?

לא בודקים אם הטענה בכלל נכונה לפני שמנסים אינדוקציה.

איך מתקנים?

אינדוקציה מוכיחה טענות נכונות. אם הבסיס נכשל מיד (כמו

n^{2}<n

עבור

n=1)

, הטענה פשוט שגויה.

סיכום

מה למדנו?

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

כל הכבוד! עכשיו אתם מבינים את הלוגיקה של האינדוקציה ומוכנים ליישם אותה.

תרגול נוסף

עברו לתרגול כדי להתאמן על זיהוי שלב הבסיס, שלב הצעד וזיהוי הוכחות פסולות!

עיקרון האינדוקציה: שלב הבסיס ושלב הצעד

עיקרון האינדוקציה: שלב הבסיס ושלב הצעד

מבוא

הרעיון המרכזי

דימוי הדומינו

דוגמאות מפורטות

דוגמה 1: זיהוי שלב הבסיס

מהו שלב הבסיס בהוכחת 1+2+…+n=n(n+1)21+2+\ldots+n = \frac{n(n+1)}{2}1+2+…+n=2n(n+1)​?

דוגמה 2: ניסוח שלב הצעד

כיצד מנסחים את שלב הצעד עבור 1+2+…+n=n(n+1)21+2+\ldots+n = \frac{n(n+1)}{2}1+2+…+n=2n(n+1)​?

דוגמה 3: הוכחה ויזואלית — משולש נקודות

במשולש נקודות, שורה i מכילה i נקודות. הוכיחו שב-n השורות הראשונות יש n(n+1)2\frac{n(n+1)}{2}2n(n+1)​ נקודות

דוגמה 4: צעד תקין אך בסיס שנכשל

מדוע ההוכחה ש-2+4+…+2n=n2+n+12+4+\ldots+2n = n^{2}+n+12+4+…+2n=n2+n+1 פסולה?

טעויות נפוצות

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

טעות נפוצה: מדלגים על שלב הבסיס

טעות נפוצה: מבלבלים בין ההנחה לבין הטענה הכללית

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

סיכום

תרגול נוסף

מהו שלב הבסיס בהוכחת $1+2+\ldots+n = \frac{n(n+1)}{2}$ ?

כיצד מנסחים את שלב הצעד עבור $1+2+\ldots+n = \frac{n(n+1)}{2}$ ?

במשולש נקודות, שורה i מכילה i נקודות. הוכיחו שב-n השורות הראשונות יש $\frac{n(n+1)}{2}$ נקודות

מדוע ההוכחה ש- $2+4+\ldots+2n = n^{2}+n+1$ פסולה?