שינויים
/* רעיון בסיסי - אינדוקציה על הטבעיים */
למה זה מספיק?
בוא נחשוב.. הוכחנו באופן ישיר כי הטענה נכונה עבור <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>
דוגמא:
נוכיח באינדוקציה כי הטענה <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math>
נכונה לכל <math>n\in \mathbb{N} </math> טבעי
הוכחה:
עבור <math>n=1</math> אכן מתקיים כי <math>1^2=1^3</math>
כעת נניח כי הטענה עבור <math>n</math> כלשהוא, כלומר מתקיים <math>(1+2+\cdots +n)^2 =1^3 +2^3 + \cdots +n^3</math> ונוכיח כי הטענה נכונה עבור <math>n+1</math>, כלומר
<math>(1+2+\cdots +n+n+1)^2 =1^3 +2^3 + \cdots +n^3 + (n+1)^3</math>
דוגמא נוספת:
==עיקרון הסדר הטוב ==
==הכללות==
===הכללה פשוטהפשוטה1===
הכללה ישירה מתבצעת כך (החלפה רק של הטענה הראשונה): אם נוכיח עבור טענה <math>P(n)</math> ש:
* הטענה מתקיימת עבור <math>n=k</math> מסוים כלומר <math>P(k)</math> מתקיים
אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>
כלומר - במקום להוכיח עבור <math>n=1</math> ואז הטענה מתקיים החל מ-1 ניתן להוכיח עבור <math>n=k</math> ואז הטענה מתקיים החל מ-k
===הכללה פשוטה 2 ===
אם נוכיח עבור טענה <math>P(n)</math> ש:
* הטענה מתקיימת עבור <math>n=1</math> מסוים כלומר <math>P(1)</math> מתקיים
* '''אם''' הטענה נכונה עבור כל המספרים עד מספר טבעי מסוים <math>n</math> (כלומר מתקיים <math>P(m)</math> עבור <math>m\leq n</math>) אזי היא נכונה גם עבור המספר הבא אחריו (כלומר <math>P(n+1)</math> מתקיים).
אז באופן דומה הטענה נכונה <math>P(n)</math> נכונה עבור <math>n\geq k</math>
כלומר - אפשר להחליף את ההנחה שמתקיים עבור <math>n</math> ולהוכיח עבור <math>n+1</math>
בהנחה שמתקיים עבור כל מי ש'''קטן שווה''' <math>n</math> ולהוכיח עבור <math>n+1</math>
=== הכללה מעמיקה ===
תהא <math>A</math> קבוצה סדורה היטבבת מניה אז אפשר לעשות שם אינדוקציה הערה: אפשר לעשות אינדוקציה טרנספניטית על קבוצות כלשהן (לאו דווקא בנות מניה)הערה: קיום סדר טוב על הטבעיים שקול לקיומה של אינדוקציה על הטבעיים. == תרגילים יותר מעניינים ==כפל n מטריצותהפרש סימטרי של n קבוצות
