אינדוקציה הסבר

דרך נפוצה להוכחת התחלקות היא על פי הרעיון הבא:

נניח ונתון לנו כעובדה כי:

4ⁿ מתחלק ב 3.

ומבקשים שנוכיח כי:

4^{n +1}

מתחלק ב 3.

אז כצעד ראשון נכתוב כי עלינו להוכיח כי הביטוי:

הוא שלם.

ונוכיח כי הוא שלם כך:

1.ננסה להפריד מהביטוי את 4ⁿ כי ידוע לנו שהוא מתחלק ב 3.

המשך ההפרדה תעשה על ידי הביטוי:

4 * 4ⁿ = 3 * 4ⁿ + 4ⁿ

החלק השמאלי שלם – כי 3 חלקי 3 זה שלם.

החלק הימני שם – כי זה מה שהיה נתון.

לסיכום

את השורה הזו עליכם לזכור, היא שימושית:

4 * 4ⁿ = 3 * 4ⁿ + 4ⁿ

ובנוסף

יש עוד כללים להתחלקות של מספרים, למשל:

1.מכפלת מספרים צמודים מתחלקת ב 2.
כלומר:
n (n + 1)
בטוח זוגי.

2.מכפלת 3 מספרים צמודים בטוח מתחלקת ב 6.
כלומר:
n (n + 1)(n + 2)
בטוח מתחלק ב 6.

דוגמה

הוכיחו כי עבור כל n טבעי המקיים n > 1 הביטוי

6ⁿ

מתחלק ב 9.

פתרון

שלב 1: בדיקה 

ההוכחה נדרשת עבור n > 1 שזה אומר n = 2 ומעלה.

נציב n = 2

6² = 36

מצאנו כי עבור n = 2 הביטוי מתחלק ב 9.

שלב 2: הנחה

נניח כי קיים k טבעי שעבורו

6^k

מתחלק ב 9.

שלב 3: הוכחה

נוכיח כי

6^{k+ 1}

מתחלק ב 9.

על מנת להשתמש בהנחה עלינו ליצור את 6^k :

6^{k+ 1} = 6 * 6^k

6^k מתחלק ב 9, ולכן גם כל כפולה של ביטוי זה מתחלק ב 9.

שלב 4: משפט מסכם

בדקנו שהטענה נכונה עבור n = 2.

הוכחנו שאם הטענה נכונה לאיבר מסוים היא נכונה גם לאיבר העוקב.

בכך הוכחנו באינדוקציה כי הטענה נכונה עבור n > 2 טבעי.

בחלק זה עלינו להוכיח כי כי לשתי סדרות יש איברים זהים.

שלבי הפתרון הם:

בודקים עבור n = 1

מניחים כי a_k = b_k

מוכיחים בעזרת ההנחה כי:

a_{k+ 1} = b_{k + 1}

נושא זה בחומר הלימוד אבל לא נתקלתי בשאלה כזו בבגרות.

דוגמה

נתונה הסדרה:

a_n = 3ⁿ

והסדרה

b_{n + 1} = 3b_n

b₁ = 3

הוכיחו כי הסדרות מתלכדות.

פתרון

שלב 1: נבדוק שהאיבר הראשון מתלכד

a_n = 3ⁿ

a₁ = 3¹ = b₁

האיבר הראשון בשתי הסדרות זהה.

שלב 2: נניח שעבור איבר במקום k הסדרות מתלכדות

נניח כי קיים k טבעי שעבורו הסדרות מתלכדות.

a_k = b_k

שלב 3: הוכחה לאיבר העוקב

נוכיח כי עבור האיבר שבמקום k + 1 הסדרות מתלכדות.

a_{k + 1} = 3^{k + 1}

b_{k + 2} = 3b_{k + 1}

b₁ = 3

והוכחה היא:

a_{k + 1} = 3^{k + 1} = 3 * 3^k  = 3a_k  = 3b_k = b_k+1

הוכחנו כי האיברים הנמצאים במקום k + 1 הם זהים.

a_{k + 1}  = b_k+1

שלב 4: משפט מסכם

בדקנו שהטענה נכונה עבור n = 1.

הוכחנו שאם הטענה  נכונה לאיבר מסוים היא נכונה גם לאיבר העוקב.

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

