דילוג לתוכן המרכזי

סיכום אינדוקציה מתמטית

מתמטיקה כיתה י"א 5 יח"ל · 6 נושאים

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

טענה שתלויה במספר טבעי

יש טענות שיש בהן משתנה nn, למשל "1+3+5+⋯+(2n−1)=n21+3+5+\dots+(2n-1)=n^2" או "n3+2nn^3+2n מתחלק ב-33". לכל nn שמציבים מקבלים טענה אחרת: עבור n=1n=1, עבור n=2n=2, וכן הלאה.

במדויק: טענה שתלויה במספר טבעי היא טענה עם משתנה nn, כך שלכל מספר טבעי n=1,2,3,…n=1,2,3,\dots מתקבלת טענה מסוימת, שהיא נכונה או לא נכונה. הטענה "לכל nn טבעי" נכונה רק אם היא נכונה עבור כל אחד מהמספרים הטבעיים, בלי יוצא מן הכלל.

המספרים הטבעיים הם 1,2,3,…1,2,3,\dots, ויש אינסוף מהם. לכן אי אפשר לבדוק אותם אחד אחד: גם אם בדקנו מיליון מקרים, יכול להיות שהמקרה הבא נכשל. הוכחה באינדוקציה היא שיטה שמכסה את כל המקרים בבת אחת.

nnהטענה 1+3+⋯+(2n−1)=n21+3+\dots+(2n-1)=n^2
111=11=1
221+3=41+3=4
331+3+5=91+3+5=9

תזכורת: סדרה לפי מקום ולפי כלל נסיגה

סדרה היא רשימה של מספרים לפי הסדר: a1,a2,a3,…a_1,a_2,a_3,\dots. אפשר לתת אותה בשתי דרכים: נוסחה שנותנת כל איבר לפי המקום שלו, או איבר ראשון וכלל שמחשב כל איבר מהאיבר שלפניו.

במדויק: סדרה היא פונקציה שמוגדרת על המספרים הטבעיים: לכל מקום nn יש איבר אחד ana_n (מסמנים גם a(n)a(n)).

- הגדרה לפי מקום: נוסחה an=f(n)a_n=f(n), למשל an=n2−4n+5a_n=n^2-4n+5.

- הגדרה בכלל נסיגה: האיבר הראשון a1a_1, וכלל שמחשב את an+1a_{n+1} מתוך ana_n (ואולי גם מתוך nn), למשל a1=2, an+1=an+2n−3a_1=2,\ a_{n+1}=a_n+2n-3.

הגרף של סדרה הוא אוסף של נקודות נפרדות (n,an)(n,a_n), כי nn מקבל רק ערכים טבעיים. בגרף: הסדרה an=n2−4n+5a_n=n^2-4n+5, שאיבריה הראשונים 2,1,2,5,102,1,2,5,10. הקו המקווקו רק מראה על איזו עקומה הנקודות יושבות. את אותה סדרה נותן גם הכלל a1=2, an+1=an+2n−3a_1=2,\ a_{n+1}=a_n+2n-3.

0123456246810(1,2)(2,1)(3,2)(4,5)(5,10)

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

הוכחה באינדוקציה

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

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

למה זה עובד: לפי (1) הטענה נכונה עבור 11. לפי (2) עם k=1k=1, היא נכונה עבור 22. לפי (2) עם k=2k=2, היא נכונה עבור 33, וכן הלאה. כך מגיעים לכל מספר טבעי.

שלב (2) הוא טענה מהסוג "אם... אז...". כשמוכיחים אותו לא יודעים עדיין אם הטענה נכונה עבור kk: רק מראים שאם היא נכונה עבור kk, אז היא נכונה גם עבור k+1k+1.

עבורלמה הטענה נכונה
n=1n=1שלב הבסיס
n=2n=2שלב הצעד עם k=1k=1
n=3n=3שלב הצעד עם k=2k=2
n=4n=4שלב הצעד עם k=3k=3

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

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

1. שלב הבסיס: הטענה נכונה עבור n=1n=1.

2. שלב הצעד: לכל kk טבעי, אם הטענה נכונה עבור kk, אז היא נכונה עבור k+1k+1.

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

