הבדלים בין גרסאות בדף "תרגול 4 תשעז"
(←רעיון בסיסי - אינדוקציה על הטבעיים) |
(←הכללה פשוטה שנייה) |
||
(3 גרסאות ביניים של משתמש אחר אחד אינן מוצגות) | |||
שורה 10: | שורה 10: | ||
* (צעד האינדוקציה) '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>. | * (צעד האינדוקציה) '''אם''' הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר <math>P(n)\rightarrow P(n+1)</math>. | ||
− | למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=1</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=2</math>כלומר <math>P(2)</math>. אה! אז עכשיו זה נכון עבור <math>n=2</math> אז לפי אותה טענה זה נכון גם עבור <math>n=3</math>! ומה עכשיו? אם זה נכון עבור <math>n=3</math> זה נכון עבור <math>n=4</math> . וכן | + | למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור <math>n=1</math> כלומר <math>P(1)</math> מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור <math>n=1</math> (שזה אכן כך) אז הטענה נכונה גם עבור <math>n=2</math>. כלומר <math>P(2)</math>. אה! אז עכשיו זה נכון עבור <math>n=2</math>, אז לפי אותה טענה זה נכון גם עבור <math>n=3</math>! ומה עכשיו? אם זה נכון עבור <math>n=3</math>, זה נכון עבור <math>n=4</math>. וכן הלאה באותה הדרך. אפשר להשתכנע שבסופו של דבר <math>P(n)</math> נכון '''לכל''' <math>n</math>. |
'''דוגמה:''' | '''דוגמה:''' | ||
שורה 67: | שורה 67: | ||
'''דוגמה:''' | '''דוגמה:''' | ||
− | הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math> | + | הוכח כי לכל <math>x>0</math> מתקיים <math>(1+x)^n > 1+nx</math> לכל <math>n\geq 2</math>. |
פתרון: | פתרון: | ||
− | עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math> | + | עבור <math>n=2</math> נקבל <math>(1+x)^2 = 1+2x+x^2>1+2x</math> כי <math>x>0</math> . |
− | כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math> | + | כעת נניח כי הטענה נכונה עבור <math>n</math> כלשהו, כלומר מתקיים <math>(1+x)^n > 1+nx</math>. |
נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי | נוכיח עבור <math>n+1</math> מהנחת האינדוקציה נקבל כי | ||
− | <math> (1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)= | + | <math>(1+x)^{n+1}=(1+x)^n\cdot (1+x)>(1+nx) (1+x)</math> |
+ | <math>=1+nx +x+nx^2 > 1+x+nx =1+ (n+1)x</math> | ||
וסיימנו. | וסיימנו. | ||
שורה 91: | שורה 92: | ||
בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>. | בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>. | ||
− | + | ====תרגיל (בד"כ נעשה בהרצאה)==== | |
כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים. | כל מספר טבעי <math>1<n </math> ניתן להציגו כמכפלה של מספרים ראשוניים. | ||
שורה 104: | שורה 105: | ||
אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math> | אחרת <math>n+1</math> מתפרק למכפלה <math>n+1=ab</math> כאשר <math>1<a,b<n+1</math> | ||
לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים | לפי הנחת האינדוקציה <math>a,b</math> מתפרקים למכפלה של מספרים ראשוניים | ||
− | <math>a=\ | + | <math>a=\prod_{k=1}^l p_k,b=\prod_{i=1}^r q_i</math> כאשר <math>p_k,q_i</math> ראשוניים. |
+ | |||
+ | אזי <math>n+1=ab=\prod_{k=1}^l p_k\cdot \prod_{i=1}^r q_i</math> וסיימנו. | ||
− | + | ====תרגיל==== | |
+ | שאלת השוקולוד. | ||
=תרגילים יותר מעניינים= | =תרגילים יותר מעניינים= |
גרסה אחרונה מ־12:12, 8 בדצמבר 2019
חזרה לדף מערכי התרגול.
תוכן עניינים
אינדוקציה מתמטית: רעיון בסיסי
אינדוקציה היא שיטה המאפשרת להוכיח שטענה מסוימת נכונה עבור כל מספר טבעי (למשל ) בעזרת הסקה מן הפרט אל הכלל.
הוכחת הטענה שקולה להוכחת שתי הטענות הבאות:
- (בסיס האינדוקציה) הטענה מתקיימת עבור . כלומר נכון.
- (צעד האינדוקציה) אם הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר .
למה זה מספיק? בוא נחשוב. הוכחנו באופן ישיר כי הטענה נכונה עבור כלומר מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור (שזה אכן כך) אז הטענה נכונה גם עבור . כלומר . אה! אז עכשיו זה נכון עבור , אז לפי אותה טענה זה נכון גם עבור ! ומה עכשיו? אם זה נכון עבור , זה נכון עבור . וכן הלאה באותה הדרך. אפשר להשתכנע שבסופו של דבר נכון לכל .
דוגמה: נוכיח באינדוקציה כי הטענה נכונה לכל טבעי.
הוכחה:
עבור אכן מתקיים כי .
כעת נראה שאם הטענה נכונה עבור כלשהוא, כלומר אם מתקיים אזי הטענה נכונה עבור , כלומר . כלומר נוכיח ש:
נוכיח:
לפי הנחת האינדוקציה אפשר להמשיך הלאה:
וסיימנו.
דוגמה:
הוכח כי לכל מספר טבעי מתקיים כי
פתרון:
עבור אכן מתקיים
כעת נניח שהטענה נכונה עבור ונוכיח את הטענה עבור
לפי הנחת האינדוקציה ניתן להמשיך
שזה הטענה עבור וסיימנו.
הכללות
הכללה פשוטה ראשונה
הכללה ישירה שבה יש שינוי רק בבסיס האינדוקציה: אם נוכיח עבור טענה כי:
- הטענה מתקיימת עבור מסוים. כלומר נכונה.
- אם הטענה נכונה עבור מספר טבעי מסוים, אז היא נכונה גם עבור המספר הבא אחריו. כלומר .
אז באופן דומה הטענה נכונה נכונה עבור .
כלומר - במקום להוכיח עבור ואז הטענה מתקיימת החל מ- ניתן להוכיח עבור ואז הטענה מתקיים החל מ-.
דוגמה: הוכח כי לכל מתקיים לכל .
פתרון:
עבור נקבל כי .
כעת נניח כי הטענה נכונה עבור כלשהו, כלומר מתקיים .
נוכיח עבור מהנחת האינדוקציה נקבל כי
וסיימנו.
הכללה פשוטה שנייה
הכללה שבה יש שינוי בצעד האינדוקציה, הנקראת אינדוקציה שלמה: אם נוכיח עבור טענה כי:
- הטענה מתקיימת עבור . כלומר נכונה.
- אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים (כלומר מתקיים עבור ) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר מתקיים).
אז באופן דומה הטענה נכונה נכונה עבור .
כלומר - אפשר להחליף את ההנחה שמתקיים עבור ולהוכיח עבור בהנחה שמתקיים עבור כל מי שקטן שווה ולהוכיח עבור .
תרגיל (בד"כ נעשה בהרצאה)
כל מספר טבעי ניתן להציגו כמכפלה של מספרים ראשוניים.
הוכחה:
עבור זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.
כעת נניח שהטענה נכונה לכל ונוכיח עבור .
אם ראשוני - סיימנו כי אז הוא הפירוק של עצמו.
אחרת מתפרק למכפלה כאשר לפי הנחת האינדוקציה מתפרקים למכפלה של מספרים ראשוניים כאשר ראשוניים.
אזי וסיימנו.
תרגיל
שאלת השוקולוד.
תרגילים יותר מעניינים
תרגיל
יהא פסוק. נגדיר בעזרת אינדוקציה פסוקים:
הוכיחו כי טאוטולוגיה כאשר אי-זוגי.
פתרון: נוכיח באינדוקציה כי לכל אי-זוגי, הפסוק הוא טאוטולוגיה. בדיקה: עבור , הפסוק הוא . הוא אכן טאוטולוגיה.
צעד: כעת, נניח את נכונות הטענה עבור אי-זוגי, ונוכיח עבור האי-זוגי הבא בתור, כלומר .
מתקיים: נראה כי זו אכן טאוטולוגיה. ראשית, לפי ההנחה, לכל ערך של .
- אם , נקבל - אכן אמת.
- אם , נקבל - אכן אמת.
וסיימנו באינדוקציה.
תרגיל
יהיו מטריצות ריבועיות אזי האיבר הכללי של המכפלה של כולם ניתן ע"י הנוסחה
הוכחה (באינדוקציה על מספר המטריצות):
עבור זה ההגדרה של כפל בין 2 מטריצות.
כעת, נניח שהטענה נכונה עבור כלשהו. נוכיח נכונות עבור .
לפי הנחת האינדוקציה נמשיך:
וסיימנו.
אזהרה
אינדוקציה היא כלי חזק אך יש לשים לב כי משתמשים בו נכון.
דוגמה מפורסמת להוכחת שגויה באינדוקציה היא הדוגמה הבאה:
טענה: כל קבוצה של סוסים לא ריקה מכילה סוסים מצבע יחיד.
"הוכחה": נוכיח בעזרת אינדוקציה על מספר האיברים בקבוצת הסוסים.
עבור אכן מתקיים כי קבוצה עם סוס אחד מכילה רק סוסים מצבע יחיד.
כעת נניח כל קבוצה עם סוסים מכילה סוסים רק מצבע יחיד ונוכיח את הטענה לקבוצת סוסים מגודל .
תהא קבוצה עם סוסים אזי לפי הנחת האינדוקציה ו- הן קבוצות שמכילות סוסים מצבע יחיד (כי אלו קבוצות סוסים מגודל ), ולכן כל הסוסים ב- גם כן בעלי צבע יחיד (כי יש חפיפה בין ובין ).
חישבו איפה השגיאה (רמז: במעבר מ ל ).