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

בסיס: עבור $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$

$\overset{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$

בסיס: עבור $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 \overset{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 \overset{n \geq 5}{>} 16 - 2 = 14 > 0 \checkmark$

בסיס: עבור $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$: $F_1 = 1 = F_2 \checkmark$

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

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

$\overset{I.H.}{=} F_{2n} + F_{2n+1}$

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