דרך הפתרון

מבנה הוכחה באינדוקציה

כשצריך להוכיח טענה לכל nn טבעי:

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

2. שלב הצעד - הנחה: הטענה נכונה עבור kk טבעי כלשהו. כותבים אותה עם kk במקום nn.

3. שלב הצעד - צריך להוכיח: כותבים את הטענה עם k+1k+1 במקום nn.

4. שלב הצעד - הוכחה: מתחילים מאגף אחד של הטענה עבור k+1k+1, משתמשים בהנחה, ומגיעים לאגף השני.

5. שלב ההסקה: "לפי עקרון האינדוקציה, הטענה נכונה לכל nn טבעי."

שים לב

ההנחה "נכון עבור kk מסוים כלשהו" היא לא הטענה שמוכיחים ("לכל nn"). היא רק חלק משלב הצעד, ומשתמשים בה כדי להגיע ל-k+1k+1.

שים לב

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

שים לב

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

דוגמה - הוכחה מלאה בשלושת השלבים

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

2+4+6+⋯+2n=n(n+1)2+4+6+\dots+2n=n(n+1)
פתרון

1. נתון: הטענה 2+4+⋯+2n=n(n+1)2+4+\dots+2n=n(n+1). המטרה: להוכיח אותה לכל nn טבעי.

2. שלב הבסיס (n=1n=1): באגף שמאל יש איבר אחד: 22. באגף ימין: 1⋅(1+1)=21\cdot(1+1)=2. האגפים שווים.

3. הנחה: עבור kk טבעי כלשהו מתקיים 2+4+⋯+2k=k(k+1)2+4+\dots+2k=k(k+1).

4. צריך להוכיח: 2+4+⋯+2k+2(k+1)=(k+1)(k+2)2+4+\dots+2k+2(k+1)=(k+1)(k+2).

5. הוכחה: מפרידים את האיבר האחרון ומשתמשים בהנחה:

2+4+⋯+2k⏟k(k+1)+2(k+1)=k(k+1)+2(k+1)=(k+1)(k+2)\underbrace{2+4+\dots+2k}_{k(k+1)}+2(k+1)=k(k+1)+2(k+1)=(k+1)(k+2)

בסוף הוצאנו את (k+1)(k+1) כגורם משותף.

6. שלב ההסקה: הטענה נכונה עבור n=1n=1, והוכחנו שאם היא נכונה עבור kk אז היא נכונה עבור k+1k+1. לפי עקרון האינדוקציה, היא נכונה לכל nn טבעי.

תשובה

הטענה נכונה לכל nn טבעי.

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

2. הוכחת נוסחאות סכום

סכום של nn איברים

בסכום כמו 1+3+5+⋯+(2n−1)1+3+5+\dots+(2n-1) מספר המחוברים תלוי ב-nn: עבור n=1n=1 יש מחובר אחד, עבור n=2n=2 שניים, וכן הלאה. הביטוי (2n−1)(2n-1) שבסוף הוא המחובר האחרון, והוא גם הנוסחה של כל מחובר לפי המקום שלו.

במדויק: אם ana_n סדרה, SnS_n הוא סכום nn האיברים הראשונים שלה: Sn=a1+a2+⋯+anS_n=a_1+a_2+\dots+a_n. האיבר הראשון קבוע, וכש-nn גדל ב-11 נוסף לסכום בדיוק איבר אחד: an+1a_{n+1}. עבור n=1n=1 הסכום הוא האיבר הראשון בלבד: S1=a1S_1=a_1.

כך נראה הסכום 1+3+5+⋯+(2n−1)1+3+5+\dots+(2n-1) עבור nn הראשונים. בכל שורה נוסף מחובר אחד, והוא שווה ל-2n−12n-1 עם ה-nn של השורה.

nnSnS_nהמחובר שנוסף
111111
221+31+333
331+3+51+3+555
441+3+5+71+3+5+777

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

הקשר בין Sk+1S_{k+1} ל-SkS_k

Sk+1=Sk+ak+1S_{k+1}=S_k+a_{k+1}

