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

מבוא

מטרות השיעור

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

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

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

הכלי האלגברי המרכזי

אם A מתחלק ב-d וגם B מתחלק ב-d, אז A+B מתחלק ב-d.

בשלב הצעד נכתוב את הביטוי החדש בצורה: $(הביטוי עבור k) + (שארית שמתחלקת ב- d)$

לחזקות נשתמש בטריק: $a^{k + 1} = a \cdot a^{k}$ , ואז "מוסיפים ומחסרים" כדי לבודד את הביטוי מהמקרה הקודם.

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

דוגמה 1: התחלקות חזקה

הוכיחו: $4^{n} - 1$ מתחלק ב-3 לכל n טבעי

4^{k + 1} - 1 = 4 (4^{k} - 1) + 3

בסיס $(n=1)$

4^{1} - 1 = 3

, ו-3 מתחלק ב-3. הבסיס מתקיים.

בדיקה מהירה

מוכיחים ש- $4^n - 1$ מתחלק ב-3. בשלב הצעד מניחים ש- $4^k - 1$ מתחלק ב-3. כיצד כדאי לכתוב את $4^(k+1) - 1$ כדי להיעזר בהנחה?

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

דוגמה 2: התחלקות פולינומית

הוכיחו: $n^{2} + n$ מתחלק ב-2 לכל n טבעי

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

בסיס $(n=1)$

1^{2} + 1 = 2

, ו-2 מתחלק ב-2. הבסיס מתקיים.

דוגמה 3: התחלקות ב-3 (פולינום)

הוכיחו: $n^{3} + 2n$ מתחלק ב-3 לכל n טבעי

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

בסיס $(n=1)$

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

, ו-3 מתחלק ב-3. הבסיס מתקיים.

בדיקה מהירה

מוכיחים ש- $n^{3}+2n$ מתחלק ב-3. בשלב הצעד מקבלים $(k+1)^{3}+2(k+1) = (k^{3}+2k) + 3k^{2} + 3k + 3$ . מדוע הביטוי כולו מתחלק ב-3?

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

דוגמה 4: התחלקות ב-6 (שתי דרכים)

הוכיחו: $n^{3} - n$ מתחלק ב-6 לכל n טבעי

(k + 1)^{3} - (k + 1) = (k^{3} - k) + 3 k (k + 1)

אפשר להוכיח זאת גם ישירות: $n^{3} - n = (n - 1) n (n + 1)$ — מכפלת שלושה עוקבים, ולכן מתחלקת ב-6.

בסיס $(n=1)$

1^{3} - 1 = 0

, ו-0 מתחלק ב-6. הבסיס מתקיים.

תשובה מספרית

מוכיחים באינדוקציה ש- $n^{3}-n$ מתחלק ב-6 לכל n טבעי. מה ערך הביטוי $n^{3}-n$ בשלב הבסיס $(n=1)$ ?

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

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

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

5^{k + 1} - 1 = 5 \cdot 5^{k} - 1 = 5 (5^{k} - 1) + 4

ה-+4 נובע מ--5+4=-1: הוספנו וחיסרנו 5.

למה זה קורה?

תלמידים פותחים את הביטוי עבור

k+1

אך לא מזהים בתוכו את הביטוי עבור k.

איך מתקנים?

לחזקות:

a^(k+1) = a \cdot a^k

, ואז מוסיפים ומחסרים כדי לקבל

a^k - 1

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

טעות נפוצה: הסקה מדוגמאות במקום הוכחה

גם אם $7^{n} - 1$ מתחלק ב-6 עבור עשרות ערכים, רק שלב הצעד מבטיח את כל ה-n-ים.

למה זה קורה?

בודקים שהביטוי מתחלק עבור

n=1,2,3

ומסיקים שהוא מתחלק לכל n.

איך מתקנים?

בדיקת מקרים תומכת בהשערה אך אינה מוכיחה. נדרש שלב צעד שמראה שאם המקרה ה-k מתחלק, גם ה-

(k+1)

מתחלק.

בדיקה מהירה

תלמיד 'הוכיח' ש- $7^n - 1$ מתחלק ב-6 כך: 'בדקתי $n=1 ($ קיבלתי $6), n=2 ($ קיבלתי $48), n=3 ($ קיבלתי 342), וכולם מתחלקים ב-6, לכן הטענה נכונה לכל n.' מה הפגם בהוכחה?

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

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

$n^{3} - n$ הוא הכפולה; 6 הוא המחלק. כלומר $n^{3} - n = 6 m$ עבור מספר שלם m.

למה זה קורה?

כותבים '6 מתחלק ב-

(n^{3}-n)'

במקום

'(n^{3}-n)

מתחלק ב-6'.

איך מתקנים?

'A מתחלק ב-B' פירושו ש-A הוא כפולה של B (B הוא המחלק). שימו לב מי מתחלק במי.

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

ב- $n^{3} - n$ : צריך גם ש-3k(k+1) יתחלק ב-6, ולכן מנמקים ש-k(k+1) זוגי.

למה זה קורה?

מבודדים את הביטוי הקודם אך לא בודקים שהשארית מתחלקת ב-d.

איך מתקנים?

צריך ששני החלקים יתחלקו ב-d: הביטוי מההנחה והשארית. רק אז הסכום מתחלק ב-d.

סיכום

מה למדנו?

בטענת התחלקות מוכיחים שביטוי מתחלק ב-d לכל n טבעי.
טכניקת הבידוד: כותבים את המקרה ה-(k+1) כ"ביטוי מההנחה" ועוד "שארית שמתחלקת ב-d".
לחזקות: $a^{k + 1} = a \cdot a^{k}$ , מוסיפים ומחסרים כדי לבודד.
כלל מפתח: סכום של שני מספרים שמתחלקים ב-d מתחלק ב-d.
בדיקת דוגמאות אינה הוכחה — תמיד מציינים בסיס, צעד והסקה.

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

תרגול נוסף

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

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

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

מבוא

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

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

דוגמה 1: התחלקות חזקה

הוכיחו: 4n−14^{n} - 14n−1 מתחלק ב-3 לכל n טבעי

דוגמה 2: התחלקות פולינומית

הוכיחו: n2+nn^{2} + nn2+n מתחלק ב-2 לכל n טבעי

דוגמה 3: התחלקות ב-3 (פולינום)

הוכיחו: n3+2nn^{3} + 2nn3+2n מתחלק ב-3 לכל n טבעי

דוגמה 4: התחלקות ב-6 (שתי דרכים)

הוכיחו: n3−nn^{3} - nn3−n מתחלק ב-6 לכל n טבעי

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

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

טעות נפוצה: הסקה מדוגמאות במקום הוכחה

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

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

סיכום

תרגול נוסף

הוכיחו: $4^{n} - 1$ מתחלק ב-3 לכל n טבעי

הוכיחו: $n^{2} + n$ מתחלק ב-2 לכל n טבעי

הוכיחו: $n^{3} + 2n$ מתחלק ב-3 לכל n טבעי

הוכיחו: $n^{3} - n$ מתחלק ב-6 לכל n טבעי