4. Determine the smallest real number $p$ such that the inequality

$$
\sqrt{1^{2}+1}+\sqrt{2^{2}+1}+\sqrt{3^{2}+1}+\ldots+\sqrt{n^{2}+1} \leqq \frac{1}{2} n(n+p)
$$

holds for every natural number $n$.
SOLUTION. For $n=1$, the given inequality has the form

$$
\sqrt{2} \leqq \frac{1}{2}(p+1), \quad \text { or } \quad p \geqq 2 \sqrt{2}-1
$$

Let $p_{1}=2 \sqrt{2}-1$. We have found that no number $p$ smaller than $p_{1}$ has the required property. The number $p_{1}$ is thus the sought number if we show that for every $n \geqq 1$ it holds that

$$
\sqrt{1^{2}+1}+\sqrt{2^{2}+1}+\sqrt{3^{2}+1}+\ldots+\sqrt{n^{2}+1} \leqq \frac{1}{2} n\left(n+p_{1}\right) .
$$

We will prove this by mathematical induction.

(i) For $n=1$, inequality (1) is satisfied due to the way we determined the number $p_{1}$.

(ii) Assume that inequality (1) holds for some natural number $n$ and we will show that it also holds for the natural number $n+1$. Let

$$
F(n)=\sqrt{1^{2}+1}+\sqrt{2^{2}+1}+\sqrt{3^{2}+1}+\ldots+\sqrt{n^{2}+1} \leqq \frac{1}{2} n\left(n+p_{1}\right) .
$$

Since

$$
F(n+1)=F(n)+\sqrt{(n+1)^{2}+1},
$$

according to the induction hypothesis (2) and the definition of $p_{1}$,

$$
F(n+1) \leqq \frac{1}{2} n(n+2 \sqrt{2}-1)+\sqrt{(n+1)^{2}+1} .
$$

Now we will prove the inequality

$$
\frac{1}{2} n(n+2 \sqrt{2}-1)+\sqrt{(n+1)^{2}+1} \leqq \frac{1}{2}(n+1)(n+1+2 \sqrt{2}-1) .
$$

By rearranging, we get an equivalent inequality

$$
\sqrt{(n+1)^{2}+1} \leqq n+\sqrt{2}
$$

whose validity we can easily verify by squaring both sides:

$$
(n+\sqrt{2})^{2}=n^{2}+2 \sqrt{2} n+2>n^{2}+2 n+2=(n+1)^{2}+1
$$

According to (3) and (4),

$$
F(n+1) \leqq \frac{1}{2}(n+1)(n+1+2 \sqrt{2}-1)=\frac{1}{2}(n+1)\left(n+1+p_{1}\right),
$$

which is inequality (1) for the value $n+1$.

Conclusion. The sought real number is $p=2 \sqrt{2}-1$.

GUIDING PROBLEM:

Determine the smallest real number $p$ such that the inequality

$$
1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots+\frac{1}{2^{n}-1} \leqq p \cdot n
$$

holds for every natural number $n$. $p=1$. For $n=1$ we get $p \geqq 1$; the property of the number $p=1$ can be proven by mathematical induction, where the sum of the "new" fractions $1 /\left(2^{n}+k\right), k \in\left\{0,1, \ldots, 2^{n}-1\right\}$, is estimated from above by the $2^{n}$-fold of the largest of them.