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$ . אפשר להשתכנע שבאמת