כאשר ak+1a_{k+1} הוא המחובר האחרון בסכום עם k+1k+1 איברים: מציבים k+1k+1 במקום nn בנוסחה של המחובר.

דרך הפתרון

הוכחת נוסחת סכום באינדוקציה

כשצריך להוכיח a1+a2+⋯+an=f(n)a_1+a_2+\dots+a_n=f(n) לכל nn טבעי:

1. מזהים את המחובר הכללי ana_n (הביטוי האחרון באגף שמאל), וכותבים את ak+1a_{k+1}.

2. שלב הבסיס: באגף שמאל רק a1a_1, ובאגף ימין f(1)f(1). בודקים שהם שווים.

3. הנחה: a1+⋯+ak=f(k)a_1+\dots+a_k=f(k).

4. צריך להוכיח: a1+⋯+ak+ak+1=f(k+1)a_1+\dots+a_k+a_{k+1}=f(k+1). כדאי לפשט מראש את f(k+1)f(k+1), כדי לדעת לאן מגיעים.

5. הוכחה: מחליפים את a1+⋯+aka_1+\dots+a_k ב-f(k)f(k) לפי ההנחה, מוסיפים ak+1a_{k+1} ומפשטים עד f(k+1)f(k+1).

6. שלב ההסקה: לפי עקרון האינדוקציה, הנוסחה נכונה לכל nn טבעי.

שים לב

ב-ak+1a_{k+1} מציבים k+1k+1 במקום כל nn. ב-(2n−1)(2n-1) המחובר הבא הוא 2(k+1)−1=2k+12(k+1)-1=2k+1, ולא 2k−1+12k-1+1.

שים לב

כש-f(k)f(k) ו-ak+1a_{k+1} חולקים גורם משותף, כמו (k+1)(k+1), מוציאים אותו לפני שפותחים סוגריים. כך מגיעים מהר לצורה של f(k+1)f(k+1).

דוגמה - נוסחת סכום של מכפלות n(n+1)n(n+1)

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

1⋅2+2⋅3+3⋅4+⋯+n(n+1)=n(n+1)(n+2)31\cdot2+2\cdot3+3\cdot4+\dots+n(n+1)=\frac{n(n+1)(n+2)}{3}
פתרון

1. נתון: נוסחת הסכום. המטרה: להוכיח אותה לכל nn טבעי. המחובר הכללי an=n(n+1)a_n=n(n+1), ולכן ak+1=(k+1)(k+2)a_{k+1}=(k+1)(k+2).

2. שלב הבסיס (n=1n=1): אגף שמאל: 1⋅2=21\cdot2=2. אגף ימין: 1⋅2⋅33=2\frac{1\cdot2\cdot3}{3}=2. שווים.

3. הנחה: 1⋅2+⋯+k(k+1)=k(k+1)(k+2)31\cdot2+\dots+k(k+1)=\frac{k(k+1)(k+2)}{3} עבור kk טבעי כלשהו.

4. צריך להוכיח: 1⋅2+⋯+k(k+1)+(k+1)(k+2)=(k+1)(k+2)(k+3)31\cdot2+\dots+k(k+1)+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3}.

5. הוכחה: לפי ההנחה, אגף שמאל שווה ל-

k(k+1)(k+2)3+(k+1)(k+2)=(k+1)(k+2)(k3+1)=(k+1)(k+2)(k+3)3\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=(k+1)(k+2)\left(\frac{k}{3}+1\right)=\frac{(k+1)(k+2)(k+3)}{3}

הוצאנו את (k+1)(k+2)(k+1)(k+2) כגורם משותף, וקיבלנו בדיוק את אגף ימין.

6. שלב ההסקה: לפי עקרון האינדוקציה, הנוסחה נכונה לכל nn טבעי.

תשובה

הנוסחה נכונה לכל nn טבעי.

שאלות פתוחות על הוכחת נוסחאות סכום

3. הוכחת טענות התחלקות

התחלקות

1212 מתחלק ב-44 כי 12=4⋅312=4\cdot3, ו-1414 לא מתחלק ב-44 כי בחלוקה יש שארית 22. כשאומרים ש"n3+2nn^3+2n מתחלק ב-33" מתכוונים שלכל nn טבעי התוצאה היא 33 כפול מספר שלם.

