שאלות מבחן בנושא אינדוקציה¶

מבחן 2019 מועד ב - שאלה 5ב¶

נוסחת נסיגה עם אינדוקציה¶

שאלה: שני פוליטיקאים, אמנון ותמר, רוצים לבקר ב-$n$ ערים, עיר אחת ביום, במשך $n$ ימים. הם מסכימים שיבקרו בכל עיר באותו יום, או בימים עוקבים שהפרשם לכל היותר יום אחד.

נסמן ב-$a_n$ את מספר הדרכים החוקיות. מצאו נוסחת נסיגה ל-$a_n$ עם תנאי התחלה מספיקים.

פתרון

תנאי התחלה: $$a_0 = 1, \quad a_1 = 1$$

נוסחת נסיגה: $$a_n = n \cdot a_{n-1} + n(n-1) \cdot a_{n-2}$$

הסבר:

נפריד לפי איך אמנון ותמר מתחילים:

מקרה 1: שניהם מתחילים באותה עיר.

יש $n$ אפשרויות לבחור עיר התחלה
לכל בחירה, יש $a_{n-1}$ דרכים להשלים את שאר הלו"ז
תרומה: $n \cdot a_{n-1}$

מקרה 2: הם מתחילים בערים שונות.

הם חייבים לבקר באותה עיר ביום השני (בסדר הפוך)
יש $n$ אפשרויות לעיר של אמנון ו-$n-1$ לתמר
היום השני נקבע באופן יחיד (הם מחליפים)
לכל בחירה כזו, יש $a_{n-2}$ דרכים להשלים
תרומה: $n(n-1) \cdot a_{n-2}$

סה"כ: $a_n = n \cdot a_{n-1} + n(n-1) \cdot a_{n-2}$ ✓

מבחן 2024 מועד ב' - שאלה 2ד¶

אינדוקציה על הפרש¶

הגדרה: יחס $R$ על $A$ נקרא מחבר מקורות אם: $$\forall a, b, c \in A. (\langle a, c \rangle \in R \land \langle b, c \rangle \in R) \rightarrow \langle a, b \rangle \in R$$

נתון: $S = \{\langle n+1, n \rangle \mid n \in \mathbb{N}\}$ ויחס $T \subseteq \mathbb{N} \times \mathbb{N}$.

שאלה: הוכיחו: אם $T$ מחבר מקורות ו-$S \subseteq T$, אז $(\mathbb{N}^+ \times \mathbb{N}^+) \subseteq T$.

פתרון באינדוקציה על ההפרש

נוכיח טענה חזקה יותר: $$\forall k \in \mathbb{N}. \forall \langle a, b \rangle \in \mathbb{N}^+ \times \mathbb{N}^+. (|a - b| = k) \rightarrow (\langle a, b \rangle \in T \land \langle b, a \rangle \in T)$$

בסיס ($k = 0$): יהי $a = b \in \mathbb{N}^+$.

מ-$a = n+1$ לאיזשהו $n \in \mathbb{N}$, יש לנו $\langle a, a-1 \rangle = \langle n+1, n \rangle \in S \subseteq T$.

מ-$T$ מחבר מקורות ו-$\langle a, a-1 \rangle \in T$, נקבל $\langle a, a \rangle \in T$ ✓

צעד: נניח שהטענה נכונה לכל זוגות עם הפרש $k$. יהיו $a, b$ עם $|a - b| = k+1$.

מקרה $a > b$:

יש לנו $\langle a, a-1 \rangle \in S \subseteq T$ (מהגדרת $S$)
לפי הנחת האינדוקציה, $(a-1) - b = k$, לכן $\langle b, a-1 \rangle \in T$
מ-$T$ מחבר מקורות ו-$\langle a, a-1 \rangle, \langle b, a-1 \rangle \in T$, נקבל $\langle a, b \rangle \in T$ ✓

מקרה $b > a$: סימטרי.

מבחן 2020 מועד א - שאלה 4¶

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

הגדרה: סדרה $(a_n)_{n \in \mathbb{N}}$ מוגדרת: $$a_0 = 1, \quad a_1 = 2, \quad \forall n \geq 1. a_{n+1} = 2a_n + a_{n-1}$$

שאלה: הוכיחו שלכל $n \in \mathbb{N}$: $$a_n = \frac{(1+\sqrt{2})^{n+1} - (1-\sqrt{2})^{n+1}}{2\sqrt{2}}$$

פתרון באינדוקציה מלאה

נסמן $\alpha = 1 + \sqrt{2}$, $\beta = 1 - \sqrt{2}$.

שימו לב: $\alpha + \beta = 2$, $\alpha \beta = -1$, והם שורשי $x^2 - 2x - 1 = 0$.

בסיס ($n = 0$): $$\frac{\alpha - \beta}{2\sqrt{2}} = \frac{2\sqrt{2}}{2\sqrt{2}} = 1 = a_0 \checkmark$$

בסיס ($n = 1$): $$\frac{\alpha^2 - \beta^2}{2\sqrt{2}} = \frac{(\alpha-\beta)(\alpha+\beta)}{2\sqrt{2}} = \frac{2\sqrt{2} \cdot 2}{2\sqrt{2}} = 2 = a_1 \checkmark$$

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

