Flawed proof and counterexample

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.

תלמידה מציעה נוסחה: 1+2+⋯+n=n2+n+221+2+\dots+n=\frac{n^2+n+2}{2}. היא מראה שהצעד עובד, בחישוב נכון. הנה הסכומים האמיתיים, והנה הערכים של הנוסחה שלה. השוו את החצים.

113263104155+2+3+4+5…
הסכומים האמיתיים 1+2+⋯+n1+2+\dots+n.
214273114165+2+3+4+5…
הנוסחה המוצעת n2+n+22\frac{n^2+n+2}{2}: אותם חצים בדיוק, אבל כל ערך גדול ב-11. הצעד נכון, והבסיס לא.

הראו שהצעד של הנוסחה המוצעת עובד: אם 1+⋯+k=k2+k+221+\dots+k=\frac{k^2+k+2}{2}, אז 1+⋯+(k+1)=(k+1)2+(k+1)+221+\dots+(k+1)=\frac{(k+1)^2+(k+1)+2}{2}.

Show the answer and the solution

k2+k+22+(k+1)=k2+3k+42\frac{k^2+k+2}{2}+(k+1)=\frac{k^2+3k+4}{2}, וגם (k+1)2+(k+1)+2=k2+3k+4(k+1)^2+(k+1)+2=k^2+3k+4. הצעד עובד. אבל עבור n=1n=1: 1≠21 \neq 2. בלי בסיס אין הוכחה, גם כשהצעד מושלם.

הצעד שנשבר במעבר מ-1 ל-2

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

«הוכחה»: כל הכדורים בכל שקית הם באותו צבע

שקית עם nn כדורים

כל nn הכדורים באותו צבע

n=1n=1: כדור אחד הוא בצבע אחד

בדיקה

כל שקית עם kk כדורים היא בצבע אחד

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

בשקית עם k+1k+1 כדורים, מוציאים את הכדור הראשון: נשארים kk כדורים בצבע אחד

ההנחה

מחזירים אותו ומוציאים את האחרון: שוב kk כדורים בצבע אחד

ההנחה

לשתי הקבוצות יש כדורים משותפים, ולכן כולם באותו צבע

כלל המעבר

המסקנה שקרית, ולכן יש שגיאה. חפשו אותה בשורה האחרונה, עבור k=1k=1.

מה קורה בשורה האחרונה כש-k=1k=1, כלומר במעבר מ-11 כדור ל-22 כדורים?

Show the answer and the solution

בשקית יש שני כדורים. הקבוצה הראשונה היא כדור אחד, והשנייה היא הכדור האחר. אין כדור משותף, ולכן אין מעבר. הצעד עובד רק עבור k≥2k \geq 2, והבסיס הוא n=1n=1: שרשרת הדומינו נשברת בין האבן הראשונה לשנייה.

להפריך: מספיקה דוגמה נגדית אחת

1+2+⋯+n=2n−11+2+\dots+n=2^n-1?

הנוסחה נכונה עבור n=1n=1 ועבור n=2n=2. האם היא נכונה לכל nn?

n=1: 1=21−1\begin{aligned}n &= 1: \ 1 \\ &= 2^1-1\end{aligned}

מתקיים

n=2: 3=22−1\begin{aligned}n &= 2: \ 3 \\ &= 2^2-1\end{aligned}

מתקיים

n=3: 6≠23−1=7\begin{aligned}n &= 3: \ 6 \neq 2^3-1 \\ &= 7\end{aligned}

נכשלת. הנוסחה שגויה

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

פרמטר: קודם מציבים

בבגרות מופיעה לפעמים נוסחה עם פרמטר. מציבים n=1n=1 (ולפעמים גם n=2n=2), מוצאים את הפרמטר, ורק אז מוכיחים באינדוקציה.

1⋅2+2⋅3+⋯+n(n+1)=n(n+1)(n+a)31 \cdot 2+2 \cdot 3+\dots+n(n+1)=\frac{n(n+1)(n+a)}{3}

מצאו את aa.

n=1: 2=1⋅2⋅(1+a)3\begin{aligned}n &= 1: \ 2 \\ &= \frac{1 \cdot 2 \cdot (1+a)}{3}\end{aligned}

מציבים

1+a=3 ⇒ a=2\begin{aligned}1+a &= 3 \ \Rightarrow \ a \\ &= 2\end{aligned}

