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

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

בסיס: עבור $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{aligned} 0 + 1 + \ldots + n &= (0 + 1 + \ldots + (n-1)) + n \\ &\overset{*}{=} \frac{(n-1)n}{2} + n \\ &= \frac{n^2 - n + 2n}{2} \\ &= \frac{n^2 + n}{2} = \frac{n(n+1)}{2} \end{aligned}$

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

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

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

• בסיס: $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$.

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

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

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

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