\[a_{n+1} = 2a_n + a_{n-1} = 2 \cdot \frac{\alpha^{n+1} - \beta^{n+1}}{2\sqrt{2}} + \frac{\alpha^n - \beta^n}{2\sqrt{2}}\]

\[= \frac{2\alpha^{n+1} - 2\beta^{n+1} + \alpha^n - \beta^n}{2\sqrt{2}}\]

\[= \frac{\alpha^n(2\alpha + 1) - \beta^n(2\beta + 1)}{2\sqrt{2}}\]

מ-$\alpha^2 = 2\alpha + 1$ ו-$\beta^2 = 2\beta + 1$ (שניהם שורשי המשוואה):

\[= \frac{\alpha^n \cdot \alpha^2 - \beta^n \cdot \beta^2}{2\sqrt{2}} = \frac{\alpha^{n+2} - \beta^{n+2}}{2\sqrt{2}} \checkmark\]

מבחן 2023 מועד ב - שאלה 5¶

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

שאלה: תהי $A$ קבוצה סופית ו-$R$ יחס אנטי-סימטרי על $A$. הוכיחו שקיימת פונקציה $f: A \to \mathbb{N}$ כך שלכל $a, b \in A$: $$\langle a, b \rangle \in R \land a \neq b \implies f(a) < f(b)$$

פתרון באינדוקציה על גודל הקבוצה

אינדוקציה על $|A| = n$.

בסיס ($n = 0$): $A = \emptyset$, הפונקציה הריקה מקיימת ✓

בסיס ($n = 1$): $A = \{a\}$, נגדיר $f(a) = 0$. אין זוגות שונים, לכן מתקיים ✓

צעד: נניח נכונות לקבוצות בגודל $n$. תהי $|A| = n+1$.

טענת עזר: קיים $m \in A$ "מקסימלי", כלומר לא קיים $b \neq m$ עם $\langle m, b \rangle \in R$.

הוכחת טענת עזר: נניח בשלילה שלכל $a \in A$ קיים $b \neq a$ עם $\langle a, b \rangle \in R$. נבנה סדרה $a_0, a_1, a_2, \ldots$ כך ש-$\langle a_i, a_{i+1} \rangle \in R$. מ-$A$ סופית, קיימים $i < j$ עם $a_i = a_j$. מטרנזיטיביות "שרשרת", $\langle a_i, a_{i+1} \rangle \in R$ ו-$\langle a_{i+1}, a_i \rangle \in R$ (מהשרשרת חזרה). מאנטי-סימטריות: $a_i = a_{i+1}$, סתירה.

המשך הוכחה: יהי $m$ מקסימלי. נגדיר $A' = A \setminus \{m\}$, ו-$|A'| = n$.

לפי הנחת האינדוקציה, קיימת $g: A' \to \mathbb{N}$ המקיימת את התנאי.

נגדיר $f: A \to \mathbb{N}$: $$f(a) = \begin{cases} g(a) & a \neq m \\ \max\{g(a) \mid a \in A'\} + 1 & a = m \end{cases}$$

בדיקת התנאי: יהיו $a \neq b$ עם $\langle a, b \rangle \in R$.

אם $a, b \neq m$: לפי תכונת $g$, $f(a) = g(a) < g(b) = f(b)$ ✓
אם $b = m$: $f(a) = g(a) \leq \max < f(m)$ ✓
אם $a = m$: בלתי אפשרי, כי $m$ מקסימלי ואין $b \neq m$ עם $\langle m, b \rangle \in R$.

טבלת סיכום¶

סוג אינדוקציה	מתי להשתמש	שאלות
רגילה	טענה על $n$ תלויה רק ב-$n-1$	2020-4
מלאה/חזקה	טענה על $n$ תלויה בכל $k < n$	2019-5ב, 2024Bb-2ד
על הפרש	טענה על זוגות עם הפרש מסוים	2024Bb-2ד
על גודל קבוצה	טענה על קבוצות סופיות	2023Bb-5

טיפים¶

טיפים לשאלות אינדוקציה

בסיס: בדקו את המקרה/ים הקטנים ביותר
צעד: כתבו במפורש "נניח נכונות ל-$n$ (או לכל $k < n$)"
שימוש בהנחה: הראו איפה בדיוק משתמשים בהנחת האינדוקציה
נוסחאות נסיגה: זהו את המבנה הרקורסיבי של הבעיה
אינדוקציה מלאה: כשצריכים יותר ממקרה אחד קודם
אינדוקציה על הפרש: שימושי ליחסים וזוגות מספרים

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

שכחת בסיס האינדוקציה
הנחה שהטענה נכונה ל-$n+1$ במקום ל-$n$
אי-שימוש בהנחת האינדוקציה בצעד
בסיס לא מספיק (למשל, צריך שני בסיסים לנסיגה מסדר 2)

סוג אינדוקציה	מתי להשתמש	שאלות
רגילה	טענה על \(n\) תלויה רק ב-\(n-1\)	2020-4
מלאה/חזקה	טענה על \(n\) תלויה בכל \(k < n\)	2019-5ב, 2024Bb-2ד
על הפרש	טענה על זוגות עם הפרש מסוים	2024Bb-2ד
על גודל קבוצה	טענה על קבוצות סופיות	2023Bb-5