תרגילי אינדוקציה¶

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

שאלה: הוכיחו שלכל $n$ טבעי מתקיים: $$0 + 1 + \ldots + n = \frac{n(n+1)}{2}$$

פתרון

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

צעד: יהי $n \geq 1$ טבעי. נניח נכונות עבור $n-1$:

\[0 + 1 + \ldots + n = (0 + 1 + \ldots + (n-1)) + n\]

\[\stackrel{I.H.}{=} \frac{(n-1)n}{2} + n = \frac{n^2 - n + 2n}{2} = \frac{n^2 + n}{2} = \frac{n(n+1)}{2} \checkmark\]

תרגיל 2 - חזקות של 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{I.H.}{>} 2n^2\]

צ"ל: $2n^2 > (n+1)^2$

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

\[= (n-1)^2 - 2 \stackrel{n \geq 5}{>} 16 - 2 = 14 > 0 \checkmark\]

תרגיל 3 - מכפלת ראשוניים (אינדוקציה מלאה)¶

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

פתרון

בסיס: עבור $n = 2$: המספר 2 ראשוני, ולכן מכפלה (טריוויאלית) של ראשוניים. $\checkmark$

צעד (אינדוקציה מלאה): יהי $n \geq 3$. נניח שהטענה נכונה לכל $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$.

מהנחת האינדוקציה, קיימים ראשוניים $p_1, \ldots, p_{k_1}$ ו-$q_1, \ldots, q_{k_2}$ כך ש: $$m_1 = p_1 \cdots p_{k_1}, \quad m_2 = q_1 \cdots q_{k_2}$$

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

למה אינדוקציה רגילה לא עובדת?

באינדוקציה רגילה היינו מניחים ש-$n-1$ מכפלת ראשוניים.

אבל מ-$n-1 = p_1 \cdots p_k$ נקבל רק $n = p_1 \cdots p_k + 1$ - שזה לא מכפלת ראשוניים!

תרגיל 4 - פרדוקס הסוסים (טעות נפוצה)¶

שאלה: מצאו את הטעות בהוכחה הבאה:

"טענה": כל הסוסים בעולם הם באותו צבע.

"הוכחה": באינדוקציה על גודל הקבוצה $n$.

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

הטעות

הטעות היא במעבר מ-$n=1$ ל-$n=2$.

עבור $n=1$ ו-$n+1=2$ סוסים $a_1, a_2$:

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

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

הצעד תקף רק כאשר $n \geq 2$, כי אז: - $\{a_1, \ldots, a_n\}$ מכילה לפחות את $a_2$ - $\{a_2, \ldots, a_{n+1}\}$ מכילה לפחות את $a_2$

תרגיל 5 - סדרת פיבונאצ'י¶

הגדרה: $F_0 = 0, F_1 = 1$, ולכל $n \geq 2$: $F_n = F_{n-1} + F_{n-2}$

שאלה: הוכיחו שלכל $n \geq 1$: $F_1 + F_3 + \ldots + F_{2n-1} = F_{2n}$

פתרון

בסיס: $n = 1$: $$F_1 = 1 = F_2 \checkmark$$

צעד: נניח נכונות עבור $n$ ונוכיח ל-$n+1$:

\[F_1 + F_3 + \ldots + F_{2n-1} + F_{2n+1}\]

\[\stackrel{I.H.}{=} F_{2n} + F_{2n+1}\]

\[= F_{2n+2} = F_{2(n+1)} \checkmark\]

טבלת סיכום¶

סוג אינדוקציה	מתי להשתמש	דוגמה
רגילה	$P(n)$ תלוי רק ב-$P(n-1)$	סכום סדרה
מלאה	$P(n)$ תלוי בכל $P(k)$ עבור $k < n$	מכפלת ראשוניים
מ-$k$	הטענה נכונה רק מ-$n \geq k$	$2^n > n^2$ מ-$n=5$

טעויות נפוצות¶

טעויות נפוצות

שכחת בסיס - חייבים להוכיח את המקרה הראשון
בסיס שגוי - כשהטענה מתחילה מ-$k$, הבסיס הוא $n=k$
אי-שימוש בהנחה - בצעד חייבים להשתמש בהנחת האינדוקציה
הנחה שגויה - מניחים ל-$n+1$ במקום ל-$n$
קפיצה גדולה - כמו בפרדוקס הסוסים, חייבים לבדוק שהצעד תקף

סוג אינדוקציה	מתי להשתמש	דוגמה
רגילה	\(P(n)\) תלוי רק ב-\(P(n-1)\)	סכום סדרה
מלאה	\(P(n)\) תלוי בכל \(P(k)\) עבור \(k < n\)	מכפלת ראשוניים
מ-\(k\)	הטענה נכונה רק מ-\(n \geq k\)	\(2^n > n^2\) מ-\(n=5\)