The principle of induction

On elev, this lesson comes with exercises checked instantly, a hint when your child gets stuck, and progress tracking.

Practise on elev

Automatic translation, not reviewed, of the Hebrew lesson your child follows at school.

חשבו את הסכומים 11, 1+21+2, 1+2+31+2+3, 1+2+3+41+2+3+4 וכן הלאה. יוצא 1,3,6,10,151, 3, 6, 10, 15. נראה שהסכום של nn המספרים הראשונים הוא n(n+1)2\frac{n(n+1)}{2}. בדקנו חמישה ערכים. אבל איך יודעים שהנוסחה נכונה גם עבור n=1000n=1000, ועבור כל nn?

113263104155+2+3+4+5…
כל סכום הוא הסכום הקודם ועוד המספר הבא: Sn+1=Sn+(n+1)S_{n+1}=S_n+(n+1). הקשר הזה בין סכום לסכום שאחריו הוא הבסיס של האינדוקציה.

מהו S6=1+2+⋯+6S_6=1+2+\dots+6? חשבו פעם מ-S5=15S_5=15 ופעם בנוסחה n(n+1)2\frac{n(n+1)}{2}.

Show the answer and the solution

S6=15+6=21S_6=15+6=21, ובנוסחה 6⋅72=21\frac{6 \cdot 7}{2}=21. שתי הדרכים נותנות אותו מספר: הנוסחה עברה מ-55 ל-66.

שורה של אבני דומינו

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

שלושת השלבים בכתיבה

11

בדיקה: מציבים n=1n=1 בשני האגפים ומראים שהם שווים

22

הנחה: מניחים שהטענה נכונה עבור n=kn=k (הנחת האינדוקציה)

33

הוכחה: מוכיחים את הטענה עבור n=k+1n=k+1, בעזרת ההנחה

הוכחה: 1+2+⋯+n=n(n+1)21+2+\dots+n=\frac{n(n+1)}{2}

nn מספר טבעי

1+2+⋯+n=n(n+1)21+2+\dots+n=\frac{n(n+1)}{2} לכל nn טבעי

n=1n=1: אגף שמאל 11, אגף ימין 1⋅22=1\frac{1 \cdot 2}{2}=1

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

1+2+⋯+k=k(k+1)21+2+\dots+k=\frac{k(k+1)}{2}

הנחת האינדוקציה

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

מציבים את ההנחה במקום kk המחוברים הראשונים

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

מכנה משותף, ואז הוצאת הגורם המשותף (k+1)(k+1)

(k+1)(k+2)2\frac{(k+1)(k+2)}{2} היא הנוסחה עבור n=k+1n=k+1

מציבים n=k+1n=k+1 ב-n(n+1)2\frac{n(n+1)}{2} ומקבלים אותו ביטוי

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

לפני שמתחילים את שלב 3, כותבים את המטרה. מהי הנוסחה עבור n=k+1n=k+1?

Show the answer and the solution

1+2+⋯+(k+1)=(k+1)(k+2)21+2+\dots+(k+1)=\frac{(k+1)(k+2)}{2}. מציבים k+1k+1 במקום כל nn בנוסחה, גם בתוך הסוגריים: n+1n+1 הופך ל-k+2k+2.

לכתוב את המטרה לפני החישוב

הטענה: 2+4+6+⋯+2n=n(n+1)2+4+6+\dots+2n=n(n+1). מה כותבים בשלב ההוכחה?

2+4+⋯+2k=k(k+1)2+4+\dots+2k=k(k+1)

הנחת האינדוקציה

2+4+⋯+2k+2(k+1)=(k+1)(k+2)2+4+\dots+2k+2(k+1)=(k+1)(k+2)

המטרה: מציבים n=k+1n=k+1. האיבר החדש הוא 2(k+1)2(k+1)

k(k+1)+2(k+1)=(k+1)(k+2)k(k+1)+2(k+1)=(k+1)(k+2)

מציבים את ההנחה ומוציאים גורם משותף (k+1)(k+1). הגענו למטרה

הנחת האינדוקציה היא הנחה, לא מה שמוכיחים. בשלב 3 חייבים להשתמש בה. הוכחה שלא משתמשת בהנחה בכלל היא סימן שמשהו חסר. בבגרות הופיעו בעבר גם טענות על התחלקות (למשל ש-4n−14^n-1 מתחלק ב-33), אבל השנה הן לא נלמדות. בפרק הזה נוכיח סכומים, נוסחאות של סדרות ונזהה הוכחות שגויות.

שתי הטעויות הנפוצות בשלב ההוכחה.

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

מציבים k+1k+1 במקום nn בכל מקום בנוסחה. לא מוסיפים 11 לתוצאה.

P(1), P(2), P(3) ✓ ⇒ P(n)P(1),\ P(2),\ P(3) \ \checkmark \ \Rightarrow \ P(n)
P(1) + (P(k)⇒P(k+1))P(1) \ \text{+} \ \big(P(k) \Rightarrow P(k+1)\big)

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

Exercises

