שלום! את השיעור של היום אנחנו נייחד לטכניקה מאוד נפוצה להוכחת משפטים מתמטיים שידוע בשם אינדוקציה מתמטית ובנוסף לתיאור הרעיון ההוכחה ודוגמה שנוכיח מפורשות משהו באמצעות הטכניקה. אני גם רוצה לקשור בין מושג האינדוקציה המתמטית לבין הסדרות או אולי יותר ההגדרה הרקורסיבית של סדרות. שעסקנו בה בשיעורים האחרונים. אני אתחיל מדוגמה שאני מקווה תבהיר במה אנחנו עוסקים. בואו נתבונן בטענה מתמטית שלעת עתה יכולה להיות נכונה או לא. טענה: לכל L טבעי המספר 6 בחזקת N פחות 1 הוא כפולה של 5. זאת טענה. אם היא נכונה צריך להוכיח אותה אם היא שגויה מספיק למצוא N אחד ש-6 בחזקת N פחות 1 לא יהיה כפולה של 5 וזה יוכיח שהטענה אינה נכונה. אם נחשוב מה כתוב כאן, למעשה אפשר לחשוב על זה כעל אין סוף טענות נפרדות למעשה מה שכתוב כאן זה ש-6 בחזקת 1 פחות 1 הוא כפולה של 5. וגם 6 בחזקת 2 פחות 1 הוא כפולה של 5. וגם 6 בחזקת 3 פחות 1 הוא כפולה של 5 וכן הלאה. אבל ללא סוף. יש פה אין סוף טענות ויש טענה ראשית שאומרת כולן נכונות. אולי בשפה אחרת אני אומר שיש פה סדרה של פסוקים מתמטיים כן, אנחנו, משהו כמו 6 בחזקת 1 פחות 1 הוא כפולה של 5 הוא דוגמה לפסוק מתמטי שיכול להיות נכון או לא. והטענה היא שסדרת הפסוקים הזאת, כולה היא סדרה של פסוקים נכונים. אז מכיוון שיש לנו פה סדרה ואנחנו עבדנו עם סדרות במפגשים האחרונים ולמדנו למשל שמאוד נוח לסמן סדרות באותיות, האיבר ה-N של סדרה אפשר לעשות פה לבנות כאן סדרה לא של מספרים כפי שעשינו בשיעורים הקודמים אלא סדרה של פסוקים מתמטיים. למשל נוכל לומר שהפסוק המתמטי שנקרא לו Q1 האיבר הראשון בסדר של פסוקים הוא הפסוק 6 בחזקת 1 פחות 1 הוא כפולה של 5 הפסוק המתמטי Q2 הוא ש-6 בריבוע פחות 1 הוא כפולה של 5. הפסוק Q3 ובאופן כללי נוכל לומר הפסוק ה-N הוא שהמספר 6 בחזקת A פחות 1 הוא כפולה של 5 כן, אז יש לנו סדרה של פסוקים מתמטיים אני כותב את זה בכתיב מאוד כלומר זהה סדרות שהשתמשנו בו בשיעורים קודמים, אלא שהפעם כל 1 מה-Q האלה הוא לא מספר ממשי אלא הוא פסוק מתמטי. פסוק מתמטי יכול להיות אמת. במקרה זה נאמר שערכו הוא הערך אמת. מקובל לסמן זאת באות T מן המילה True. אבל פסוק מתמטי גם יכול להיות שיקרי במקרה זה נאמר שערכו הוא שקר או הסימון המקובל הוא F מ-False באנגלית. הטענה שכתובה כאן שלכל N טבעי 6 ב-N פחות 1 הוא כפולה של 5, דרך אלטרנטיבית לנסח את אותה טענה היא לומר שאם נתבונן בסדרת הפסוקים המתמטיים: Q1, Q2, Q3 כשהפסוק ה-N הוא 6 בחזקת N פחות 1 הוא כפולה של 5 הטענה פה אומרת שהסדרה הזאת היא סדרה שכל איבריה הם אמת. זו דרך קצת אחרת להסתכל על הטענה הזאת. נשאלת אבל עכשיו שאלה עקרונית, זאת אומרת אנחנו קצת הוכחנו משפטים מתמטיים קצת במהלך הקורס הזה, קצת עסקתם בזה בבית ספר בדרך כלל היה צריך לעבוד קשה, יותר או פחות כדי להוכיח משפט מתמטי אבל כל משפט מתמטי שהוכחנו הצריך עבודה. פה אנחנו במצב שבו אנחנו צריכים להוכיח שסדרה אין סופית של פסוקים מתמטיים הם כולם אמת. ויש פה אם כן שאלה עקרונית כיצד אפשר במכה אחת, בהוכחה אחת להוכיח שאין ספור פסוקים מתמטיים כולם הם אמת. זה המקום שטכניקת ההוכחה של אינדוקציה מתמטית נכנסת לפעולה. בואו באמת נישאר עם הדוגמה שלנו. למשל את הפסוק הראשון ש-6 בחזקת 1 פחות 1 הוא כפולה של 5 אפשר לבדוק זאת בצורה ישירה באמצעת חישוב. 6 בחזקת 1 זה 6 פחות 1 זה 5, 5 הוא כמובן הכפולה של 5 אז לא קשה לקבוע באמצעות חישוב ישיר שהפסוק הראשון שאומר ש-6 בחזקת 1 פחות 1 הוא כפולה של 5 הוא אכן פסוק אמת. Q1 שווה T הפסוק הראשון הוא אמת. מה לגבי הפסוק השני? 6 בריבוע 36 פחות 1, 35. 35 הוא כפולה של 5 לכן שוב באמצעות חישוב הראנו בצורה מפורשת ש-Q2 גם כן היה פסוק אמת. זה נכון 6 בריבוע פחות הוא כפולה של 5. באותו אופן נוכל להמשיך, 6 בשלישית זה 216 פחות 1 זה 215 כפולה של 5 גם Q3 הוא אמת. אבל אני מניח שברור לכם שזו לא דרך שיטתית להראות שסדרה אינסופית של טענות מתמטיות היא נכונה. אנחנו בכל פעם צריכים לחשב מחדש ולא לומדים שום דבר מכל חישוב שבאמצעותו נוכל להסיק משהו על השאר. הרעיון האינדוקציה המתמטית הוא הבא. יש לנו סדרה של פסוקים מתמטיים סדרה אין סופית של פסוקים מתמטיים מטרתנו היא להראות שכולם הם אמת. באינדוקציה מתמטית אנחנו עושים את הדבר הבא: אנחנו בודקים שבאמת האיבר הראשון בסדרה אכן היה אמת. מה שכמובן רק מראה שהוא אמת לא מראה שהסדרה כולה היא אמת. ואז אנחנו מוכיחים תנאי היקש. כלל היקש. אנחנו מראים שאם יש איבר בסדרה. נסמן אותו ב-QN שהוא אמת. אם הוא אמת אז בהכרח גם האיבר אחריו יהיה אמת. אז באינדוקציה מתמטית מוכיחים א׳: ש-Q1 הוא אמת. ודבר שני מוכיחים שלכל N אם QN הוא אמת אזי QN ועוד 1 הוא גם כן אמת. ומה שאני אומר שאם אנחנו מראים זאת אז נובע מכך מיד שבאמת כל הפסוקים בסדרה הם כולם אמת. מדוע? הראנו מפורשות שהפסוק הראשון אמת אבל על זה ראינו שאם הפסוק היה אמת אז גם השני היה אמת. אנחנו כבר יודעים שגם הפסוק השני הוא אמת אבל אם אנחנו יודעים שהוא אמת, אז גם זה שאחריו הוא פסוק אמת. וכך באופן רקורסיבי אנחנו יכולים להראות שגם הפסוק 1000 בסדרה הוא אמת כי הפסוק ה-999 היה אמת. איך אני יודע כי ה-998 היה אמת וחוזרים אחורה עד לפסוק הראשון שבאמת ידעתי שהוא אמת. זה הרעיון של האינדוקציה המתמטית. אפשר הרבה פעמים מדמים את ההכוחה באמצעות אינדוקציה לרכבת דומינו שמטרתי היא להפיל את אבני הדומינו ומה שאני עושה כדי להפיל, אני למעשה מפיל רק את הראשון רק אני מצמיד את האבנים מספיק כך שכל אבן שנופלת מפילה את זאת שבאה אחריה זה קצת תמונה מטפורה ציורית כדי לתאר אולי את ההכוחה באמצעות אינדוקציה שבה מה שאני עושה אני מראה שהפסוק הראשון הוא אמת, נדמה את זה להפלת האבן הראשונה במגדל, סליחה ברכבת. ואז כלל ההיקש הוא המטפורה שלא זה שאני הצמדתי את אבני הדומינו מספיק כך שאם אני אראה שפסוק מסוים הוא אמת אז מובטח שגם זה שאחריו הוא אמת, זו המטפורה הפלת רכבת הדומינו. בואו נדגים באמת את דרך ההוכחה הזאת עבור הטענה שהתחלנו ממנה. אני רוצה להוכיח שלכל 6N בחזקת N פחות 1 הוא כפולה של 5. אז השלב הראשון בהוכחה הוא כמון שלב א׳ שמופיע כאן הוכחה נראה תחילה Q1 הוא אמת, הראינו זאת כבר נכון, פשוט על ידי הצבה ישירה אכן 5 בחזקת 1 פחות 1 שווה 5 6 הוא כפולה של 5. והשלב הראשון השלב הקל בדרך כלל בהוכחה באמצעות אינדוקציה, שלב שכיננו שלב א׳ ואז מגיע השלב השני. אנחנו אומרים נניח ש-QN הפסוק ה-N הוא אמת. כלומר נניח ש-6 בחזקת N פחות 1 הוא כפולה של 5 חשוב לי להדגיש, כשאני אומר נניח אני לא אומר שאני יודע שזה נכון, ייתכן שזה שיקרי אבל הרעיון של האינדוקציה כפי שהסברנו אותו הוא שאני מראה שאם זה נכון אז גם הפסוק הבא הוא נכון. כלומר אני רוצה להשתמש בהנחה ש-6 בחזקת N פחות 1 הוא כפולה של 5 על מנת להראות, נראה כי הדבר גורר, ההנחה גוררת שגם הפסוק הבא הוא אמת ושוב אני אכתוב פה בסוגריים כלומר, ש-6 בחזרת N ועוד 1 פחות 1 הוא כפולה של 5. אז כיצד נראה זאת? נתבונן ב-6 בחזקת N ועוד 1 פחות 1. נשים לב ש-6 בחזקת N ועוד 1 לפי חוקי החזקות שווה ל-6 פעמים, 6 בחזקת N פחות 1. עכשיו היתה לי הנחה. ההנחה שלי היתה ש-6 בחזקת N פחות 1 הוא כפולה של 5. אז בואו נכתוב מחדש את מה שכתוב באופן הבא, נכתוב 6 פעמים 6 בחזקת N פחות 1 כי הוא מישהו, שזה ביטוי שאני יודע לומר עליו משהו. אבל אז אני חיסרתי 6 אז אני צריך להוסיף 6 מחדש ולחסר 1 אני רק אכתוב זאת כך. ועכשיו נתבונן בביטוי שקיבלנו עבור 6 בחזקת N ועוד 1 פחות 1 קיבלנו אותו כסכום של 2 איברים, אחד מהם הוא פשוט 5 הוא בוודאי מתחלק ב-5, השני הוא 6 פעמים הביטוי שבהנחה שלנו, הנחת האינדוקציה, הנחנו שהוא כפולה של 5 אז אני רוצה לחזור ולחדד את הנקודה הזאת, אני כרגע לפחות לא יודע ש-6 בחזקת N פחות 1 הוא כפולה של 5 אבל אני ידוע שאם הוא אכן כזה אז גם כשאני אכפול אותו ב-6 היא תישאר לי כפולה של 5. כשאני אחבר 5 עדין תשאר לי כפולה של 5 אז אני יודע שאם 6 בחזקת N פחות 1 הוא כפולה של 5 אזי גם 6 בחזקת N ועוד 1 פחות 1 הוא כפולה של 5. הוכחתי זה עתה בדיוק את מה שרציתי. שאם הפסוק ה-N הוא אמת אזי הפסוק ה-N ועוד 1 הוא גם כן אמת ומכיוון שהראתי שבצורה, בנפרד, בשלב א׳ שהפסוק הראשון הוא אמת הרי שמעקרון האינדוקציה, מאותה בניה של הרקורסיה שכל דבר גורר את הבא אחריו אנחנו מסיקים מיד את נפילת כל רכבת הדומינו הזאת זאת אומרת, כל אחד מהפסוקים, Q1, Q2, Q3 עד אין סוף הם כולם פסוקי אמת. ובכן נסיית את השיעור שלנו בדוגמה מעט היטולית שבה אני אראה לכם שימוש שגוי בעקרון האינדוקציה. אני הולך להוכיח לכם את הטענה הבאה: לכל הדובים בעולם אותו הצבע. טענה לכל הדובים אותו הצבע. טענה זו כמובן אינה נכונה. אם תטיילו ביערות צפון אמריקה תפגשו דובים חומים ואם תצפינו לאלסקה תפגשו דובים לבנים הטענה אינה נכונה ואם זאת אני הולך להוכיח אותה בעזרת הטכניקה שלמדנו לפני מספר רגעים אני אנסח קודם כל את הטענה הזאת בצורה מעט שונה שתתאים לשימוש באינדוקציה אני אגדיר פסוק שנקרא לו QN שאומר שבכל קבוצה שבה יש N דובים לכל הדובים אותו הצבע. בכל קבוצה בת N דובים, היינו כל מספר טבעי לכל הדובים אותו הצבע ואחרי שהגדרנו את הפסוק QN את סדרת הפסוקים אפשר לנסח מחדש את הטענה הטענה היא שלכל N טבעי הפסוק QN מקבל את הערך אמת אז בואו נוכיח זאת אנחנו נשתמש בעקרון האינדוקציה ונוכיח שקודם כל הפסוק הראשון הוא אמת ודבר שני נוכיח שלכל N נוכיח ש-1 Q1 הוא אמת. ודבר שני, כן השלב האינדוקטיבי בהוכחה שלכל N אם ואני חוזר ומדגיש בעקרון האינדוקציה אנחנו אומרים שאם הפסוק ה-N הוא אמת אזי גם הפסוק שבא אחריו, הפסוק שעוקב לו הוא גם כן אמת. אז אלה שלבי ההוכחה. אז שלב א׳, מהו הפסוק Q1 בכל קבוצה שבה יש דב 1 לכל הדובים אותו צבע, זה כמובן נכון באופן טריביאלי. אז Q1 שווה T בדקנו. ועכשיו אנחנו עוברים לשלב השני נניח ש-QN הוא אמת שבאמת לכל קבוצה שבה יש N דובים, לכל הדובים אותו צבע ונתבונן עכשיו בקבוצת דובים שבה יש N ועוד 1 דובים. אני רוצה להוכיח ש-QN ועוד 1 הוא גם כן פסוק אמת אז נתבנון בקבוצה בת N ועוד 1 דובים שאני אומר שאני צריך להוכיח ש-QN ועוד 1 הוא אמת, כן אני צריך להוכיח שלכל קבוצה שיש בה N ועוד 1, בוודאי שאפשר למצוא איזושהי קבוצה בת N ועוד 1 דובים שבה לכל הדובים אותו צבע אבל צריך להוכיח שלכל קבוצה שיש בה N ועוד 1 דובים, לכל הדובים אותו צבע ולכן אני לוקח קבוצה שרירותית שיש בה N ועוד 1 דובים. אני באופן סימבולי מציין אותה פה באיזושהי צורה. ועכשיו מה נעשה, נקח את אחד הדובים ונוציא אותו לרגע מהקבוצה. מה נשאר? קבוצה שיש בה N דובים. אבל לפי הנחת האינדוקציה לכל הדובים, לכל N הדובים שנותרו אותו צבע. שימו לב אני לא יודע מהו אותו צבע הטענה וההנחה לא אומרים כלום לגבי אם הצבע הזה חום שחור, לבן או כחול. אבל מהנחת האינדוקציה מובטח ש-N הדובים שנשארו, לכולם אותו צבע. ועכשיו נחזיר את הדב הזה ונקח דב אחר מאותה קבוצה ונוציא אותו שוב נשארנו עם N דובים שלכולם אותו צבע ומכאן שהדב שהוצאנו בהתחלה צבעו היה זהה לצבע של הדובים האחרים שהיו שם ולכן מכאן נובע שלכל N ועוד 1 דובים אותו צבע. כלומר אנחנו עכשיו באמצעות הטיעון הזה הוכחנו שההנחה שלכל קבוצה בת N דובים לכל הדובים אותו צבע גוררת שהדבר נכון גם כשיש N ועוד 1 דובים ובעצם בזאת השלמנו את הוכחת המשפט והסקנו מסקנה מסעירה שלכל הדובים בעולם אותו צבע. תודה רבה!
