טענה שתלויה במספר טבעי
יש טענות שיש בהן משתנה , למשל "" או " מתחלק ב-". לכל שמציבים מקבלים טענה אחרת: עבור , עבור , וכן הלאה.
במדויק: טענה שתלויה במספר טבעי היא טענה עם משתנה , כך שלכל מספר טבעי מתקבלת טענה מסוימת, שהיא נכונה או לא נכונה. הטענה "לכל טבעי" נכונה רק אם היא נכונה עבור כל אחד מהמספרים הטבעיים, בלי יוצא מן הכלל.
המספרים הטבעיים הם , ויש אינסוף מהם. לכן אי אפשר לבדוק אותם אחד אחד: גם אם בדקנו מיליון מקרים, יכול להיות שהמקרה הבא נכשל. הוכחה באינדוקציה היא שיטה שמכסה את כל המקרים בבת אחת.
תזכורת: סדרה לפי מקום ולפי כלל נסיגה
סדרה היא רשימה של מספרים לפי הסדר: . אפשר לתת אותה בשתי דרכים: נוסחה שנותנת כל איבר לפי המקום שלו, או איבר ראשון וכלל שמחשב כל איבר מהאיבר שלפניו.
במדויק: סדרה היא פונקציה שמוגדרת על המספרים הטבעיים: לכל מקום יש איבר אחד (מסמנים גם ).
- הגדרה לפי מקום: נוסחה , למשל .
- הגדרה בכלל נסיגה: האיבר הראשון , וכלל שמחשב את מתוך (ואולי גם מתוך ), למשל .
הגרף של סדרה הוא אוסף של נקודות נפרדות , כי מקבל רק ערכים טבעיים. בגרף: הסדרה , שאיבריה הראשונים . הקו המקווקו רק מראה על איזו עקומה הנקודות יושבות. את אותה סדרה נותן גם הכלל .
1. עקרון האינדוקציה: שלב הבסיס, שלב הצעד ושלב ההסקה
הוכחה באינדוקציה
דמיינו שורה ארוכה מאוד של אבני דומינו. אם האבן הראשונה נופלת, וכל אבן שנופלת מפילה את האבן שאחריה - כל האבנים ייפלו. על הרעיון הזה בנויה ההוכחה באינדוקציה.
במדויק: עקרון האינדוקציה: נתונה טענה שתלויה במספר טבעי . אם (1) הטענה נכונה עבור , וגם (2) לכל מספר טבעי : אם הטענה נכונה עבור , אז היא נכונה גם עבור - אז הטענה נכונה לכל מספר טבעי .
למה זה עובד: לפי (1) הטענה נכונה עבור . לפי (2) עם , היא נכונה עבור . לפי (2) עם , היא נכונה עבור , וכן הלאה. כך מגיעים לכל מספר טבעי.
שלב (2) הוא טענה מהסוג "אם... אז...". כשמוכיחים אותו לא יודעים עדיין אם הטענה נכונה עבור : רק מראים שאם היא נכונה עבור , אז היא נכונה גם עבור .
עקרון האינדוקציה
כדי להוכיח טענה לכל טבעי, מספיק להוכיח שתי דרישות:
1. שלב הבסיס: הטענה נכונה עבור .
2. שלב הצעד: לכל טבעי, אם הטענה נכונה עבור , אז היא נכונה עבור .
משתי הדרישות יחד נובע שהטענה נכונה לכל טבעי (שלב ההסקה).
מבנה הוכחה באינדוקציה
כשצריך להוכיח טענה לכל טבעי:
1. שלב הבסיס: מציבים ומראים שהטענה נכונה (בשוויון: מחשבים כל אגף בנפרד).
2. שלב הצעד - הנחה: הטענה נכונה עבור טבעי כלשהו. כותבים אותה עם במקום .
3. שלב הצעד - צריך להוכיח: כותבים את הטענה עם במקום .
4. שלב הצעד - הוכחה: מתחילים מאגף אחד של הטענה עבור , משתמשים בהנחה, ומגיעים לאגף השני.
5. שלב ההסקה: "לפי עקרון האינדוקציה, הטענה נכונה לכל טבעי."
ההנחה "נכון עבור מסוים כלשהו" היא לא הטענה שמוכיחים ("לכל "). היא רק חלק משלב הצעד, ומשתמשים בה כדי להגיע ל-.
בשלב הצעד לא צריך לדעת אם הטענה נכונה עבור . מוכיחים רק את הקשר: אם היא נכונה עבור , אז היא נכונה עבור .
כל הוכחה חייבת לכלול את שלושת השלבים בבירור: בסיס, צעד והסקה. בלי אחד מהם אין הוכחה.
דוגמה - הוכחה מלאה בשלושת השלבים
הוכיחו באינדוקציה שלכל טבעי מתקיים:
1. נתון: הטענה . המטרה: להוכיח אותה לכל טבעי.
2. שלב הבסיס (): באגף שמאל יש איבר אחד: . באגף ימין: . האגפים שווים.
3. הנחה: עבור טבעי כלשהו מתקיים .
4. צריך להוכיח: .
5. הוכחה: מפרידים את האיבר האחרון ומשתמשים בהנחה:
בסוף הוצאנו את כגורם משותף.
6. שלב ההסקה: הטענה נכונה עבור , והוכחנו שאם היא נכונה עבור אז היא נכונה עבור . לפי עקרון האינדוקציה, היא נכונה לכל טבעי.
הטענה נכונה לכל טבעי.
2. הוכחת נוסחאות סכום
סכום של איברים
בסכום כמו מספר המחוברים תלוי ב-: עבור יש מחובר אחד, עבור שניים, וכן הלאה. הביטוי שבסוף הוא המחובר האחרון, והוא גם הנוסחה של כל מחובר לפי המקום שלו.
במדויק: אם סדרה, הוא סכום האיברים הראשונים שלה: . האיבר הראשון קבוע, וכש- גדל ב- נוסף לסכום בדיוק איבר אחד: . עבור הסכום הוא האיבר הראשון בלבד: .
כך נראה הסכום עבור הראשונים. בכל שורה נוסף מחובר אחד, והוא שווה ל- עם ה- של השורה.
בזכות המבנה הזה, הסכום עם איברים הוא הסכום עם איברים ועוד איבר אחד. זה הקשר שמשתמשים בו בשלב הצעד.
הקשר בין ל-
כאשר הוא המחובר האחרון בסכום עם איברים: מציבים במקום בנוסחה של המחובר.
הוכחת נוסחת סכום באינדוקציה
כשצריך להוכיח לכל טבעי:
1. מזהים את המחובר הכללי (הביטוי האחרון באגף שמאל), וכותבים את .
2. שלב הבסיס: באגף שמאל רק , ובאגף ימין . בודקים שהם שווים.
3. הנחה: .
4. צריך להוכיח: . כדאי לפשט מראש את , כדי לדעת לאן מגיעים.
5. הוכחה: מחליפים את ב- לפי ההנחה, מוסיפים ומפשטים עד .
6. שלב ההסקה: לפי עקרון האינדוקציה, הנוסחה נכונה לכל טבעי.
ב- מציבים במקום כל . ב- המחובר הבא הוא , ולא .
כש- ו- חולקים גורם משותף, כמו , מוציאים אותו לפני שפותחים סוגריים. כך מגיעים מהר לצורה של .
דוגמה - נוסחת סכום של מכפלות
הוכיחו באינדוקציה שלכל טבעי מתקיים:
1. נתון: נוסחת הסכום. המטרה: להוכיח אותה לכל טבעי. המחובר הכללי , ולכן .
2. שלב הבסיס (): אגף שמאל: . אגף ימין: . שווים.
3. הנחה: עבור טבעי כלשהו.
4. צריך להוכיח: .
5. הוכחה: לפי ההנחה, אגף שמאל שווה ל-
הוצאנו את כגורם משותף, וקיבלנו בדיוק את אגף ימין.
6. שלב ההסקה: לפי עקרון האינדוקציה, הנוסחה נכונה לכל טבעי.
הנוסחה נכונה לכל טבעי.
3. הוכחת טענות התחלקות
התחלקות
מתחלק ב- כי , ו- לא מתחלק ב- כי בחלוקה יש שארית . כשאומרים ש" מתחלק ב-" מתכוונים שלכל טבעי התוצאה היא כפול מספר שלם.
במדויק: מספר שלם מתחלק במספר טבעי (ללא שארית) אם יש מספר שלם כך ש-. למשל ו- מתחלקים ב-.
בשלב הצעד מקבלים מההנחה שוויון כמו , כאשר שלם. את השוויון הזה מכניסים לביטוי של , ומראים שגם הוא כפול מספר שלם.
סכום וכפולה של מספרים שמתחלקים ב-
אם ו- (, שלמים), אז:
- ו- מתחלקים ב-.
- מתחלק ב- לכל שלם.
הוכחת התחלקות באינדוקציה
כשצריך להוכיח שהביטוי מתחלק ב- לכל טבעי:
1. שלב הבסיס: מחשבים וכותבים אותו כ- כפול מספר שלם.
2. הנחה: , כאשר מספר שלם.
3. צריך להוכיח: מתחלק ב-, כלומר עבור שלם כלשהו.
4. הוכחה: מסדרים את כך שיופיע בו חלק מההנחה:
- פולינום ב-: פותחים סוגריים וכותבים . מראים שהיתרה מתחלקת ב-.
- חזקה : כותבים , ומציבים את מתוך ההנחה.
5. שלב ההסקה: לפי עקרון האינדוקציה, מתחלק ב- לכל טבעי.
את מההנחה לא קובעים: הוא מספר שלם כלשהו. מההנחה מקבלים , וזה מה שמציבים.
בדיקה של כמה ערכים של אינה הוכחה של התחלקות לכל . היא רק עוזרת להבין את הטענה.
דוגמה א - ביטוי פולינומי: מפרידים את
הוכיחו באינדוקציה שלכל טבעי, מתחלק ב-.
1. נתון: . המטרה: להוכיח ש- מתחלק ב- לכל טבעי.
2. שלב הבסיס (): . מתחלק ב-.
3. הנחה: עבור טבעי כלשהו, כאשר שלם.
4. צריך להוכיח: מתחלק ב-.
5. הוכחה: פותחים סוגריים ומקבצים את :
לפי ההנחה זה . הביטוי בסוגריים שלם, ולכן הסכום מתחלק ב-.
6. שלב ההסקה: לפי עקרון האינדוקציה, מתחלק ב- לכל טבעי.
מתחלק ב- לכל טבעי.
דוגמה ב - ביטוי עם חזקה: מציבים את מההנחה
הוכיחו באינדוקציה שלכל טבעי, מתחלק ב-.
1. נתון: . המטרה: להוכיח ש- מתחלק ב- לכל טבעי.
2. שלב הבסיס (): . מתחלק ב-.
3. הנחה: עבור טבעי כלשהו, כאשר שלם. לכן .
4. צריך להוכיח: מתחלק ב-.
5. הוכחה: . המספר שלם, ולכן הביטוי מתחלק ב-.
6. שלב ההסקה: לפי עקרון האינדוקציה, מתחלק ב- לכל טבעי.
מתחלק ב- לכל טבעי.
4. אינדוקציה בסדרות: שקילות כלל נסיגה ונוסחה לפי מקום
שתי הצגות של אותה סדרה
את אותה סדרה אפשר לפעמים לתת גם בנוסחה לפי מקום וגם בכלל נסיגה. למשל, נותנת , וגם הכלל נותן . כדי לדעת שהן שוות בכל המקומות צריך הוכחה.
במדויק: שתי סדרות ו- שוות (שתי הצגות של אותה סדרה) אם לכל מספר טבעי . התאמה במספר סופי של מקומות, גם רבים, לא מספיקה.
בגרף רואים את ארבעת האיברים הראשונים של הסדרה, כנקודות על העקומה . כלל הנסיגה מחשב כל נקודה מהנקודה שלפניה, והנוסחה מחשבת כל נקודה ישירות לפי . הוכחה באינדוקציה מראה ששתי הדרכים נותנות את אותן נקודות לכל .
איבר ראשון וכלל נסיגה קובעים סדרה אחת
האיבר הראשון והכלל שמחשב את מתוך מספיקים כדי לקבוע את כל איברי הסדרה. לכן כדי להראות שנוסחה נותנת את הסדרה, מראים שהיא מתאימה לאיבר הראשון ומקיימת את אותו כלל נסיגה.
מעבר בין שתי ההצגות
הוכחה שנוסחה לפי מקום מתאימה לכלל נסיגה
כשנתונה סדרה בכלל נסיגה ( ו- מתוך ), וצריך להוכיח ש- לכל טבעי:
1. שלב הבסיס: מראים ש- הנתון שווה ל-.
2. הנחה: עבור טבעי כלשהו.
3. צריך להוכיח: .
4. הוכחה: כותבים לפי כלל הנסיגה (בעזרת ), מציבים לפי ההנחה, ומפשטים עד . ליד כל שוויון כותבים את הנימוק: "לפי כלל הנסיגה", "לפי ההנחה".
5. שלב ההסקה: לפי עקרון האינדוקציה, לכל טבעי.
כך מוכיחים גם את נוסחת האיבר הכללי של סדרה חשבונית ( נותן ) ושל סדרה הנדסית ( נותן ).
בשלב הצעד מתחילים מ- ומשתמשים בכלל הנסיגה. לא מתחילים מ- ומניחים שהוא שווה ל- - זה מה שצריך להוכיח.
דוגמה - כלל נסיגה עם כפל: נוסחה עם חזקה
סדרה מוגדרת על ידי ו-.
א. חשבו את ו-.
ב. הוכיחו באינדוקציה שלכל טבעי .
1. א: , . הנוסחה נותנת ו-, אבל זו רק בדיקה, לא הוכחה.
2. נתון: , . המטרה: לכל טבעי.
3. שלב הבסיס (): ו-. שווים.
4. הנחה: עבור טבעי כלשהו.
5. צריך להוכיח: .
6. הוכחה: (לפי כלל הנסיגה) (לפי ההנחה) .
7. שלב ההסקה: לפי עקרון האינדוקציה, לכל טבעי.
א. , . ב. הוכח: לכל טבעי.
5. טענות ויזואליות וגאומטריות
טענה על סדרה של ציורים
יש טענות על ציורים שנבנים בשלבים: מעבירים עוד ישר, מוסיפים עוד נקודה, מצרפים עוד משבצת. בכל שלב הציור הקודם נשאר, ומשהו נוסף עליו. כאן האינדוקציה טבעית במיוחד: הציור מראה מה נוסף במעבר משלב לשלב.
במדויק: נתונה סדרה של ציורים, שבה הציור ה- נבנה מהציור ה- לפי כלל קבוע. הוא גודל שנספר בציור ה- (מספר חלקים, קטעים, משבצות). מהכלל מקבלים כלל נסיגה: שווה ל- ועוד מה שנוסף בשלב, ואת הנוסחה של מוכיחים באינדוקציה.
דוגמה: מעבירים ישרים במישור, כך שאין שני ישרים מקבילים ואין שלושה ישרים שעוברים באותה נקודה. נסמן ב- את מספר חלקי המישור. ישר אחד מחלק את המישור ל- חלקים, שני ישרים ל-, ושלושה ישרים ל- (בציור, החלקים ממוספרים).
הישר ה- חותך כל אחד מ- הישרים הקודמים בנקודה אחרת, ולכן הוא מחולק ל- חלקים. כל חלק כזה חוצה חלק מישור אחד לשניים, ולכן נוספים בדיוק חלקים: .
ישרים במישור
ישרים במישור, שאין ביניהם שניים מקבילים ואין שלושה שעוברים באותה נקודה:
•הוספת הישר ה- מוסיפה חלקי מישור: , עם .
•מכאן, באינדוקציה: .
הוכחה באינדוקציה של טענה על ציורים
כשנתונה סדרה של ציורים וצריך להוכיח נוסחה לכל טבעי:
1. מתארים איך הציור ה- נבנה מהציור ה-, וסופרים מה נוסף. כך מקבלים כלל נסיגה: שווה ל- ועוד מה שנוסף, עם נימוק מהציור.
2. שלב הבסיס: סופרים בציור הראשון ומראים ש-.
3. הנחה: עבור טבעי כלשהו.
4. צריך להוכיח: .
5. הוכחה: לפי כלל הנסיגה, הוא ועוד מה שנוסף. לפי ההנחה מחליפים את ב-, ומפשטים עד .
6. שלב ההסקה: לפי עקרון האינדוקציה, לכל טבעי.
את מה שנוסף בשלב הצעד מנמקים עבור כללי, מתוך האופן שבו הציור נבנה. ספירה בשלושת הציורים הראשונים לא מוכיחה את כלל הנסיגה.
בודקים שהתנאים של הציור נשמרים בכל שלב. למשל, אם שני ישרים מקבילים, הישר החדש חותך פחות ישרים ומוסיף פחות חלקים.
דוגמה - קטעים בין נקודות על מעגל
על מעגל מסמנים נקודות שונות, ומחברים בקטע כל שתי נקודות. נסמן ב- את מספר הקטעים.
א. מצאו כלל נסיגה ל- ונמקו.
ב. הוכיחו באינדוקציה ש- לכל טבעי.
1. נתון: נקודות על מעגל, וכל שתיים מחוברות בקטע. המטרה: כלל נסיגה ל-, והוכחה ש-.
2. א: כשמוסיפים נקודה חדשה ל- נקודות, מחברים אותה לכל אחת מ- הנקודות הקיימות, והקטעים הישנים נשארים. לכן נוספים בדיוק קטעים: . בציור: נקודות עם קטעים, ונקודה חמישית שמוסיפה קטעים מקווקווים.
3. שלב הבסיס (): בנקודה אחת אין קטעים: . הנוסחה: . שווים.
4. הנחה: עבור טבעי כלשהו.
5. צריך להוכיח: .
6. הוכחה: (לפי כלל הנסיגה) (לפי ההנחה) .
7. שלב ההסקה: לפי עקרון האינדוקציה, לכל טבעי.
א. , . ב. הוכח: .
6. זיהוי הוכחות תקינות ומהלכים שגויים שאינם הוכחה
הוכחה תקינה ומהלך שאינו הוכחה
קל לכתוב משהו שנראה כמו הוכחה באינדוקציה ואינו הוכחה. צריך לדעת לבדוק הוכחה: מה בדיוק הוכח, ומה רק נבדק או הונח.
במדויק: הוכחה באינדוקציה תקינה כוללת: שלב בסיס שבו הטענה נבדקה עבור , שלב צעד שבו הוכח, לכל טבעי ולא רק עבור מסוים, שמהטענה עבור נובעת הטענה עבור , ושלב הסקה. בדיקה של מספר סופי של מקרים, גם אם הם רבים, אינה הוכחה.
שני השלבים לא תלויים זה בזה, ואף אחד מהם לא מחליף את השני. בדיקת מקרים פרטיים עוזרת להבין טענה ולנחש נוסחה. אבל בהוכחה באינדוקציה, המקרה הוא חלק מההוכחה רק כשיש לצדו שלב צעד.
מה חסר ומה זה גורם
שני השלבים לא תלויים זה בזה: כל אחד מהם צריך הוכחה משלו.
הפרכה בדוגמה נגדית
כדי להראות שטענה "לכל טבעי" לא נכונה, מספיק למצוא טבעי אחד שעבורו היא לא נכונה.
מהלכים שגויים נפוצים: מוכיחים את שלב הצעד רק עבור מסוים (למשל ); מניחים את הטענה עבור - מה שצריך להוכיח; או כותבים "נכון לכל " אחרי בדיקה של כמה מקרים בלבד.
אם שתי סדרות מתחילות באותם איברים, זה לא אומר שהן אותה סדרה. רק הוכחה (או מציאת מקום שבו הן שונות) מכריעה.
דוגמה א - שלב הצעד עובד ושלב הבסיס נכשל
תלמיד רוצה להוכיח שלכל טבעי . הוא מניח שהטענה נכונה עבור , ומקבל:
האם הוכיח את הטענה?
1. נתון: שלב צעד שהתלמיד כתב. המטרה: לבדוק אם זו הוכחה של הטענה.
2. בודקים את שלב הצעד: , וגם . שלב הצעד נכון.
3. בודקים את שלב הבסיס (): אגף שמאל , אגף ימין . , ולכן הבסיס לא מתקיים.
4. מסקנה: בלי בסיס אין הוכחה. למעשה הטענה לא נכונה לאף : באינדוקציה מוכיחים ש- לכל טבעי, וזה קטן ב- מאגף ימין.
לא. שלב הצעד נכון, אבל שלב הבסיס נכשל (), והטענה לא נכונה לאף טבעי.
דוגמה ב - התאמה בשלושה מקרים בלי שלב צעד
נתונות הסדרות ו-.
א. השוו את ו- עבור .
ב. תלמיד הסיק מסעיף א ש- לכל טבעי. האם הוא צודק?
1. נתון: שתי הסדרות. המטרה: להשוות אותן ולבדוק את המסקנה של התלמיד.
2. א: , , . , , . שוות בשלושת המקומות.
3. ב: בדיקה של שלושה מקרים היא רק שלב בסיס ועוד שתי בדיקות. אין שלב צעד, ולכן אין הוכחה.
4. בודקים את : , אבל . מצאנו דוגמה נגדית, ולכן המסקנה לא נכונה.
א. עבור . ב. לא: ו-.