יחידה 1: אינדוקציה מתמטית¶

מבוא¶

מהי אינדוקציה?

אינדוקציה מתמטית היא שיטה (שימושית מאוד) להוכחת טענות מהצורה:

לכל מספר טבעי $n$ מתקיים $P(n)$

כאשר $\mathbb{N} = \{0, 1, 2, \ldots\}$ היא קבוצת המספרים הטבעיים, ו-$P(n)$ היא טענה כלשהי בנוגע למספר הטבעי $n$.

דוגמאות לטענות שמוכיחים באינדוקציה

לכל $n$ טבעי מתקיים: $0 + 1 + \ldots + n = \frac{n(n+1)}{2}$
לכל $n$ טבעי מתקיים: $n^3 - n$ מתחלק ב-$6$

עקרון האינדוקציה¶

אינדוקציה רגילה (פשוטה)¶

עקרון האינדוקציה המתמטית

כדי להוכיח שטענה $P(n)$ מתקיימת לכל מספר טבעי $n \geq 0$, מספיק להוכיח:

בסיס האינדוקציה: $P(0)$ נכון
צעד האינדוקציה: לכל $n \geq 1$ טבעי, אם $P(n-1)$ נכון אז $P(n)$ נכון

ההנחה $P(n-1)$ נקראת הנחת האינדוקציה.

ניסוח שקול

בצעד האינדוקציה אפשר גם להוכיח:

אם $P(n)$ אז $P(n+1)$, עבור $n \geq 0$

מדוע האינדוקציה עובדת?¶

אינטואיציה

אפשר לדמות את עקרון האינדוקציה לאפקט דומינו:

בסיס: הקלף הראשון נופל (מוכיחים $P(0)$)
צעד: כל קלף שנופל מפיל את הבא אחריו (אם $P(n)$ אז $P(n+1)$)

מסקנה: כל הקלפים יפלו (הטענה נכונה לכל $n$)

דוגמאות בסיסיות¶

דוגמה 1: סכום סדרה חשבונית¶

הוכחה: $0 + 1 + \ldots + n = \frac{n(n+1)}{2}$

בסיס: עבור $n = 0$: $$0 = \frac{0 \cdot (0+1)}{2} = 0 \checkmark$$

צעד: יהי $n \geq 1$ טבעי. נניח שהטענה נכונה עבור $n-1$ (הנחת האינדוקציה): $$0 + 1 + \ldots + (n-1) = \frac{(n-1)n}{2}$$

נוכיח עבור $n$: $$\begin{align} 0 + 1 + \ldots + n &= (0 + 1 + \ldots + (n-1)) + n \\ &\stackrel{*}{=} \frac{(n-1)n}{2} + n \\ &= \frac{n^2 - n + 2n}{2} \\ &= \frac{n^2 + n}{2} = \frac{n(n+1)}{2} \end{align}$$

כש-$(*)$ היא הנחת האינדוקציה.

דוגמה 2: אי-שוויון אקספוננציאלי¶

הוכחה: לכל $n \geq 5$ מתקיים $2^n > n^2$

בסיס: עבור $n = 5$: $$2^5 = 32 > 25 = 5^2 \checkmark$$

צעד: יהי $n \geq 5$ טבעי. נניח $2^n > n^2$ (הנחת האינדוקציה). נוכיח עבור $n+1$: $$2^{n+1} = 2 \cdot 2^n \stackrel{*}{>} 2n^2$$

צריך להראות: $2n^2 > (n+1)^2$, כלומר $2n^2 - (n+1)^2 > 0$.

\[2n^2 - (n+1)^2 = 2n^2 - n^2 - 2n - 1 = n^2 - 2n - 1 = (n-1)^2 - 2\]

עבור $n \geq 5$: $(n-1)^2 - 2 \geq 4^2 - 2 = 14 > 0$ ✓

אינדוקציה עם בסיס שונה מ-0¶

התאמת הבסיס

אם הטענה היא: "לכל מספר טבעי $n \geq k$ מתקיים $P(n)$", אז:

בסיס: מוכיחים $P(k)$
צעד: לכל $n \geq k+1$ מוכיחים: $P(n-1) \Rightarrow P(n)$

אינדוקציה מלאה (שלמה)¶

למה צריך אינדוקציה מלאה?¶

הבעיה: כל $n \geq 2$ ניתן לכתיבה כמכפלה של ראשוניים

ניסיון כושל באינדוקציה רגילה:

בסיס: $n=2$ הוא ראשוני ✓
צעד: נניח $n-1 = p_1 \cdot p_2 \cdot \ldots \cdot p_k$
אז $n = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$... נתקענו!

הבעיה: אין קשר בין פירוק של $n-1$ לפירוק של $n$.

עקרון האינדוקציה המלאה¶

עקרון האינדוקציה המלאה (השלמה)

כדי להוכיח שטענה $P(n)$ מתקיימת לכל מספר טבעי $n \geq k$:

