כיצד לבצע הוכחות אינדוקציה?
בהוכחת אינדוקציה "חלשה", בסופו של דבר אתה מחפש קשר בין P (k) ו- P (k + 1) כדי להוכיח שהצעתך נכונה.
אינדוקציה מתמטית היא שיטה להוכחה מתמטית המבוססת על הקשר בין אמירות מותנות. למשל, בואו נתחיל בהצהרה המותנית: "אם זה יום ראשון, אני אראה כדורגל." אתה יכול להצהיר את ההצהרה הבאה: "אם אני צופה בכדורגל, אני אזמין הוצאה." אתה יכול לעקוב אחר הצהרה זו עם אחר: "אם אני מזמין הוצאה, אני לא אבשל." מאלה תוכלו להסיק בתוקף כי: "אם זה יום ראשון, אני לא אבשל ", בגלל הקשר ההגיוני בין הצהרות מותנות אלה. אם אתה יכול להוכיח שההצהרה הראשונה בשרשרת ההשלכות נכונה, וכל אמירה מרמזת על האמירה הבאה, באופן טבעי נובע שההצהרה האחרונה בשרשרת היא גם נכונה.ככה אינדוקציה מתמטית עובדת, והשלבים שלהלן ימחישו כיצד לבנות הוכחת אינדוקציה רשמית.
שיטה 1 מתוך 2: שימוש באינדוקציה מתמטית "חלשה" או "רגילה"
- 1העריך את הבעיה. נניח שאתה מתבקש לחשב את סכום המספרים האי-זוגיים "n" הראשונים, כתוב כ [1 + 3 + 5 +... + (2n - 1)], על ידי אינדוקציה. (המונח האחרון כאן נובע מהעובדה שאם תכפיל מספר כלשהו ואז תגרע 1 מאותו ערך, המספר המתקבל תמיד יהיה אי זוגי.) בהתחלה, ייתכן שתבחין כי נראה כי סכום המספרים האי-זוגיים העוקבים עוקב אחר תבנית. (למשל, 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16; 1 + 3 + 5 + 7 + 9 = 25). נראה שהסכום הוא מספר המספרים המוזרים שאתה מוסיף בריבוע, נכון? כעת, כשיש לנו מושג על התבנית שמשחקת כאן, אנו יכולים להתחיל בהוכחה שלנו.
- 2ציין את הרכוש שיוכח באמצעות אינדוקציה. בדוגמה שלנו שמנו לב לתבנית המתייחסת לסכום המספרים האי-זוגיים הראשונים "n". כדי להשלים את המשימה שהוקצתה לנו (כלומר, חישוב סכום המספרים האי-זוגיים הראשונים "n"), נוכל לקחת את הזמן לכתוב את כל המספרים האי-זוגיים, החל מ- 1 עד "n" ולהוסיף אותם למעלה. אבל יש דרך קלה יותר. בהתבסס על מה שראינו לגבי הסיכומים הראשונים שעשינו, נוכל להציע נכס זה, אותו ננסה להוכיח באמצעות אינדוקציה:
- 1 + 3 +... + (2n - 1) = n ^ 2
- נתייחס למאפיין זה כ- P (n) מכיוון ש- "n" הוא המשתנה בו השתמשנו לעיל.
- הסימן השמאלי של המשוואה מייצג את סכום המספרים האי- זוגיים הראשונים "n", החל מ- 1.
- 3הבן את הרעיון העומד מאחורי אינדוקציה מתמטית. כדאי לחשוב על אינדוקציה במונחים של דומינו, מה שמזכיר את "שרשרת ההשלכות" שנדונה במבוא לעיל. חשבו על כל ערך של "n" במאפיין לעיל, P (n), כדומינו בודד, המסודר בשורה. אם אנו יכולים להראות כי P (1) - הערך הראשון בשרשרת - נכון, זה אומר שנוכל להפיל את הדומינו הראשון. יתר על כן, אם אנו מניחים שניתן לדפוק כל דומינו אחד (כלומר, P (n) תקף לערך שרירותי כלשהו של "n") ובהנחה זו, ניתן לדפוק גם את הדומינו הבא (כלומר, P (n + 1) נכון גם), זה אומר שאנחנו יכולים להפיל את כל הדומינו עם הנכס המוצהר שלנו. המשמעות היא שהנכס נכון בכל המקרים והשגנו את מטרתנו באמצעות אינדוקציה.
- 4הוכיח כי המקרה הבסיסי עבור הנכס מתקיים. "מקרה הבסיס" עבור נכס מסוים הוא ערך כלשהו קטן המשמש כדי להראות שההצהרה הראשונה של הנכס מתקיימת. במקרה זה נשתמש ב- "1" מכיוון שזהו המספר האי זוגי הראשון וקל לעבוד איתו. אם המאפיין תקף למקרה הבסיס, נוכיח שנוכל לדפוק את הדומינו הראשון ונוכל לעבור לשלב הבא.
- P (1): 1 = 1 ^ 2
- P (1): 1 = 1 (זה החזיק, אנחנו טובים. הדומינו הראשון למטה.)
- 5ציין את השערת ההשראה. השלב הבא של האינדוקציה כולל הנחת הנחה. בדוגמה שלנו, אנו נניח כי עבור ערך שרירותי כלשהו של "n" - נניח "k" - שההצהרה נכונה. כלומר, אנו מאמינים כי הרכוש שלנו יחזיק ללא קשר לערך המשמש ל"נ ". אם זה לא היה נכון, לנכס שלנו (כלומר הפיתרון שלנו לבעיה המקורית של חישוב סכום המספרים האי-זוגיים הראשונים "n") לא היה שימוש רב. אמנם עדיין לא הוכחנו דבר, אך הנחה זו חשובה ולבושה בצורה הבאה:
- P (k): 1 + 3 +... + (2k - 1) = k ^ 2
- זכור שאנו מניחים שזה נכון בהמשך ההוכחה (כלומר שנוכל להפיל כל דומינו בודד בשרשרת).
- 6הוכיח כי ההשערה האינדוקטיבית מתקיימת לערך הבא בשרשרת. במילים אחרות, אנו מניחים כי P (k) מתקיים, ובהנחה זו ננסה להוכיח שגם P (k + 1) מתקיים. אם אנו יכולים לעשות זאת, הוכחנו שהתיאוריה שלנו תקפה באמצעות אינדוקציה מכיוון שאם מפיל דומינו אחד (בהנחה ש- P (k) נכון) מפיל את הדומינו הבא (באמצעות הנחה זו, הוכחת P (k + 1) היא גם נכון), כל הדומינו ייפול והרכוש שלנו יוכח תקף. אז בואו ננסה את זה:
- P (k): 1 + 3 +... + (2k - 1) = k ^ 2 נכון.
- P (k + 1): 1 + 3 +... + (2k - 1) + (2 (k + 1) - 1) = (k + 1) ^ 2
- החלק הנטוי שלמעלה בצד שמאל של המשוואה מייצג את התוספת של המונח הבא של מספר מוזר ברצף, k + 1. אם נוכל להפוך אותו צד שמאל שווה לצד ימין, יהיה לנו הצליח.
- מנקודת ההנחה שלנו, אנו יודעים כי חלק בלתי באות נטויה מעל שווים K ^ 2, אז בואו לעשות החלפה כי.
- P (k + 1): k ^ 2 + (2 (k + 1) - 1) = (k + 1) ^ 2
- P (k + 1): k ^ 2 + 2k + 1 = (k + 1) ^ 2
- P (k + 1): (k + 1) ^ 2 = (k + 1) ^ 2
- 7מסכם שהמאפיין מוכח בתוקף על ידי אינדוקציה מתמטית. על ידי שימוש באלגברה קטנה, הוכחנו שהנכס שלנו אינו נכון לא רק עבור ערך שרירותי כלשהו של "n", אלא גם עבור הערך העוקב אחר אותו ערך. הראינו ש- P (1) נכון, נניח ש- P (k) נכון, והוכחנו כי בהתבסס על הנחה זו, P (k + 1) נכון גם הוא. כדי להשתמש באנלוגיית הדומינו המתמשכת שלנו, דפקנו בהצלחה את הדומינו הראשון והראינו שלרכוש שלנו יש ערך כלשהו. ואז, בהנחה שניתן יהיה להפיל כל דומינו שרירותי בשרשרת, הוכחנו כי פעולה זו בהכרח תפיל את הדומינו הבא, עד אין קץ בשאר השרשרת. לפיכך, הראינו שהרכוש שלנו מחזיק באופן כללי וסיימנו בהצלחה את ההוכחה שלנו באמצעות אינדוקציה מתמטית.
כמו בעבר, הצעד הראשון בכל הוכחת אינדוקציה הוא להוכיח כי מקרה הבסיס מתקיים.
שיטה 2 מתוך 2: שימוש באינדוקציה מתמטית "חזקה" או "מלאה"
- 1להבין את ההבדל בין שתי צורות האינדוקציה. הדוגמה שלעיל היא זו של מה שמכונה אינדוקציה "חלשה", הנקראת כך לא בגלל הבדל באיכות בין שתי שיטות האינדוקציה אלא כדי להמחיש הבדל בין ההנחה בהשערת ההשראה של כל סוג של הוכחה. שתי טכניקות ההוכחה הן למעשה שוות ערך, רק לפעמים יש צורך להניח יותר בהשערת ההשראה על מנת להוכיח את ההצעה העומדת על הפרק. כדי לחזור לאנלוגיית הדומינו שלנו, לפעמים המשקל של ההנחה ש- P (k) נכון אינו מספיק כדי להפיל את הדומינו המיוצג על ידי P (k + 1). לפעמים אתה צריך להיות מסוגל להפיל את הכל את הדומינו לפניו על מנת להוכיח שההצעה שלך מתקיימת.
- 2ציין את ההצעה שתוכיח באמצעות אינדוקציה חזקה. כדי להמחיש זאת, נבחן דוגמה אחרת. נניח שאתה מתבקש להוכיח נכון את ההצעה כי ניתן לכתוב את כל המספרים השלמים הגדולים מ -1 כמוצר של מספרים ראשוניים.
- כמו בעבר, נתייחס להצעה זו כאל P (n), כאשר "n" הוא המספר שניתן לבטא כמוצר של ראשוניים.
- מכיוון שאנחנו מדברים על כל המספרים השלמים הגדולים מ- 1, "n" יצטרך להיות גדול או שווה ל -2.
- זכור שמספר ראשוני הוא מספר שלם חיובי גדול מ- 1 שניתן לחלק אותו רק בלי שארית, בפני עצמו ו- 1.
- 3להוכיח שמקרה הבסיס מתקיים. כמו בעבר, הצעד הראשון בכל הוכחת אינדוקציה הוא להוכיח כי מקרה הבסיס מתקיים. במקרה זה נשתמש ב- 2. מכיוון ש- 2 הוא מספר ראשוני (רק ניתן לחלוקה בפני עצמו ו- 1), אנו יכולים להסיק כי המקרה הבסיסי נכון.
- 4ציין את השערת ההשראה (החזקה). כאן ההבדל בין אינדוקציה "חלשה" ל"אינדוקציה חזקה "מציג את עצמו בצורה הברורה ביותר, שכן שלב זה הוא ההבדל היחיד בין שתי צורות ההוכחה ההשראה. ההשערה האינדוקטיבית לאינדוקציה "חלשה" מניחה שעבור ערך שרירותי כלשהו של "n" שוב, נשתמש ב- "k" - שההצעה מחזיקה. לאחר מכן נשתמש בהנחה זו כדי להוכיח שהערך הבא בשרשרת נכון, מה שמאפשר לנו להסיק שההצעה שלנו תקפה בסך הכל. עם זאת, עבור הצעה זו, בהנחה ש- P (k) נכון אינו אומר לנו דבר על P (k + 1). סוג זה של הנחה "חלשה" אינו מספיק כאן, ולכן נצטרך להניח עוד. ההשערה האינדוקטיבית לאינדוקציה "חזקה", במקום להניח פשוט כי P (k) אמיתית, מניחה כי לכל הערכים של "n"בין המקרה הבסיסי ל"קי ", שההצעה נכונה. נשתמש בזה הנחה חזקה יחסית (כלומר, אנו מניחים יותר) כדי להוכיח שהטענה נכונה.
- סוג זה של הנחה "חזקה" הוא המבדיל בין שתי צורות ההוכחה.
- במקרה זה, נניח כי עבור ערך כלשהו של k ≥ 2, כל מספר שלם "n" כך ש -2 ≤ n ≤ k עשוי להיכתב כתוצר של ראשוני.
- 5הוכיח שהשערת ההשראה "החזקה" מתקיימת לערך הבא בשרשרת. כעת נשתמש בהנחה חזקה זו כדי להוכיח שגם P (k + 1) מתקיים, וכך נוכיח את תקפות ההצעה שלנו באופן כללי. ישנן שתי תוצאות רלוונטיות עבור "k + 1". אם "k + 1" הוא מספר ראשוני, ההצעה שלנו מתקיימת, וסיימנו. אם "k + 1" אינו מספר ראשוני, יהיה לו גורם ראשוני קטן ביותר, אותו נסמן כ- "p". לכן, "k + 1" יכול לבוא לידי ביטוי כמוצר של "p" ומספר אחר, "x". מכיוון ש- "x" בהכרח יהיה פחות מ- "k", ההשערה האינדוקטיבית שלנו אומרת אותנו שניתן לכתוב "x" כתוצר של ראשוניים, מה שבסופו של דבר אומר - ללא קשר לשאלה אם "k + 1" הוא ראשוני או לא, ניתן לכתוב אותו כמוצר של מספרים ראשוניים.
- 6לסיום ההצעה מוכחת בתוקף על ידי אינדוקציה מתמטית חזקה. באמצעות השערת ההשראה "החזקה" שלנו, הצלחנו להוכיח את ההצעה שלנו שהייתה כאשר אינדוקציה "חלשה" לא הייתה מספקת לשם כך. נסה תחילה אינדוקציה "חלשה" מכיוון שהעובדה שאתה מניח פחות תיאורטית הופכת את ההיגיון מאחורי ההוכחה לחזק יותר, בניגוד למוסכמות השמות המשמשות לשני סוגי ההוכחות הללו. אולם מבחינה מתמטית שתי צורות האינדוקציה שוות ערך.
כך פועלת אינדוקציה מתמטית, והשלבים שלהלן ימחישו כיצד לבנות הוכחת אינדוקציה רשמית.
- בהוכחת אינדוקציה "חלשה", בסופו של דבר אתה מחפש קשר בין P (k) ו- P (k + 1) כדי להוכיח שהצעתך נכונה. בהוכחת אינדוקציה "חזקה", אתם מחפשים קשר בין P (כל ערך של "n" בין המקרה הבסיסי ל- "k") ו- P (k + 1).
- אם אינדוקציה "חזקה" מתקיימת, כך גם אינדוקציה רגילה, ולהיפך. זכור ששני סוגי ההוכחות שווים זה לזה, ואחד מהם אינו טוב יותר מטבעו מהשני. אינדוקציה "חזקה" מציעה לעיתים מעט עזרה בכתיבת ההוכחה כאשר ההשערה האינדוקטיבית לאינדוקציה "חלשה" אינה מוכיחה בבירור את ההצעה העומדת על הפרק.
- אינדוקציה עובדת בגלל עקרון הסדר הטוב. כלומר, לכל קבוצה לא שלמה של מספרים שלמים חיוביים יש אלמנט קטן ביותר. בדוגמה שלנו, האלמנט הקטן ביותר היה 1.
- אינדוקציה משמשת בדרך כלל כדי להוכיח כי נכס נכון לכל המספרים הטבעיים. פירוש הדבר שתעבוד עם מספרים שלמים חיוביים (מספרים לא חלקים, או שלמים).
בהוכחת אינדוקציה "חזקה", אתם מחפשים קשר בין P (כל ערך של "n" בין המקרה הבסיסי ל- "k") ו- P (k + 1).
- אל תשכח את מקרי הבסיס! לעתים קרובות קל להתעלם מהצעד הפשוט הזה, מכיוון שהוא די טריוויאלי. עם זאת, ההוכחה האינדוקטיבית שלך תהיה שלמה בלעדיה.
- אל תבלבל בין אינדוקציה מתמטית לבין המושג חשיבה אינדוקטיבית, שבה מנסים להגיע למסקנה אפשרית על סמך ראיות שנצפו. אינדוקציה מתמטית היא למעשה חשיבה דדוקטיבית המשתמשת בהיגיון כדי לעבור מהנחות יסוד מסוימות וברורות למסקנה מוגדרת.
תגובות (1)
- מדהים. הסביר הרבה יותר טוב מכל מורה, מורה או פרופסור שאי פעם היה לי. תודה למי שכתב את זה.
