🔹 חלק א' – פתרונות לתרגילים ברמת בסיס

תרגיל 1 – סכום מספרים טבעיים

הטענה: לכל \(n\ge1\) מתקיים \(1+2+3+\dots+n = \frac{n(n+1)}{2}\).

שלב הבסיס:
נבדוק עבור \(n=1\):

\(1 = \frac{1\cdot2}{2} = 1\) ✔

הנחת האינדוקציה:
נניח כי עבור \(n=k\) מתקיים: \(1+2+3+\dots+k = \frac{k(k+1)}{2}\).

צעד האינדוקציה:
נוכיח שעבור \(n=k+1\):

\(1+2+\dots+k+(k+1)\)

לפי הנחת האינדוקציה: \(1+2+\dots+k+(k+1) = \frac{k(k+1)}{2} + (k+1)\)

נוציא גורם משותף \(k+1\): \(\frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right)\)

\((k+1)\left(\frac{k}{2} + 1\right) = (k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}\)

וזה בדיוק: \(\frac{(k+1)((k+1)+1)}{2}\). ✔

תרגיל 2 – סכום מספרים זוגיים

הטענה: לכל \(n\ge1\) מתקיים \(2+4+6+\dots+2n = n(n+1)\).

בסיס:
עבור \(n=1\): \(2 = 1\cdot2\). ✔

הנחת אינדוקציה:
\(2+4+\dots+2k = k(k+1)\).

צעד:

נחשב: \(2+4+\dots+2k+2(k+1)\)

לפי ההנחה: \(2+4+\dots+2k+2(k+1) = k(k+1) + 2(k+1)\)

נוציא גורם משותף \(k+1\): \(k(k+1)+2(k+1) = (k+1)(k+2)\)

וזה בדיוק \((k+1)((k+1)+1)\). ✔

תרגיל 3 – סכום ריבועים

הטענה: \(1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}\).

בסיס:
עבור \(n=1\): \(1^2 = 1 = \frac{1\cdot2\cdot3}{6}\). ✔

הנחת אינדוקציה:
\(1^2+2^2+\dots+k^2 = \frac{k(k+1)(2k+1)}{6}\).

צעד:

נחשב: \(1^2+2^2+\dots+k^2+(k+1)^2\)

לפי ההנחה: \(1^2+2^2+\dots+k^2+(k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2\)

נוציא גורם משותף \(k+1\): \((k+1)\left(\frac{k(2k+1)}{6} + (k+1)\right)\)

נביא למכנה משותף: \((k+1)\left(\frac{k(2k+1) + 6(k+1)}{6}\right)\)

\(k(2k+1)+6(k+1)=2k^2+k+6k+6=2k^2+7k+6=(k+2)(2k+3)\)

לכן: \((k+1)\cdot\frac{(k+2)(2ק+3)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}\)

וזה בדיוק: \(\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\). ✔

תרגיל 4 – אי־שוויון: \(2^n \ge n+1\)

הטענה: לכל \(n\ge1\) מתקיים \(2^n \ge n+1\).

בסיס:
\(n=1\): \(2^1 = 2 \ge 2 = 1+1\). ✔

הנחת אינדוקציה:
\(2^k \ge k+1\).

צעד:

\(2^{k+1} = 2\cdot2^k \ge 2(k+1) = 2k+2\)

נשווה ל־\(k+2\): \(2k+2 \ge k+2 \iff k \ge 0\) – נכון עבור כל \(k\ge1\). ✔

תרגיל 5 – אי־שוויון: \(3^n > n^2\)

הטענה: \(3^n > n^2\) לכל \(n\ge1\).

בסיס:
\(n=1\): \(3^1=3>1=1^2\). \(n=2\): \(9>4\). ✔

הנחת אינדוקציה:
נניח ש־\(3^k>k^2\) עבור \(k\ge2\).

צעד:

\(3^{k+1} = 3\cdot3^k > 3k^2\)

רוצים להראות: \(3k^2 > (k+1)^2\).

\(3k^2 - (k+1)^2 = 3k^2 - (k^2+2k+1) = 2k^2 - 2k - 1\)

עבור \(k\ge2\) הביטוי חיובי (בדיקה ישירה: עבור \(k=2\) מתקבל \(8-4-1=3>0\), והוא רק גדל). לכן \(3^{k+1}>(k+1)^2\). ✔

תרגיל 6 – אי־שוויון עם עצרת: \(n!\ge2^{n-1}\)

הטענה: לכל \(n\ge1\): \(n! \ge 2^{\,n-1}\).

בסיס:
\(n=1\): \(1! = 1 \ge 2^0 = 1\). ✔

הנחת אינדוקציה:
\(k! \ge 2^{k-1}\).

צעד:

\((k+1)! = (k+1)\cdot k! \ge (k+1)\cdot 2^{k-1}\)

רוצים להראות: \((k+1)\cdot2^{k-1} \ge 2^k\).

\((k+1)\cdot2^{k-1} \ge 2\cdot2^{k-1} \iff k+1 \ge 2\iff k\ge1\), וזה נכון. ✔

תרגיל 7 – רצף: \(a_{n+1}=a_n+2\)

הרצף מוגדר: \(a_1=1,\quad a_{n+1}=a_n+2\). טענה: \(a_n=2n-1\).

בסיס:
\(a_1=1\), וצד ימין: \(2\cdot1-1=1\). ✔

הנחת אינדוקציה:
\(a_k = 2k-1\).

צעד:

\(a_{k+1}=a_k+2=(2k-1)+2=2k+1=2(k+1)-1\). ✔

תרגיל 8 – התחלקות: \(5^n-1\) ב־4

הטענה: לכל \(n\ge1\) המספר \(5^n-1\) מתחלק ב־4.

בסיס:
\(n=1\): \(5^1-1=4\) – מתחלק ב־4. ✔

הנחה:
\(5^k-1\) מתחלק ב־4.

צעד:

\(5^{k+1}-1 = 5\cdot5^k-1\)

\(=5\cdot5^k-5+4 = 5(5^k-1)+4\)

לפי ההנחה \(5^k-1\) כפולה של 4, ולכן גם \(5(5^k-1)\) ועוד 4 – כפולה של 4. ✔

תרגיל 9 – התחלקות: \(7^n-1\) ב־6

הטענה: לכל \(n\ge1\) המספר \(7^n-1\) מתחלק ב־6.

בסיס:
\(n=1\): \(7-1=6\). ✔

הנחה:
\(7^k-1\) מתחלק ב־6.

צעד:

\(7^{k+1}-1 = 7\cdot7^k-1 = 7(7^k-1)+6\)

שוב, \(7^k-1\) כפולה של 6, ולכן גם \(7(7^k-1)+6\) כפולה של 6. ✔

תרגיל 10 – התחלקות: \(n^3+2n\) ב־3

הטענה: לכל \(n\ge1\) המספר \(n^3+2n\) מתחלק ב־3.

דרך נוחה: בדיקה לפי שאריות מודולו 3.

• אם \(n\equiv0\pmod3\) – ברור שהביטוי מתחלק ב־3.
• אם \(n\equiv1\pmod3\): \(n^3\equiv1\), \(2n\equiv2\), סה״כ \(\equiv0\).
• אם \(n\equiv2\pmod3\): \(n^3\equiv8\equiv2\), \(2n\equiv4\equiv1\), סה״כ \(\equiv0\).

לכן \(n^3+2n\) מתחלק ב־3 לכל \(n\). ✔