🔹 Part A – Solutions to Basic-Level Exercises

Exercise 1 – Sum of Natural Numbers

Statement: for all \(n\ge1\) it holds that \(1+2+3+\dots+n = \frac{n(n+1)}{2}\).

Base step:
We check for \(n=1\):

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

Inductive hypothesis:
Assume that for \(n=k\) it holds that: \(1+2+3+\dots+k = \frac{k(k+1)}{2}\).

Inductive step:
We prove that for \(n=k+1\):

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

By the inductive hypothesis: \(1+2+\dots+k+(k+1) = \frac{k(k+1)}{2} + (k+1)\)

Factor out \(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}\)

which is exactly: \(\frac{(k+1)((k+1)+1)}{2}\). ✔

---

Exercise 2 – Sum of Even Numbers

Statement: for all \(n\ge1\) it holds that \(2+4+6+\dots+2n = n(n+1)\).

Base:
For \(n=1\): \(2 = 1\cdot2\). ✔

Inductive hypothesis:
\(2+4+\dots+2k = k(k+1)\).

Step:

We compute: \(2+4+\dots+2k+2(k+1)\)

By the hypothesis: \(2+4+\dots+2k+2(k+1) = k(k+1) + 2(k+1)\)

Factor out \(k+1\): \(k(k+1)+2(k+1) = (k+1)(k+2)\)

which is exactly \((k+1)((k+1)+1)\). ✔

---

Exercise 3 – Sum of Squares

Statement: \(1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}\).

Base:
For \(n=1\): \(1^2 = 1 = \frac{1\cdot2\cdot3}{6}\). ✔

Inductive hypothesis:
\(1^2+2^2+\dots+k^2 = \frac{k(k+1)(2k+1)}{6}\).

Step:

We compute: \(1^2+2^2+\dots+k^2+(k+1)^2\)

By the hypothesis: \(1^2+2^2+\dots+k^2+(k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2\)

Factor out \(k+1\): \((k+1)\left(\frac{k(2k+1)}{6} + (k+1)\right)\)

Convert to a common denominator: \((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)\)

Therefore: \((k+1)\cdot\frac{(k+2)(2k+3)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}\)

which is exactly: \(\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\). ✔

---

Exercise 4 – Inequality: \(2^n \ge n+1\)

Statement: for all \(n\ge1\) it holds that \(2^n \ge n+1\).

Base:
\(n=1\): \(2^1 = 2 \ge 2 = 1+1\). ✔

Inductive hypothesis:
\(2^k \ge k+1\).

Step:

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

Compare with\(k+2\): \(2k+2 \ge k+2 \iff k \ge 0\) – which holds for all \(k\ge1\). ✔

---

Exercise 5 – Inequality: \(3^n > n^2\)

Statement: \(3^n > n^2\) for all \(n\ge1\).

Base:
\(n=1\): \(3^1=3>1=1^2\). \(n=2\): \(9>4\). ✔

Inductive hypothesis:
Assume that\(3^k>k^2\) For \(k\ge2\).

Step:

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

We want to show: \(3k^2 > (k+1)^2\).

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

For \(k\ge2\) the expression is positive (direct check: for \(k=2\) we get \(8-4-1=3>0\), and it only increases). Therefore \(3^{k+1}>(k+1)^2\). ✔

---

Exercise 6 – Inequality with Factorial: \(n!\ge2^{n-1}\)

Statement: for all \(n\ge1\): \(n! \ge 2^{\,n-1}\).

Base:
\(n=1\): \(1! = 1 \ge 2^0 = 1\). ✔

Inductive hypothesis:
\(k! \ge 2^{k-1}\).

Step:

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

We want to show: \((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\), which holds. ✔

---

Exercise 7 – Sequence: \(a_{n+1}=a_n+2\)

The sequence is defined by: \(a_1=1,\quad a_{n+1}=a_n+2\). Claim: \(a_n=2n-1\).

Base:
\(a_1=1\), and the right-hand side: \(2\cdot1-1=1\). ✔

Inductive hypothesis:
\(a_k = 2k-1\).

Step:

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

---

Exercise 8 – Divisibility: \(5^n-1\) by 4

Statement: for all \(n\ge1\) the number \(5^n-1\) is divisible by 4.

Base:
\(n=1\): \(5^1-1=4\) – divisible by 4. ✔

Hypothesis:
\(5^k-1\) is divisible by 4.

Step:

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

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

By the hypothesis \(5^k-1\) a multiple of 4, so \(5(5^k-1)\) plus 4 – also a multiple of 4. ✔

---

Exercise 9 – Divisibility: \(7^n-1\) by 6

Statement: for all \(n\ge1\) the number \(7^n-1\) is divisible by 6.

Base:
\(n=1\): \(7-1=6\). ✔

Hypothesis:
\(7^k-1\) is divisible by 6.

Step:

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

Again, \(7^k-1\) a multiple of 6, so \(7(7^k-1)+6\) also a multiple of 6. ✔

---

Exercise 10 – Divisibility: \(n^3+2n\) by 3

Statement: for all \(n\ge1\) the number \(n^3+2n\) is divisible by 3.

Convenient approach: check by residues modulo 3.

• If \(n\equiv0\pmod3\) – clearly the expression is divisible by 3.
• If \(n\equiv1\pmod3\): \(n^3\equiv1\), \(2n\equiv2\), total \(\equiv0\).
• If \(n\equiv2\pmod3\): \(n^3\equiv8\equiv2\), \(2n\equiv4\equiv1\), total \(\equiv0\).

Therefore \(n^3+2n\) is divisible by 3 for all \(n\). ✔