עכשיו מוכיחים באינדוקציה את n(n+1)(n+2)3\frac{n(n+1)(n+2)}{3}

טענה עבור nn זוגי: צעד של 2

הטענה 1−2+3−4+⋯+(n−1)−n=−n21-2+3-4+\dots+(n-1)-n=-\frac{n}{2} מדברת רק על nn זוגי. הבסיס הוא n=2n=2, והצעד עובר מ-kk ל-k+2k+2: מוסיפים שני מחוברים, (k+1)−(k+2)=−1(k+1)-(k+2)=-1, ו-−k2−1=−k+22-\frac{k}{2}-1=-\frac{k+2}{2}.

לפני כל הוכחה שאלו: מאיזה nn מתחילים, ומה הצעד? בדרך כלל מתחילים מ-n=1n=1 וצועדים ב-11. בטענה על זוגיים מתחילים מ-22 וצועדים ב-22.

שלוש הוכחות שנראות שלמות ואינן.

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

צעד בלי בסיס לא מוכיח דבר. הנוסחה n2+n+22\frac{n^2+n+2}{2} עוברת את הצעד ושגויה.

P(1) ✓, P(k)⇒P(k+1)  (k≥2)P(1) \ \checkmark ,\ P(k) \Rightarrow P(k+1) \ \ (k \geq 2)
P(1), P(2) ✓, P(k)⇒P(k+1)  (k≥2)P(1) ,\ P(2) \ \checkmark ,\ P(k) \Rightarrow P(k+1) \ \ (k \geq 2)

אם הצעד עובד רק מ-k=2k=2, צריך לבדוק גם את n=2n=2. אחרת השרשרת נשברת בין 11 ל-22.

n=12 ✓⇒a\begin{aligned}n &= 1 \\ 2 \ \checkmark \Rightarrow a\end{aligned}
n=1 + n=2⇒a\begin{aligned}n &= 1 \ \text{+} \ n \\ &= 2 \Rightarrow a\end{aligned}

כשהצבה אחת נותנת שני ערכים של הפרמטר, הצבה שנייה בוחרת ביניהם.

Exercises

Exercise 1

תלמיד «הוכיח» ש-1+2+⋯+n=n2+n+221+2+\dots+n=\frac{n^2+n+2}{2}: הוא הראה שאם הנוסחה נכונה עבור n=kn=k, היא נכונה עבור n=k+1n=k+1. מה חסר בהוכחה?

  1. צריך לבדוק גם את n=2n=2
  2. הבסיס: עבור n=1n=1 הנוסחה נותנת 22 ולא 11
  3. לא חסר דבר, ההוכחה נכונה
  4. הצעד אינו נכון
Show the answer and the solution

Answer: B הבסיס: עבור n=1n=1 הנוסחה נותנת 22 ולא 11

Worked solution:

n=1: 1+1+22=2≠1\begin{aligned}n &= 1: \ \frac{1+1+2}{2} \\ &= 2 \neq 1\end{aligned}

הבסיס נכשל

k2+k+22+(k+1)=(k+1)2+(k+1)+22\frac{k^2+k+2}{2}+(k+1)=\frac{(k+1)^2+(k+1)+2}{2}

הצעד נכון

הנכונה: הבסיס. הצעד נכון בחישוב, ולכן «הצעד אינו נכון» שגוי. הנוסחה גדולה ב-11 מהסכום עבור כל nn, ורק הבסיס חושף את זה.

Check the answer on elev

Exercise 2

תלמידה טוענת: 1+2+⋯+n=2n−11+2+\dots+n=2^n-1 לכל nn טבעי. מהו ה-nn הקטן ביותר שעבורו הטענה נכשלת?

Show the answer and the solution

Answer: 3

Worked solution:

n=1: 1=1\begin{aligned}n &= 1: \ 1 \\ &= 1\end{aligned}

מתקיים

n=2: 3=3\begin{aligned}n &= 2: \ 3 \\ &= 3\end{aligned}

מתקיים

n=3: 6≠7n=3: \ 6 \neq 7

נכשלת

שתי בדיקות מוצלחות אינן הוכחה. n=3n=3 היא דוגמה נגדית, ודוגמה נגדית אחת מספיקה כדי להפריך.