Exercise 1

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

  1. שאם הטענה נכונה עבור n=kn=k אז היא נכונה עבור n=k+1n=k+1
  2. שהטענה נכונה עבור n=kn=k
  3. שהטענה נכונה עבור n=1n=1, n=2n=2 ו-n=3n=3
  4. שהטענה נכונה עבור n=1n=1, ושאם היא נכונה עבור n=kn=k אז היא נכונה עבור n=k+1n=k+1
Show the answer and the solution

Answer: D שהטענה נכונה עבור n=1n=1, ושאם היא נכונה עבור n=kn=k אז היא נכונה עבור n=k+1n=k+1

Worked solution:

P(1)P(1)

הבסיס

P(k)⇒P(k+1)P(k) \Rightarrow P(k+1)

הצעד

הנכונה: בסיס וצעד יחד. שלוש בדיקות אינן הוכחה. צעד בלי בסיס לא מתחיל. ו-«נכונה עבור n=kn=k» זו ההנחה, לא ההוכחה.

Check the answer on elev

Exercise 2

הטענה היא 1+2+⋯+n=n(n+1)21+2+\dots+n=\frac{n(n+1)}{2}. מה צריך להוכיח עבור n=k+1n=k+1?

  1. 1+2+⋯+k=(k+1)(k+2)21+2+\dots+k=\frac{(k+1)(k+2)}{2}
  2. 1+2+⋯+(k+1)=k(k+1)2+11+2+\dots+(k+1)=\frac{k(k+1)}{2}+1
  3. 1+2+⋯+(k+1)=(k+1)k21+2+\dots+(k+1)=\frac{(k+1)k}{2}
  4. 1+2+⋯+(k+1)=(k+1)(k+2)21+2+\dots+(k+1)=\frac{(k+1)(k+2)}{2}
Show the answer and the solution

Answer: D 1+2+⋯+(k+1)=(k+1)(k+2)21+2+\dots+(k+1)=\frac{(k+1)(k+2)}{2}

Worked solution:

n→k+1:n+1→k+2n \to k+1: \quad n+1 \to k+2

מציבים בכל מקום

הנכונה: (k+1)(k+2)2\frac{(k+1)(k+2)}{2}. מי שבחר k(k+1)2+1\frac{k(k+1)}{2}+1 הוסיף 11 לתוצאה במקום להציב. בתשובה האחרונה n+1n+1 לא הפך ל-k+2k+2.

Check the answer on elev

Exercise 3

לפי הנוסחה 1+2+⋯+n=n(n+1)21+2+\dots+n=\frac{n(n+1)}{2}, חשבו את 1+2+3+⋯+501+2+3+\dots+50.

Show the answer and the solution

Answer: 1275

Worked solution:

n=50n=50

יש 50 מחוברים

50⋅512=1275\frac{50 \cdot 51}{2}=1275

מציבים

הנוסחה שהוכחנו חוסכת חיבור של חמישים מספרים. הטעות הנפוצה: לשכוח לחלק ב-22 ולקבל 25502550.

Check the answer on elev

Exercise 4

הוכיחו או הפריכו: אם בדקנו שהטענה נכונה עבור n=1,2,3,…,100n=1, 2, 3, \dots, 100, היא נכונה לכל nn טבעי.

Show the answer and the solution

Answer: False

Worked solution:

P(1),…,P(100)P(1), \dots, P(100)

מאה בדיקות

P(101) ?P(101) \ ?

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

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

Check the answer on elev

Exercise 5

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

2+4+⋯+2k+2(k+1)=k(k+1)+2+4+\dots+2k+2(k+1)=k(k+1)+ ____ (k+1)=(k+1)(k+(k+1)=(k+1)(k+ ____ ))

Show the answer and the solution

Answer: 2+4+⋯+2k+2(k+1)=k(k+1)+2+4+\dots+2k+2(k+1)=k(k+1)+ 2 (k+1)=(k+1)(k+(k+1)=(k+1)(k+ 2 ))

Worked solution:

2+4+⋯+2k=k(k+1)2+4+\dots+2k=k(k+1)

הנחת האינדוקציה

k(k+1)+2(k+1)k(k+1)+2(k+1)

מוסיפים את האיבר החדש

=(k+1)(k+2)=(k+1)(k+2)

גורם משותף (k+1)(k+1)

(k+1)(k+2)(k+1)(k+2) היא בדיוק n(n+1)n(n+1) עבור n=k+1n=k+1. המלכודת: לפתוח סוגריים ל-k2+3k+2k^2+3k+2 ולא לזהות את המטרה. גורם משותף מראה אותה מיד.

Check the answer on elev

Exercise 6

מיינו כל משפט לשלב שבו הוא נכתב, בהוכחה של 1+3+5+⋯+(2n−1)=n21+3+5+\dots+(2n-1)=n^2.

  • בסיס (בדיקה)
  • צעד (הנחה והוכחה)
  • 1=121=1^2
  • k2+(2k+1)=(k+1)2k^2+(2k+1)=(k+1)^2
  • מציבים n=1n=1 בשני האגפים
  • נוכיח עבור n=k+1n=k+1
  • נניח 1+3+⋯+(2k−1)=k21+3+\dots+(2k-1)=k^2