במדויק: מספר שלם aa מתחלק במספר טבעי mm (ללא שארית) אם יש מספר שלם tt כך ש-a=m⋅ta=m\cdot t. למשל 0=4⋅00=4\cdot0 ו-−8=4⋅(−2)-8=4\cdot(-2) מתחלקים ב-44.

בשלב הצעד מקבלים מההנחה שוויון כמו f(k)=m⋅tf(k)=m\cdot t, כאשר tt שלם. את השוויון הזה מכניסים לביטוי של f(k+1)f(k+1), ומראים שגם הוא mm כפול מספר שלם.

nnn3+2nn^3+2nכפולה של 33
11333⋅13\cdot1
2212123⋅43\cdot4
3333333⋅113\cdot11

סכום וכפולה של מספרים שמתחלקים ב-mm

אם a=m⋅sa=m\cdot s ו-b=m⋅tb=m\cdot t (ss, tt שלמים), אז:

- a+b=m(s+t)a+b=m(s+t) ו-a−b=m(s−t)a-b=m(s-t) מתחלקים ב-mm.

- c⋅a=m(cs)c\cdot a=m(cs) מתחלק ב-mm לכל cc שלם.

דרך הפתרון

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

כשצריך להוכיח שהביטוי f(n)f(n) מתחלק ב-mm לכל nn טבעי:

1. שלב הבסיס: מחשבים f(1)f(1) וכותבים אותו כ-mm כפול מספר שלם.

2. הנחה: f(k)=m⋅tf(k)=m\cdot t, כאשר tt מספר שלם.

3. צריך להוכיח: f(k+1)f(k+1) מתחלק ב-mm, כלומר f(k+1)=m⋅sf(k+1)=m\cdot s עבור ss שלם כלשהו.

4. הוכחה: מסדרים את f(k+1)f(k+1) כך שיופיע בו חלק מההנחה:

- פולינום ב-nn: פותחים סוגריים וכותבים f(k+1)=f(k)+Rf(k+1)=f(k)+R. מראים שהיתרה RR מתחלקת ב-mm.

- חזקה cnc^n: כותבים ck+1=c⋅ckc^{k+1}=c\cdot c^k, ומציבים את ckc^k מתוך ההנחה.

5. שלב ההסקה: לפי עקרון האינדוקציה, f(n)f(n) מתחלק ב-mm לכל nn טבעי.

שים לב

את tt מההנחה לא קובעים: הוא מספר שלם כלשהו. מההנחה 5k+3=4t5^k+3=4t מקבלים 5k=4t−35^k=4t-3, וזה מה שמציבים.

שים לב

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

דוגמה א - ביטוי פולינומי: מפרידים את f(k)f(k)

הוכיחו באינדוקציה שלכל nn טבעי, n3+2nn^3+2n מתחלק ב-33.

פתרון

1. נתון: f(n)=n3+2nf(n)=n^3+2n. המטרה: להוכיח ש-f(n)f(n) מתחלק ב-33 לכל nn טבעי.

2. שלב הבסיס (n=1n=1): 13+2⋅1=3=3⋅11^3+2\cdot1=3=3\cdot1. מתחלק ב-33.

3. הנחה: k3+2k=3tk^3+2k=3t עבור kk טבעי כלשהו, כאשר tt שלם.

4. צריך להוכיח: (k+1)3+2(k+1)(k+1)^3+2(k+1) מתחלק ב-33.

5. הוכחה: פותחים סוגריים ומקבצים את k3+2kk^3+2k:

