Le principe de récurrence

Sur elev, cette leçon vient avec des exercices corrigés sur le moment, un indice quand votre enfant bloque et le suivi de ses progrès.

Pratiquer sur elev

Traduction automatique, non relue, de la leçon en hébreu que votre enfant suit en classe.

חשבו את הסכומים 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}.

Voir la réponse et le corrigé

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?

Voir la réponse et le corrigé

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)

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

Exercices

Exercice 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
Voir la réponse et le corrigé

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

Corrigé :

P(1)P(1)

הבסיס

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

הצעד

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

Vérifier la réponse sur elev

Exercice 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}
Voir la réponse et le corrigé

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

Corrigé :

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.

Vérifier la réponse sur elev

Exercice 3

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

Voir la réponse et le corrigé

Réponse : 1275

Corrigé :

n=50n=50

יש 50 מחוברים

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

On remplace (מציבים)

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

Vérifier la réponse sur elev

Exercice 4

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

Voir la réponse et le corrigé

Réponse : Faux

Corrigé :

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

מאה בדיקות

P(101) ?P(101) \ ?

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

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

Vérifier la réponse sur elev

Exercice 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+ ____ ))

Voir la réponse et le corrigé

Réponse : 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 ))

Corrigé :

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 ולא לזהות את המטרה. גורם משותף מראה אותה מיד.

Vérifier la réponse sur elev

Exercice 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
Voir la réponse et le corrigé

Réponse : 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 — צעד (הנחה והוכחה)

Corrigé :

1=121=1^2

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

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

הצעד

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

Vérifier la réponse sur elev

Exercice 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}
Voir la réponse et le corrigé

Réponse : =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}

Corrigé :

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

מכנה משותף

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

Vérifier la réponse sur elev

Exercice 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)
Voir la réponse et le corrigé

Réponse : בודקים עבור 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)

Corrigé :

P(1)P(1)

בסיס

P(k)P(k)

הנחה

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

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

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

Vérifier la réponse sur elev

Exercice 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)

Voir la réponse et le corrigé
  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

Corrigé :

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.

Vérifier la réponse sur elev

La suite se pratique sur elev

Vidéos, exercices corrigés sur le moment et un parcours qui suit le rythme de votre enfant, pour tous les chapitres de sa classe.

Pratiquer sur elevDécouvrir elev pour cette classe