הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5"
אחיה בר-און (שיחה | תרומות) (←הכללה פשוטה 2) |
אחיה בר-און (שיחה | תרומות) (←הכללה פשוטה 2) |
||
שורה 74: | שורה 74: | ||
אם <math>n+1</math> ראשוני - סיימנו כי אז הוא הפירוק של עצמו. | אם <math>n+1</math> ראשוני - סיימנו כי אז הוא הפירוק של עצמו. | ||
− | אחרת <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=\Pi_{k=1}^l p_k,b=\Pi_{i=1}^r q_i</math> כאשר <math>p_k,q)i</math> ראשוניים | ||
+ | |||
+ | ואז <math>n=ab=\Pi_{k=1}^l p_k\cdot \Pi_{i=1}^r q_i</math> | ||
+ | |||
+ | וסיימנו | ||
=== הכללה מעמיקה === | === הכללה מעמיקה === |
גרסה מ־12:03, 17 ביולי 2014
תוכן עניינים
רעיון בסיסי - אינדוקציה על הטבעיים
בשביל להוכיח שטענה מסוימת נכונה עבור כל מספר טבעי (למשל ) מספיק להוכיח את הבאים:
- (בסיס האינדוקציה) הטענה מתקיימת עבור כלומר מתקיים
- (צעד האינדוקציה)אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר .
למה זה מספיק? בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור כלומר מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור (שזה אכן כך) אז הטענה נכונה גם עבור כלומר . אה! אז עכשיו זה נכון עבור אז לפי אותה טענה זה נכון גם עבור ! ומה עכשיו? אם זה נכון עבור זה נכון עבור . וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר נכון לכל
דוגמא: נוכיח באינדוקציה כי הטענה נכונה לכל טבעי
הוכחה:
עבור אכן מתקיים כי
כעת נניח כי הטענה עבור כלשהוא, כלומר מתקיים ונוכיח כי הטענה נכונה עבור , כלומר
דוגמא נוספת:
עיקרון הסדר הטוב
הכללות
הכללה פשוטה 1
הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה ש:
- הטענה מתקיימת עבור מסוים כלומר מתקיים
- אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר .
אז באופן דומה הטענה נכונה נכונה עבור
כלומר - במקום להוכיח עבור ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור ואז הטענה מתקיים החל מ-k
דוגמא:
הוכח כי לכל מתקיים לכל
פתרון:
עבור נקבל כי
כעת נניח כי הטענה נכונה עבור כלשהוא, כלומר מתקיים
נוכיח עבור מהנחת האינדוקציה נקבל כי
וסיימנו
הכללה פשוטה 2
אם נוכיח עבור טענה ש:
- הטענה מתקיימת עבור מסוים כלומר מתקיים
- אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים (כלומר מתקיים עבור ) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר מתקיים).
אז באופן דומה הטענה נכונה נכונה עבור
כלומר - אפשר להחליף את ההנחה שמתקיים עבור ולהוכיח עבור בהנחה שמתקיים עבור כל מי שקטן שווה ולהוכיח עבור
דוגמא:
כל מספר טבעי ניתן להציגו כמכפלה של מספרים ראשוניים
הוכחה:
עבור זה נכון כי 2 ראשוני ואז הוא הפירוק של עצמו.
כעת נניח שהטענה נכונה לכל ונוכיח עבור
אם ראשוני - סיימנו כי אז הוא הפירוק של עצמו.
אחרת מתפרק למכפלה כאשר לפי הנחת האינדוקציה מתפרקים למכפלה של מספרים ראשוניים כאשר ראשוניים
ואז
וסיימנו
הכללה מעמיקה
תהא קבוצה סדורה היטב בת מניה אז אפשר לעשות שם אינדוקציה
הערה: אפשר לעשות אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה) הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים.
תרגילים יותר מעניינים
כפל n מטריצות הפרש סימטרי של n קבוצות