(k+1)3+2(k+1)=k3+3k2+3k+1+2k+2=(k3+2k)+3k2+3k+3(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2=(k^3+2k)+3k^2+3k+3

לפי ההנחה זה 3t+3(k2+k+1)=3(t+k2+k+1)3t+3(k^2+k+1)=3(t+k^2+k+1). הביטוי בסוגריים שלם, ולכן הסכום מתחלק ב-33.

6. שלב ההסקה: לפי עקרון האינדוקציה, n3+2nn^3+2n מתחלק ב-33 לכל nn טבעי.

תשובה

n3+2nn^3+2n מתחלק ב-33 לכל nn טבעי.

דוגמה ב - ביטוי עם חזקה: מציבים את 5k5^k מההנחה

הוכיחו באינדוקציה שלכל nn טבעי, 5n+35^n+3 מתחלק ב-44.

פתרון

1. נתון: f(n)=5n+3f(n)=5^n+3. המטרה: להוכיח ש-f(n)f(n) מתחלק ב-44 לכל nn טבעי.

2. שלב הבסיס (n=1n=1): 51+3=8=4⋅25^1+3=8=4\cdot2. מתחלק ב-44.

3. הנחה: 5k+3=4t5^k+3=4t עבור kk טבעי כלשהו, כאשר tt שלם. לכן 5k=4t−35^k=4t-3.

4. צריך להוכיח: 5k+1+35^{k+1}+3 מתחלק ב-44.

5. הוכחה: 5k+1+3=5⋅5k+3=5(4t−3)+3=20t−12=4(5t−3)5^{k+1}+3=5\cdot5^k+3=5(4t-3)+3=20t-12=4(5t-3). המספר 5t−35t-3 שלם, ולכן הביטוי מתחלק ב-44.

6. שלב ההסקה: לפי עקרון האינדוקציה, 5n+35^n+3 מתחלק ב-44 לכל nn טבעי.

תשובה

5n+35^n+3 מתחלק ב-44 לכל nn טבעי.

שאלות פתוחות על הוכחת טענות התחלקות

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

שתי הצגות של אותה סדרה

את אותה סדרה אפשר לפעמים לתת גם בנוסחה לפי מקום וגם בכלל נסיגה. למשל, an=2n2−na_n=2n^2-n נותנת 1,6,15,28,…1,6,15,28,\dots, וגם הכלל b1=1, bn+1=bn+4n+1b_1=1,\ b_{n+1}=b_n+4n+1 נותן 1,6,15,28,…1,6,15,28,\dots. כדי לדעת שהן שוות בכל המקומות צריך הוכחה.

במדויק: שתי סדרות ana_n ו-bnb_n שוות (שתי הצגות של אותה סדרה) אם an=bna_n=b_n לכל מספר טבעי nn. התאמה במספר סופי של מקומות, גם רבים, לא מספיקה.

בגרף רואים את ארבעת האיברים הראשונים של הסדרה, כנקודות (n,an)(n,a_n) על העקומה y=2x2−xy=2x^2-x. כלל הנסיגה מחשב כל נקודה מהנקודה שלפניה, והנוסחה מחשבת כל נקודה ישירות לפי nn. הוכחה באינדוקציה מראה ששתי הדרכים נותנות את אותן נקודות לכל nn.

012345051015202530(1,1)(2,6)(3,15)(4,28)

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

האיבר הראשון a1a_1 והכלל שמחשב את an+1a_{n+1} מתוך ana_n מספיקים כדי לקבוע את כל איברי הסדרה. לכן כדי להראות שנוסחה f(n)f(n) נותנת את הסדרה, מראים שהיא מתאימה לאיבר הראשון ומקיימת את אותו כלל נסיגה.

מעבר בין שתי ההצגות

כיווןמה עושים
מנוסחה לפי מקום לכלל נסיגהמחשבים a1a_1, ומבטאים את an+1a_{n+1} בעזרת ana_n, למשל דרך an+1−ana_{n+1}-a_n
מכלל נסיגה לנוסחה לפי מקוםקשה באופן עקרוני. נדרש רק בסדרה חשבונית ובסדרה הנדסית. כשהנוסחה נתונה - מוכיחים אותה באינדוקציה
דרך הפתרון

הוכחה שנוסחה לפי מקום מתאימה לכלל נסיגה

כשנתונה סדרה בכלל נסיגה (a1a_1 ו-an+1a_{n+1} מתוך ana_n), וצריך להוכיח ש-an=f(n)a_n=f(n) לכל nn טבעי:

1. שלב הבסיס: מראים ש-a1a_1 הנתון שווה ל-f(1)f(1).

2. הנחה: ak=f(k)a_k=f(k) עבור kk טבעי כלשהו.

3. צריך להוכיח: ak+1=f(k+1)a_{k+1}=f(k+1).

4. הוכחה: כותבים ak+1a_{k+1} לפי כלל הנסיגה (בעזרת aka_k), מציבים ak=f(k)a_k=f(k) לפי ההנחה, ומפשטים עד f(k+1)f(k+1). ליד כל שוויון כותבים את הנימוק: "לפי כלל הנסיגה", "לפי ההנחה".

5. שלב ההסקה: לפי עקרון האינדוקציה, an=f(n)a_n=f(n) לכל nn טבעי.

שים לב

כך מוכיחים גם את נוסחת האיבר הכללי של סדרה חשבונית (an+1=an+da_{n+1}=a_n+d נותן an=a1+(n−1)da_n=a_1+(n-1)d) ושל סדרה הנדסית (an+1=an⋅qa_{n+1}=a_n\cdot q נותן an=a1qn−1a_n=a_1q^{n-1}).

שים לב

בשלב הצעד מתחילים מ-ak+1a_{k+1} ומשתמשים בכלל הנסיגה. לא מתחילים מ-f(k+1)f(k+1) ומניחים שהוא שווה ל-ak+1a_{k+1} - זה מה שצריך להוכיח.

דוגמה - כלל נסיגה עם כפל: נוסחה עם חזקה

סדרה מוגדרת על ידי a1=4a_1=4 ו-an+1=3an−2a_{n+1}=3a_n-2.

א. חשבו את a2a_2 ו-a3a_3.

ב. הוכיחו באינדוקציה שלכל nn טבעי an=3n+1a_n=3^n+1.

פתרון

1. א: a2=3⋅4−2=10a_2=3\cdot4-2=10, a3=3⋅10−2=28a_3=3\cdot10-2=28. הנוסחה נותנת 32+1=103^2+1=10 ו-33+1=283^3+1=28, אבל זו רק בדיקה, לא הוכחה.

2. נתון: a1=4a_1=4, an+1=3an−2a_{n+1}=3a_n-2. המטרה: an=3n+1a_n=3^n+1 לכל nn טבעי.

3. שלב הבסיס (n=1n=1): a1=4a_1=4 ו-31+1=43^1+1=4. שווים.

4. הנחה: ak=3k+1a_k=3^k+1 עבור kk טבעי כלשהו.

5. צריך להוכיח: ak+1=3k+1+1a_{k+1}=3^{k+1}+1.

6. הוכחה: ak+1=3ak−2a_{k+1}=3a_k-2 (לפי כלל הנסיגה) =3(3k+1)−2=3(3^k+1)-2 (לפי ההנחה) =3k+1+3−2=3k+1+1=3^{k+1}+3-2=3^{k+1}+1.

7. שלב ההסקה: לפי עקרון האינדוקציה, an=3n+1a_n=3^n+1 לכל nn טבעי.

תשובה

א. a2=10a_2=10, a3=28a_3=28. ב. הוכח: an=3n+1a_n=3^n+1 לכל nn טבעי.

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

5. טענות ויזואליות וגאומטריות

טענה על סדרה של ציורים

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

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

דוגמה: מעבירים nn ישרים במישור, כך שאין שני ישרים מקבילים ואין שלושה ישרים שעוברים באותה נקודה. נסמן ב-L(n)L(n) את מספר חלקי המישור. ישר אחד מחלק את המישור ל-22 חלקים, שני ישרים ל-44, ושלושה ישרים ל-77 (בציור, החלקים ממוספרים).

הישר ה-nn חותך כל אחד מ-n−1n-1 הישרים הקודמים בנקודה אחרת, ולכן הוא מחולק ל-nn חלקים. כל חלק כזה חוצה חלק מישור אחד לשניים, ולכן נוספים בדיוק nn חלקים: L(n)=L(n−1)+nL(n)=L(n-1)+n.

ABCDEG1234567

ישרים במישור

nn ישרים במישור, שאין ביניהם שניים מקבילים ואין שלושה שעוברים באותה נקודה:

•הוספת הישר ה-nn מוסיפה nn חלקי מישור: L(n)=L(n−1)+nL(n)=L(n-1)+n, עם L(1)=2L(1)=2.

•מכאן, באינדוקציה: L(n)=1+n2+n22L(n)=1+\frac{n}{2}+\frac{n^2}{2}.

דרך הפתרון

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

כשנתונה סדרה של ציורים וצריך להוכיח נוסחה Q(n)=f(n)Q(n)=f(n) לכל nn טבעי:

1. מתארים איך הציור ה-(k+1)(k+1) נבנה מהציור ה-kk, וסופרים מה נוסף. כך מקבלים כלל נסיגה: Q(k+1)Q(k+1) שווה ל-Q(k)Q(k) ועוד מה שנוסף, עם נימוק מהציור.

2. שלב הבסיס: סופרים בציור הראשון ומראים ש-Q(1)=f(1)Q(1)=f(1).

3. הנחה: Q(k)=f(k)Q(k)=f(k) עבור kk טבעי כלשהו.

4. צריך להוכיח: Q(k+1)=f(k+1)Q(k+1)=f(k+1).

5. הוכחה: לפי כלל הנסיגה, Q(k+1)Q(k+1) הוא Q(k)Q(k) ועוד מה שנוסף. לפי ההנחה מחליפים את Q(k)Q(k) ב-f(k)f(k), ומפשטים עד f(k+1)f(k+1).

6. שלב ההסקה: לפי עקרון האינדוקציה, Q(n)=f(n)Q(n)=f(n) לכל nn טבעי.

שים לב

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

שים לב

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

דוגמה - קטעים בין נקודות על מעגל

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

א. מצאו כלל נסיגה ל-S(n)S(n) ונמקו.

ב. הוכיחו באינדוקציה ש-S(n)=n(n−1)2S(n)=\frac{n(n-1)}{2} לכל nn טבעי.

פתרון

1. נתון: nn נקודות על מעגל, וכל שתיים מחוברות בקטע. המטרה: כלל נסיגה ל-S(n)S(n), והוכחה ש-S(n)=n(n−1)2S(n)=\frac{n(n-1)}{2}.

2. א: כשמוסיפים נקודה חדשה ל-kk נקודות, מחברים אותה לכל אחת מ-kk הנקודות הקיימות, והקטעים הישנים נשארים. לכן נוספים בדיוק kk קטעים: S(k+1)=S(k)+kS(k+1)=S(k)+k. בציור: 44 נקודות עם 66 קטעים, ונקודה חמישית EE שמוסיפה 44 קטעים מקווקווים.

ABCDE

3. שלב הבסיס (n=1n=1): בנקודה אחת אין קטעים: S(1)=0S(1)=0. הנוסחה: 1⋅02=0\frac{1\cdot0}{2}=0. שווים.

4. הנחה: S(k)=k(k−1)2S(k)=\frac{k(k-1)}{2} עבור kk טבעי כלשהו.

5. צריך להוכיח: S(k+1)=(k+1)k2S(k+1)=\frac{(k+1)k}{2}.

6. הוכחה: S(k+1)=S(k)+kS(k+1)=S(k)+k (לפי כלל הנסיגה) =k(k−1)2+k=\frac{k(k-1)}{2}+k (לפי ההנחה) =k(k−1)+2k2=k(k+1)2=\frac{k(k-1)+2k}{2}=\frac{k(k+1)}{2}.

7. שלב ההסקה: לפי עקרון האינדוקציה, S(n)=n(n−1)2S(n)=\frac{n(n-1)}{2} לכל nn טבעי.

תשובה

א. S(n+1)=S(n)+nS(n+1)=S(n)+n, S(1)=0S(1)=0. ב. הוכח: S(n)=n(n−1)2S(n)=\frac{n(n-1)}{2}.

שאלות פתוחות על טענות ויזואליות וגאומטריות

6. זיהוי הוכחות תקינות ומהלכים שגויים שאינם הוכחה

הוכחה תקינה ומהלך שאינו הוכחה

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

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

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

מה הוכחמה ידוע
רק בסיס (וכמה מקרים)רק המקרים שנבדקו
רק צעדכלום: יכול להיות שהטענה לא נכונה לאף nn
בסיס וצעדהטענה נכונה לכל nn טבעי

מה חסר ומה זה גורם

מה חסר בהוכחהמה יכול לקרות
שלב הבסיסשלב הצעד עובד, אבל הטענה לא נכונה (אולי לאף nn)
שלב הצעדהטענה נכונה במקרים הראשונים ונכשלת בהמשך

שני השלבים לא תלויים זה בזה: כל אחד מהם צריך הוכחה משלו.

הפרכה בדוגמה נגדית

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

שים לב

מהלכים שגויים נפוצים: מוכיחים את שלב הצעד רק עבור kk מסוים (למשל k=3k=3); מניחים את הטענה עבור k+1k+1 - מה שצריך להוכיח; או כותבים "נכון לכל nn" אחרי בדיקה של כמה מקרים בלבד.

שים לב

אם שתי סדרות מתחילות באותם איברים, זה לא אומר שהן אותה סדרה. רק הוכחה (או מציאת מקום שבו הן שונות) מכריעה.

דוגמה א - שלב הצעד עובד ושלב הבסיס נכשל

תלמיד רוצה להוכיח שלכל nn טבעי 2+4+⋯+2n=n2+n+12+4+\dots+2n=n^2+n+1. הוא מניח שהטענה נכונה עבור kk, ומקבל:

2+4+⋯+2k+2(k+1)=k2+k+1+2k+2=(k+1)2+(k+1)+12+4+\dots+2k+2(k+1)=k^2+k+1+2k+2=(k+1)^2+(k+1)+1

האם הוכיח את הטענה?

פתרון

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

2. בודקים את שלב הצעד: k2+k+1+2k+2=k2+3k+3k^2+k+1+2k+2=k^2+3k+3, וגם (k+1)2+(k+1)+1=k2+3k+3(k+1)^2+(k+1)+1=k^2+3k+3. שלב הצעד נכון.

3. בודקים את שלב הבסיס (n=1n=1): אגף שמאל 22, אגף ימין 1+1+1=31+1+1=3. 2≠32\ne3, ולכן הבסיס לא מתקיים.

4. מסקנה: בלי בסיס אין הוכחה. למעשה הטענה לא נכונה לאף nn: באינדוקציה מוכיחים ש-2+4+⋯+2n=n(n+1)=n2+n2+4+\dots+2n=n(n+1)=n^2+n לכל nn טבעי, וזה קטן ב-11 מאגף ימין.

תשובה

לא. שלב הצעד נכון, אבל שלב הבסיס נכשל (2≠32\ne3), והטענה לא נכונה לאף nn טבעי.

דוגמה ב - התאמה בשלושה מקרים בלי שלב צעד

נתונות הסדרות a1=1, an+1=2ana_1=1,\ a_{n+1}=2a_n ו-bn=n2−n+22b_n=\frac{n^2-n+2}{2}.

א. השוו את ana_n ו-bnb_n עבור n=1,2,3n=1,2,3.

ב. תלמיד הסיק מסעיף א ש-an=bna_n=b_n לכל nn טבעי. האם הוא צודק?

פתרון

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

2. א: a1=1a_1=1, a2=2a_2=2, a3=4a_3=4. b1=22=1b_1=\frac{2}{2}=1, b2=42=2b_2=\frac{4}{2}=2, b3=82=4b_3=\frac{8}{2}=4. שוות בשלושת המקומות.

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

4. בודקים את n=4n=4: a4=2⋅4=8a_4=2\cdot4=8, אבל b4=16−4+22=7b_4=\frac{16-4+2}{2}=7. מצאנו דוגמה נגדית, ולכן המסקנה לא נכונה.

תשובה

א. an=bna_n=b_n עבור n=1,2,3n=1,2,3. ב. לא: a4=8a_4=8 ו-b4=7b_4=7.

שאלות פתוחות על זיהוי הוכחות תקינות ומהלכים שגויים שאינם הוכחה

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.