בסיס: $P(k)$ נכון
צעד: לכל $n \geq k+1$: אם $P(k), P(k+1), \ldots, P(n-1)$ כולם נכונים, אז $P(n)$ נכון

במילים אחרות: כדי להוכיח $P(n)$ מותר להניח את $P(m)$ לכל $k \leq m < n$.

הערה

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

הוכחת משפט הראשוניים¶

הוכחה: כל $n \geq 2$ ניתן לכתיבה כמכפלה של ראשוניים

בסיס: עבור $n = 2$: זו מכפלה של הראשוני $p = 2$ ✓

צעד (אינדוקציה מלאה): יהי $n \geq 3$ טבעי. נניח שהטענה נכונה לכל $m$ כך ש-$2 \leq m < n$.

מקרה 1: אם $n$ ראשוני - סיימנו.

מקרה 2: אם $n$ פריק, קיימים $m_1, m_2$ טבעיים בטווח $2 \leq m_1, m_2 < n$ כך ש-$n = m_1 \cdot m_2$.

מהנחת האינדוקציה (המלאה!): - $m_1 = p_1 \cdot \ldots \cdot p_{k_1}$ - $m_2 = q_1 \cdot \ldots \cdot q_{k_2}$

לכן: $n = m_1 \cdot m_2 = p_1 \cdot \ldots \cdot p_{k_1} \cdot q_1 \cdot \ldots \cdot q_{k_2}$ ✓

שגיאות נפוצות¶

שגיאה 1: בסיס לא נכון¶

דוגמה: 'כל הסוסים בעולם באותו צבע'

טענה שגויה: לכל $n \geq 1$, כל קבוצה של $n$ סוסים - כולם באותו צבע.

ניסיון הוכחה:

בסיס: $n=1$ - ברור שסוס אחד הוא באותו צבע כמו עצמו ✓
צעד: נניח הטענה נכונה ל-$n$, נוכיח ל-$n+1$.
ניקח סוסים $a_1, \ldots, a_{n+1}$
הקבוצה $\{a_1, \ldots, a_n\}$ - כולם באותו צבע (הנחת האינדוקציה)
הקבוצה $\{a_2, \ldots, a_{n+1}\}$ - כולם באותו צבע (הנחת האינדוקציה)
הסוס $a_2$ משותף לשתיהן, לכן כולם באותו צבע!

היכן השגיאה? הצעד נכשל במעבר מ-$n=1$ ל-$n=2$! עבור שני סוסים $a_1, a_2$:

הקבוצה $\{a_1\}$ - סוס אחד
הקבוצה $\{a_2\}$ - סוס אחד

אין חפיפה בין הקבוצות! אין סוס משותף שמחבר בין הצבעים.

שגיאה 2: שכחת הבסיס¶

תמיד לוודא את הבסיס!

הבסיס הוא חלק הכרחי מההוכחה
בלי בסיס, צעד האינדוקציה לבד לא מוכיח כלום
יש לבדוק שהבסיס אכן מתקיים

שגיאה 3: הנחת מה שצריך להוכיח¶

אל תניחו את $P(n)$!

בצעד האינדוקציה:

✅ נכון: מניחים $P(n-1)$ ומוכיחים $P(n)$
❌ שגוי: מניחים $P(n)$ (זה מה שצריך להוכיח!)

סיכום שיטות האינדוקציה¶

סוג	בסיס	צעד	מתי להשתמש
רגילה	$P(0)$	$P(n-1) \Rightarrow P(n)$	כשיש קשר ישיר בין $n$ ל-$n-1$
מלאה	$P(k)$	$\forall m < n: P(m) \Rightarrow P(n)$	כשצריך להניח על ערכים קטנים יותר (לא רק $n-1$)

תרגילים לתרגול¶

תרגיל 1

הוכיחו באינדוקציה: לכל $n \geq 1$ מתקיים $1 + 2 + 4 + \ldots + 2^{n-1} = 2^n - 1$

תרגיל 2

הוכיחו באינדוקציה: לכל $n \geq 1$ מתקיים $1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$

תרגיל 3

הוכיחו באינדוקציה שלמה: כל מספר טבעי $n \geq 12$ ניתן לייצוג כסכום של כפולות של 4 ו-5. (רמז: $12 = 4 \cdot 3$, $13 = 4 + 4 + 5$, $14 = 4 + 5 + 5$, $15 = 5 \cdot 3$)

מקורות¶

תרגול 1, מתמטיקה בדידה 1
ספר הקורס, פרופ' א. אברון

סוג	בסיס	צעד	מתי להשתמש
רגילה	\(P(0)\)	\(P(n-1) \Rightarrow P(n)\)	כשיש קשר ישיר בין \(n\) ל-\(n-1\)
מלאה	\(P(k)\)	\(\forall m < n: P(m) \Rightarrow P(n)\)	כשצריך להניח על ערכים קטנים יותר (לא רק \(n-1\))