88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1.5

חזרה למערכי התרגול

רעיון בסיסי - אינדוקציה על הטבעיים

בשביל להוכיח שטענה מסוימת $P(n)$ נכונה עבור כל מספר טבעי (למשל $(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3$) מספיק להוכיח את הבאים:

• הטענה מתקיימת עבור $n=1$ כלומר $P(1)$ מתקיים
• אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר $P(n)\Rightarrow P(n+1)$.

למה זה מספיק? בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור $n=1$ כלומר $P(1)$ מתקיים. לכן לפי הטענה השניה, אם הטענה נכונה עבור $n=1$ (שזה אכן כך) אז הטענה נכונה גם עבור $n=2$כלומר $P(2)$. אה! אז עכשיו זה נכון עבור $n=2$ אז לפי אותה טענה זה נכון גם עבור $n=3$! ומה עכשיו? אם זה נכון עבור $n=3$ זה נכון עבור $n=4$ . וכן על זה הדרך. אפשר להשתכנע שבסופו של דבר $P(n)$ נכון לכל $n$

דוגמא: נוכיח באינדוקציה כי הטענה $(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3$ נכונה לכל $n\in \mathbb{N}$ טבעי

הוכחה:

עבור $n=1$ אכן מתקיים כי $1^2=1^3$

כעת נניח כי הטענה עבור $n$ כלשהוא, כלומר מתקיים $(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3$ ונוכיח כי הטענה נכונה עבור $n+1$, כלומר $(1+2+\cdots +n+n+1)^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3$

דוגמא נוספת:

הכללות

הכללה פשוטה 1

הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה $P(n)$ ש:

• הטענה מתקיימת עבור $n=k$ מסוים כלומר $P(k)$ מתקיים
• אם הטענה נכונה עבור מספר טבעי מסוים אזי היא נכונה גם עבור המספר הבא אחריו. כלומר $P(n)\Rightarrow P(n+1)$.

אז באופן דומה הטענה נכונה $P(n)$ נכונה עבור $n\geq k$

כלומר - במקום להוכיח עבור $n=1$ ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור $n=k$ ואז הטענה מתקיים החל מ-k

הכללה פשוטה 2

אם נוכיח עבור טענה $P(n)$ ש:

• הטענה מתקיימת עבור $n=1$ מסוים כלומר $P(1)$ מתקיים
• אם הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים $n$ (כלומר מתקיים $P(m)$ עבור $m\leq n$) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר $P(n+1)$ מתקיים).

אז באופן דומה הטענה נכונה $P(n)$ נכונה עבור $n\geq k$

כלומר - אפשר להחליף את ההנחה שמתקיים עבור $n$ ולהוכיח עבור $n+1$ בהנחה שמתקיים עבור כל מי שקטן שווה $n$ ולהוכיח עבור $n+1$

הכללה מעמיקה

תהא $A$ קבוצה סדורה היטב בת מניה אז אפשר לעשות שם אינדוקציה

הערה: אפשר לעשות אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה) הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים.

תרגילים יותר מעניינים

כפל n מטריצות הפרש סימטרי של n קבוצות