Show the answer and the solution

Answer: 1=121=1^2 — בסיס (בדיקה) · מציבים n=1n=1 בשני האגפים — בסיס (בדיקה) · נניח 1+3+⋯+(2k−1)=k21+3+\dots+(2k-1)=k^2 — צעד (הנחה והוכחה) · k2+(2k+1)=(k+1)2k^2+(2k+1)=(k+1)^2 — צעד (הנחה והוכחה) · נוכיח עבור n=k+1n=k+1 — צעד (הנחה והוכחה)

Worked solution:

1=121=1^2

n=1n=1: הבסיס

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

הצעד

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

Check the answer on elev

Exercise 7

לפניכם שלב ההוכחה של 1+2+⋯+n=n(n+1)21+2+\dots+n=\frac{n(n+1)}{2}. שורה אחת שגויה. מצאו אותה.

1+2+⋯+k=k(k+1)21+2+\dots+k=\frac{k(k+1)}{2}
1+2+⋯+(k+1)=k(k+1)2+(k+1)1+2+\dots+(k+1)=\frac{k(k+1)}{2}+(k+1)
=k(k+1)+(k+1)2=\frac{k(k+1)+(k+1)}{2}
=(k+1)(k+2)2=\frac{(k+1)(k+2)}{2}
Show the answer and the solution

Answer: =k(k+1)+(k+1)2=\frac{k(k+1)+(k+1)}{2} → =k(k+1)+2(k+1)2=\frac{k(k+1)+2(k+1)}{2}

Worked solution:

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

מכנה משותף

כדי לחבר (k+1)(k+1) לשבר שמכנהו 22, כופלים את (k+1)(k+1) ב-22. השורה האחרונה נכונה, אבל היא לא נובעת מהשורה השגויה.

Check the answer on elev

Exercise 8

סדרו את שלבי ההוכחה של 2+4+⋯+2n=n(n+1)2+4+\dots+2n=n(n+1).

  • בודקים עבור n=1n=1: 2=1⋅22=1 \cdot 2
  • כותבים את המטרה: 2+4+⋯+2(k+1)=(k+1)(k+2)2+4+\dots+2(k+1)=(k+1)(k+2)
  • מוציאים גורם משותף ומקבלים (k+1)(k+2)(k+1)(k+2)
  • מניחים: 2+4+⋯+2k=k(k+1)2+4+\dots+2k=k(k+1)
  • מציבים את ההנחה: k(k+1)+2(k+1)k(k+1)+2(k+1)
Show the answer and the solution

Answer: בודקים עבור n=1n=1: 2=1⋅22=1 \cdot 2 · מניחים: 2+4+⋯+2k=k(k+1)2+4+\dots+2k=k(k+1) · כותבים את המטרה: 2+4+⋯+2(k+1)=(k+1)(k+2)2+4+\dots+2(k+1)=(k+1)(k+2) · מציבים את ההנחה: k(k+1)+2(k+1)k(k+1)+2(k+1) · מוציאים גורם משותף ומקבלים (k+1)(k+2)(k+1)(k+2)

Worked solution:

P(1)P(1)

בסיס

P(k)P(k)

הנחה

P(k+1)P(k+1)

מטרה, ואז חישוב

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

Check the answer on elev

Exercise 9

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

  • nn מספר טבעי

2+4+⋯+2n=n(n+1)2+4+\dots+2n=n(n+1)

Show the answer and the solution
  1. 2=1⋅22=1 \cdot 2 — בדיקה עבור n=1n=1
  2. 2+4+⋯+2k=k(k+1)2+4+\dots+2k=k(k+1) — הנחת האינדוקציה
  3. 2+4+⋯+2k+2(k+1)=k(k+1)+2(k+1)2+4+\dots+2k+2(k+1)=k(k+1)+2(k+1) — מוסיפים את האיבר ה-(k+1)(k+1) ומציבים את ההנחה
  4. k(k+1)+2(k+1)=(k+1)(k+2)k(k+1)+2(k+1)=(k+1)(k+2) — הוצאת גורם משותף (k+1)(k+1)
  5. 2+4+⋯+2(k+1)=(k+1)(k+2)2+4+\dots+2(k+1)=(k+1)(k+2) — כלל המעבר: זו הטענה עבור n=k+1n=k+1

Worked solution:

2=1⋅22=1 \cdot 2

בסיס

k(k+1)+2(k+1)=(k+1)(k+2)k(k+1)+2(k+1)=(k+1)(k+2)

צעד

האיבר ה-(k+1)(k+1) הוא 2(k+1)2(k+1), לא 22. המלכודת: להוסיף רק את המספר 22.

Check the answer on elev

Keep practising on elev

Videos, instant checking and a path that follows your child's pace, for every chapter of their grade.

Practise on elevDiscover elev for this grade