שלב 1: בדיקה

נציב n = 1

3¹ > 3 * 1 – 1

3 > 2

מצאנו כי האי שוויון נכון עבור n = 1.

שלב 2: הנחה

נניח כי קיים k טבעי המקיים:

3^k > 3k – 1

שלב 3: הוכחה

נוכיח כי:

3^{k + 1} > 3(k +1) – 1

על מנת שנוכל להשתמש בהנחה עלינו ליצור בצד שמאל את הביטוי 3^k .

 3 * 3^k > 3(k +1) – 1

נשתמש בהנחה:

 3 * (3k – 1)  > 3(k +1) – 1

מדוע יכולנו להציב ביטויים לא שווים?

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

9k – 3 > 3k + 3 – 1

9k – 3 > 3k -2

6k > 1

k > 1/6

מכוון ש k הוגדר כמספר טבעי – כלומר חיובי ושלם אי שוויון זה מתקיים.

שלב 4: משפט מסכם

נסכם במשפט: “בדקנו שהטענה נכונה עבור k=1.
ועל סמך ההנחה שהטענה נכונה עבור איבר במקום k  הוכחנו שהטענה נכונה גם עבור האיבר הבא לאחריו.
לכן הטענה

3^k > 3k – 1

נכונה עבור כל n טבעי”

בתרגיל זה נשים לב:

• לדרך שבה מציבים באי שוויון (לא עניין מורכב).

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

יש איברים שהם:

n + 1

n + 2

וכך עלינו להוסיף 1 וליצור איברים חדשים עד שנגיע לאיבר שערכו הוא 4n² + 1.

כלומר אם n = 4 אז איברי הסדרה הם:

5, 6, 7 ….. , 17

שלב א: בדיקה

נבדוק שהטענה נכונה עבור n = 1.

n + 1 + n + 2 + ….+ 3n = 4n² + n

2 + 3  = 4 + 1

5 = 5

הטענה נכונה עבור n = 1

שלב 2: הנחה

נניח כי קיים k טבעי עבורו מתקיים

k + 1 + k + 2 + ….+ 3k = 4k² + k

שלב 3: הוכחה עבור k +1

נציב k + 1 בכך מקום שבו רשום k ונקבל:

נוכיח כי מתקיים:

k +1 + 1) + (k +1 + 2) + ….+ 3k + (3k +1) + (3k + 2) + (3k + 3)= 4(k + 1)² + k + 1)

בעצם נקבל:

k +2) + (k +3) + ….+ 3k + (3k +1) + (3k + 2) + (3k + 3)= 4(k + 1)² + k + 1)

אתם יכולים לרשום את זה ישר כך, אני הוספתי את השורה העליונה כדי להסביר אך הגענו לכך.

נשים לב שבהנחה שלנו האיבר הראשון הוא k + 1 והוא לא קיים במשוואה שצריך להוכיח.

לכן כדי להציב נוסיף k  + 1 לשני צדדי המשוואה:

(k + 1) + k +2) + (k +3) + ….+ 3k + (3k +1) + (3k + 2) + (3k + 3)= 4(k + 1)² + k + 1 + (k + 1)

נציב את ההנחה:

4k² + k + (3k + 1) + (3k + 2) + (3k + 3) = 4(k + 1)² + k + 1 + (k + 1)

נפתח סוגריים בשני הצדדים ונכנס איברים:

4k² + 10k + 6 = 4(k² + 2k + 1) + 2k + 2

4k² + 10k + 7 = 4k² + 8k + 4 + 2k + 2

4k² + 10k + 6 = 4k² + 10k + 6

הוכחנו כי אי השוויון מתקיים.

שלב 4: משפט מסכם

נסכם במשפט: “בדקנו שהטענה נכונה עבור k=1.
ועל סמך ההנחה שהטענה נכונה עבור איבר במקום k  הוכחנו שהטענה נכונה גם עבור האיבר הבא לאחריו.
לכן הטענה

n + 1 + n + 2 + ….+ 3n = 4n² + n

נכונה עבור כל n טבעי”

בתרגיל זה נשים לב:

• לכך שהאיבר הראשון השתנה.
• לכך שנוספו מספר איברים ב k  + 1.