Check the answer on elev

Exercise 3

ידוע ש-1⋅2+2⋅3+⋯+n(n+1)=n(n+1)(n+a)31 \cdot 2+2 \cdot 3+\dots+n(n+1)=\frac{n(n+1)(n+a)}{3} לכל nn טבעי. מצאו את aa.

Show the answer and the solution

Answer: 2

Worked solution:

n=1: 2=2(1+a)3\begin{aligned}n &= 1: \ 2 \\ &= \frac{2(1+a)}{3}\end{aligned}

מציבים

1+a=3 ⇒ a=2\begin{aligned}1+a &= 3 \ \Rightarrow \ a \\ &= 2\end{aligned}

פותרים

n=2: 2+6=8=2⋅3⋅43\begin{aligned}n &= 2: \ 2+6 \\ &= 8 \\ &= \frac{2 \cdot 3 \cdot 4}{3}\end{aligned}

בדיקה

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

Check the answer on elev

Exercise 4

בהוכחה ש«כל הכדורים בכל שקית הם באותו צבע», באיזה מעבר נשבר הצעד?

  1. מ-11 כדור ל-22 כדורים
  2. בבסיס, עבור כדור אחד
  3. בכל מעבר
  4. מ-22 כדורים ל-33 כדורים
Show the answer and the solution

Answer: A מ-11 כדור ל-22 כדורים

Worked solution:

k=1: {1} {2}\begin{aligned}k &= 1: \ \{1\} \\ \ \{2\}\end{aligned}

שתי קבוצות בלי כדור משותף

k≥2k \geq 2

יש כדור משותף, והמעבר תקין

הנכונה: מ-11 ל-22. הבסיס נכון, והצעד נכון לכל k≥2k \geq 2. אבל שרשרת שנשברת במקום אחד נשברת כולה.

Check the answer on elev

Exercise 5

לפניכם «הוכחה» של 1+2+⋯+n=n2+n+221+2+\dots+n=\frac{n^2+n+2}{2}. שורה אחת שגויה. מצאו אותה.

n=1: 1=1+1+22\begin{aligned}n &= 1: \ 1 \\ &= \frac{1+1+2}{2}\end{aligned}
1+⋯+k=k2+k+221+\dots+k=\frac{k^2+k+2}{2}
1+⋯+(k+1)=k2+k+22+(k+1)=k2+3k+42\begin{aligned}1+\dots+(k+1) &= \frac{k^2+k+2}{2}+(k+1) \\ &= \frac{k^2+3k+4}{2}\end{aligned}
(k+1)2+(k+1)+22=k2+3k+42\frac{(k+1)^2+(k+1)+2}{2}=\frac{k^2+3k+4}{2}
Show the answer and the solution

Answer: n=1: 1=1+1+22n=1: \ 1=\frac{1+1+2}{2} → n=1: 1≠1+1+22=2n=1: \ 1 \neq \frac{1+1+2}{2}=2

Worked solution:

1+1+22=2\frac{1+1+2}{2}=2

אגף ימין עבור n=1n=1

הצעד כולו נכון. השגיאה היא בבדיקה: 1≠21 \neq 2. מי שכותב «בדיקה» בלי לחשב את שני האגפים מפספס בדיוק את זה.

Check the answer on elev

Exercise 6

הטענה: לכל nn זוגי, 1−2+3−4+⋯+(n−1)−n=−n21-2+3-4+\dots+(n-1)-n=-\frac{n}{2}. השלימו.

הבסיס: n=n= ____ ; במעבר מ-kk ל-k+2k+2 מוסיפים (k+1)−(k+2)=(k+1)-(k+2)= ____

Show the answer and the solution

Answer: הבסיס: n=n= 2 ; במעבר מ-kk ל-k+2k+2 מוסיפים (k+1)−(k+2)=(k+1)-(k+2)= -1

Worked solution:

n=2: 1−2=−1=−22\begin{aligned}n &= 2: \ 1-2 \\ &= -1 \\ &= -\frac{2}{2}\end{aligned}

בסיס

−k2+(k+1)−(k+2)=−k2−1=−k+22\begin{aligned}-\frac{k}{2}+(k+1)-(k+2) &= -\frac{k}{2}-1 \\ &= -\frac{k+2}{2}\end{aligned}

צעד של 2

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

