מה צריך לדעת על «הוכחה באינדוקציה ובדיקת תקינות הוכחות»?

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

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

מהי אינדוקציה מתמטית

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

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

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

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

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

מתי משתמשים באינדוקציה

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

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

שלושת שלבי ההוכחה: בסיס, הנחה וצעד

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

בסיס האינדוקציה. בודקים שהטענה נכונה עבור הערך הקטן ביותר שבו היא אמורה להתקיים. אם הטענה נאמרת לכל $n$ טבעי, הבסיס הוא לרוב $n=1$. אם הטענה נאמרת לכל $n \ge 2$, יש לבדוק $n=2$.

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

צעד האינדוקציה. מוכיחים שהטענה נכונה עבור $k+1$. לפני החישוב, כדאי לכתוב במפורש מה צריך להוכיח, כלומר להציב $k+1$ בטענה המקורית. לאחר מכן משתמשים בהנחת האינדוקציה ובפעולות אלגבריות כדי להגיע לצורה הנדרשת.

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

הצבת $k+1$ וזיהוי האיבר החדש

לפני שמתחילים בצעד האינדוקציה, יש לכתוב את הטענה עבור $k+1$. פעולה זו מתבצעת על ידי החלפת כל מופע של $n$ בטענה המקורית ב-$k+1$. אם הטענה כוללת סכום, יש לשים לב שהאיבר האחרון משתנה בהתאם, אך האיברים הקודמים נשארים כפי שהיו.

לדוגמה, בטענה

$1+2+\cdots+n=\frac{n(n+1)}{2}$

הצבת $k+1$ נותנת

$1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}.$

האיבר החדש הוא $(k+1)$, והסכום הקודם $1+2+\cdots+k$ הוא בדיוק הביטוי שמופיע בהנחת האינדוקציה.

בסכום שבו האיבר הכללי הוא למשל $2n-1$, עבור $k+1$ האיבר החדש הוא

$2(k+1)-1=2k+1.$

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

הוכחת נוסחת סכום: $1+2+\cdots+n$

נוכיח שלכל $n$ טבעי מתקיים:

$1+2+\cdots+n=\frac{n(n+1)}{2}.$

בסיס האינדוקציה. עבור $n=1$, באגף שמאל יש רק את האיבר $1$. באגף ימין מתקבל:

$\frac{1(1+1)}{2}=\frac{2}{2}=1.$

לכן הטענה נכונה עבור $n=1$.

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

$1+2+\cdots+k=\frac{k(k+1)}{2}.$

צעד האינדוקציה. נוכיח שהטענה נכונה עבור $k+1$, כלומר:

$1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}.$

נשתמש בהנחת האינדוקציה:

$$1+2+\cdots+k+(k+1) = \left(1+2+\cdots+k\right)+(k+1) = \frac{k(k+1)}{2}+(k+1).$$

נוציא גורם משותף $(k+1)$:

$$\frac{k(k+1)}{2}+(k+1) = (k+1)\left(\frac{k}{2}+1\right) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}.$$

קיבלנו בדיוק את הצורה שנדרשה עבור $k+1$. לכן הטענה נכונה לכל $n$ טבעי.

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

בטענות רבות על סכומים, האיבר הראשון קבוע, ובכל מעבר מ-$n$ ל-$n+1$ מתווסף איבר אחד בלבד. למשל, בסכום

$1+3+5+\cdots+(2n-1)$

האיבר הראשון הוא $1$, ובכל שלב מתווסף האיבר האי־זוגי הבא.

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

דוגמה קצרה: נוכיח שלכל $n$ טבעי,

$1+3+5+\cdots+(2n-1)=n^2.$

בסיס: עבור $n=1$, אגף שמאל הוא $1$, ואגף ימין הוא $1^2=1$.

הנחה: נניח שעבור $k$ מתקיים

$1+3+\cdots+(2k-1)=k^2.$

צעד: נוכיח עבור $k+1$:

$1+3+\cdots+(2k-1)+(2k+1)=(k+1)^2.$

לפי ההנחה:

$1+3+\cdots+(2k-1)+(2k+1)=k^2+(2k+1)=(k+1)^2.$

לכן הטענה נכונה לכל $n$ טבעי.

זיהוי הוכחה תקינה

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

• הטענה מנוסחת בבירור, וברור עבור אילו ערכים של $n$ היא אמורה להתקיים.
• בסיס האינדוקציה נבדק עבור הערך הראשון המתאים. אם הטענה נכונה רק החל מ-$n=2$, הבסיס חייב להיות $n=2$.
• אם הטענה כוללת תנאי, כגון $n \ge 2$, יש לציין את התנאי ולבדוק את הבסיס בהתאם.
• הנחת האינדוקציה כתובה במפורש עבור $k$ כלשהו, ולא עבור כל $n$ וגם לא עבור $k+1$.
• בצעד האינדוקציה מוכיחים את הטענה עבור $k+1$ מתוך ההנחה, ולא מניחים אותה.
• המעבר מ-$k$ ל-$k+1$ תקף לכל $k$ שבו ההנחה רלוונטית, ובפרט הוא מאפשר לעבור מהבסיס לערך העוקב לו.
• כל שלב אלגברי מוצדק: אין מדלגים על שוויון לא ברור, אין מבצעים חלוקה בביטוי שעלול להיות שווה לאפס, ואין משתמשים בטענה שלא הוכחה.
• בסוף הצעד מתקבל בדיוק הביטוי הנדרש עבור $k+1$, ולא רק ביטוי שנראה דומה לו.

מהלכים שגויים שאינם מהווים הוכחה

בבחינת הוכחות באינדוקציה יש לזהות גם טעויות נפוצות שהופכות את המהלך ללא תקף.

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

הנחה מעגלית. שגיאה נפוצה היא לכתוב בהנחת האינדוקציה את הטענה עבור $k+1$, או להשתמש בצעד ההוכחה במה שצריך להוכיח. הנחת האינדוקציה מתייחסת ל-$k$ בלבד.

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

בסיס שאינו מתאים. אם הטענה נאמרת עבור $n \ge 3$ אך בודקים רק $n=1$, הבסיס אינו מספיק. כמו כן, אם צעד האינדוקציה תקף רק עבור $k \ge 2$, יש לוודא שהבסיס והמעבר הראשון אכן מכסים את כל הערכים הדרושים.

צעד שאינו נובע מההנחה. אם מציגים חישוב עבור $k+1$ אך אינו משתמש בהנחת האינדוקציה, או שמשתמשים בזהות שגויה, ההוכחה אינה תקפה.

הסתמכות על דמיון בין ביטויים. אם לאחר הצבת $k+1$ מקבלים ביטוי שנראה דומה לנוסחה הרצויה, אך אין שרשרת שוויונות מלאה שמחברת בין אגף שמאל לאגף ימין, ההוכחה אינה שלמה.

מעבר לא חוקי בין מקרים. דוגמה מפורסמת היא הטענה השגויה: “לכל הסוסים בעולם יש אותו צבע”. בסיס האינדוקציה עבור קבוצה של סוס אחד נראה ברור. בצעד מניחים שבכל קבוצה של $k$ סוסים יש אותו צבע, ומנסים להוכיח זאת עבור קבוצה של $k+1$ סוסים על ידי השוואה בין שתי תת־קבוצות בנות $k$ סוסים. עבור $k=1$, שתי תת־הקבוצות מכילות סוס אחד בלבד, ואין ביניהן איבר משותף שמחבר בין הצבעים. לכן המעבר מ-$k=1$ ל-$k=2$ אינו תקף, וההוכחה כולה אינה נכונה.

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