הוכחה שגויה ודוגמה נגדית

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

לתרגל ב-elev

תלמידה מציעה נוסחה: 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}.

להציג את התשובה והפתרון

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 כדורים?

להציג את התשובה והפתרון

בשקית יש שני כדורים. הקבוצה הראשונה היא כדור אחד, והשנייה היא הכדור האחר. אין כדור משותף, ולכן אין מעבר. הצעד עובד רק עבור 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}

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

תרגילים

תרגיל 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. הצעד אינו נכון
להציג את התשובה והפתרון

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

הפתרון:

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, ורק הבסיס חושף את זה.

לבדוק את התשובה שלי ב-elev

תרגיל 2

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

להציג את התשובה והפתרון

התשובה: 3

הפתרון:

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 היא דוגמה נגדית, ודוגמה נגדית אחת מספיקה כדי להפריך.

לבדוק את התשובה שלי ב-elev

תרגיל 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.

להציג את התשובה והפתרון

התשובה: 2

הפתרון:

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 לא ידוע.

לבדוק את התשובה שלי ב-elev

תרגיל 4

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

  1. מ-11 כדור ל-22 כדורים
  2. בבסיס, עבור כדור אחד
  3. בכל מעבר
  4. מ-22 כדורים ל-33 כדורים
להציג את התשובה והפתרון

התשובה: א מ-11 כדור ל-22 כדורים

הפתרון:

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

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

k≥2k \geq 2

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

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

לבדוק את התשובה שלי ב-elev

תרגיל 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}
להציג את התשובה והפתרון

התשובה: 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

הפתרון:

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

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

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

לבדוק את התשובה שלי ב-elev

תרגיל 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)= ____

להציג את התשובה והפתרון

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

הפתרון:

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

לבדוק את התשובה שלי ב-elev

תרגיל 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, בלי בסיס
להציג את התשובה והפתרון

התשובה: בסיס 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 — הוכחה פגומה

הפתרון:

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

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

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

לבדוק את התשובה שלי ב-elev

תרגיל 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 נותן שני ערכים.)

להציג את התשובה והפתרון

התשובה: 1

הפתרון:

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.

לבדוק את התשובה שלי ב-elev

תרגיל 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 טבעי.

להציג את התשובה והפתרון

התשובה: לא נכון

הפתרון:

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, והמסקנה שקרית.

לבדוק את התשובה שלי ב-elev

תרגיל 10

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

להציג את התשובה והפתרון

התשובה: 4

הפתרון:

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}. בדיקות מראות מה כדאי להוכיח, לא מוכיחות.

לבדוק את התשובה שלי ב-elev

השיעור הבא מחכה ב-elev

סרטונים, תרגול שנבדק מיד, ומסלול שמתקדם בקצב שלך — לכל הפרקים של הכיתה.

לתרגל ב-elevלגלות את elev לכיתה הזאת