Check the answer on elev

Exercise 7

מיינו: איזו הוכחה מוכיחה את הטענה לכל nn טבעי?

  • הוכחה תקינה
  • הוכחה פגומה
  • בדיקה של n=1n=1 עד n=20n=20
  • בסיס n=1n=1 ו-n=2n=2, וצעד שעובד לכל k≥2k \geq 2
  • בסיס n=1n=1, וצעד שעובד לכל k≥1k \geq 1
  • בסיס n=1n=1, וצעד שעובד רק לכל k≥2k \geq 2
  • צעד שעובד לכל k≥1k \geq 1, בלי בסיס
Show the answer and the solution

Answer: בסיס n=1n=1, וצעד שעובד לכל k≥1k \geq 1 — הוכחה תקינה · בסיס n=1n=1 ו-n=2n=2, וצעד שעובד לכל k≥2k \geq 2 — הוכחה תקינה · צעד שעובד לכל k≥1k \geq 1, בלי בסיס — הוכחה פגומה · בדיקה של n=1n=1 עד n=20n=20 — הוכחה פגומה · בסיס n=1n=1, וצעד שעובד רק לכל k≥2k \geq 2 — הוכחה פגומה

Worked solution:

P(1)⇒P(2)⇒P(3)⇒…P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \dots

השרשרת צריכה כל חוליה

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

Check the answer on elev

Exercise 8

ידוע ש-13+23+⋯+n3=n2(n+b)241^3+2^3+\dots+n^3=\frac{n^2(n+b)^2}{4} לכל nn טבעי. מצאו את bb. (רמז: n=1n=1 נותן שני ערכים.)

Show the answer and the solution

Answer: 1

Worked solution:

n=1: 1=(1+b)24 ⇒ b=1 או b=−3\begin{aligned}n &= 1: \ 1 \\ &= \frac{(1+b)^2}{4} \ \Rightarrow \ b \\ &= 1 \ \text{או} \ b \\ &= -3\end{aligned}

שני מועמדים

n=2: 9=(2+b)2 ⇒ b=1 או b=−5\begin{aligned}n &= 2: \ 9 \\ &= (2+b)^2 \ \Rightarrow \ b \\ &= 1 \ \text{או} \ b \\ &= -5\end{aligned}

עוד הצבה

b=1b=1

הערך המשותף

הצבה אחת נתנה שני ערכים, ולכן צריך הצבה שנייה. המלכודת: לבחור b=−3b=-3 בלי לבדוק את n=2n=2.

Check the answer on elev

Exercise 9

הוכיחו או הפריכו: אם P(1)P(1) נכונה, והוכחנו P(k)⇒P(k+1)P(k) \Rightarrow P(k+1) רק עבור k≥2k \geq 2, אז P(n)P(n) נכונה לכל nn טבעי.

Show the answer and the solution

Answer: False

Worked solution:

P(1)⇏P(2)P(1) \not\Rightarrow P(2)

המעבר הראשון לא הוכח

P(2) ?P(2) \ ?

ובלי P(2)P(2) השרשרת לא מתחילה

הטענה לא נכונה. צריך לבדוק גם את P(2)P(2). בהוכחת הכדורים P(1)P(1) נכונה והצעד עובד מ-k=2k=2, והמסקנה שקרית.

Check the answer on elev

Exercise 10

תלמיד טוען: 1+3+9+⋯+3n−1=3n2−6n+41+3+9+\dots+3^{n-1}=3n^2-6n+4 לכל nn טבעי. מהו ה-nn הקטן ביותר שעבורו הטענה נכשלת?

Show the answer and the solution

Answer: 4

Worked solution:

n=1: 1=1\begin{aligned}n &= 1: \ 1 \\ &= 1\end{aligned}

מתקיים

n=2: 4=4\begin{aligned}n &= 2: \ 4 \\ &= 4\end{aligned}

מתקיים

n=3: 13=13\begin{aligned}n &= 3: \ 13 \\ &= 13\end{aligned}

מתקיים

n=4: 40≠28n=4: \ 40 \neq 28

נכשלת

שלוש בדיקות הצליחו, והנוסחה עדיין שגויה: הסכום האמיתי הוא 3n−12\frac{3^n-1}{2}. בדיקות מראות מה כדאי להוכיח, לא מוכיחות.

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