The first term of a sequence is $a_{1}=1$ and for each subsequent term,

$$
a_{n+1}=1+\frac{n}{a_{n}}, \quad n=1,2,3 \ldots
$$

Does the following limit exist? If it does, determine it.

$$
\lim _{n \rightarrow \infty}\left(a_{n}-\sqrt{n}\right)
$$
We will prove by complete induction that the sequence $a_{n}$ is monotonically increasing. It is clear from the recursive formula that an upper estimate for $a_{n}$ implies a lower estimate for $a_{n+1}$. Therefore, it is not expected that from $a_{n} \leqq a_{n+1}$ we can conclude $a_{n+1} \leqq a_{n+2}$. It is therefore advisable to formulate the statement to be proved by induction as $a_{n-1} \leqq a_{n} \leqq a_{n+1}$. By direct calculation, $1=a_{1} \leqq 2=a_{2} \leqq 2=a_{3}$, so the statement holds for $n=2$.

Assume that for some fixed $n$, $a_{n-1} \leqq a_{n} \leqq a_{n+1}$, and we need to show that this implies $a_{n} \leqq a_{n+1} \leqq a_{n+2}$. The inequality $a_{n} \leqq a_{n+1}$ holds by the induction hypothesis, so we need to prove $a_{n+1} \leqq a_{n+2}$.

\[
a_{n+2}=1+\frac{n+1}{a_{n+1}}=1+\frac{n+1}{1+\frac{n}{a_{n}}} \geqq 1+\frac{n+1}{1+\frac{n-1+1}{a_{n-1}}}=1+\frac{n+1}{a_{n}+\frac{1}{a_{n-1}}}
\]

The estimate $a_{n} \geqq 1$ clearly holds for all $n$, so

\[
1-\frac{1}{a_{n-1}} \geqq 0, \quad \text{that is} \quad a_{n}=1+\frac{n-1}{a_{n-1}} \geqq \frac{n}{a_{n-1}}
\]

From the inequality $a_{n} \geqq \frac{n}{a_{n-1}}$, it immediately follows that $\frac{n+1}{a_{n}+\frac{1}{a_{n-1}}} \geqq \frac{n}{a_{n}}$, that is, $a_{n+2} \geqq 1+\frac{n}{a_{n}}=a_{n+1}$, and thus the induction proof is complete.

Since by definition $a_{n} \cdot a_{n+1}=a_{n}+n$, and by the now proven monotonicity $a_{n}^{2} \leqq a_{n}+n$, we have

\[
\left(a_{n}-\frac{1}{2}\right)^{2} \leq n+\frac{1}{4}, \quad n=1,2, \ldots
\]

On the other hand,

\[
\left(a_{n}-\frac{1}{2}\right)^{2}=\left(\frac{1}{2}+\frac{n-1}{a_{n-1}}\right)^{2}=\frac{1}{4}+\frac{n-1}{a_{n-1}}\left(1+\frac{n-1}{a_{n-1}}\right)=\frac{1}{4}+\frac{n-1}{a_{n-1}} a_{n} \geqq \frac{1}{4}+n-1=n-\frac{3}{4}
\]

since

\[
\frac{a_{n}}{a_{n-1}} \geqq 1
\]

Taking the square root, we get

\[
\sqrt{n-\frac{3}{4}} \leqq a_{n}-\frac{1}{2} \leqq \sqrt{n+\frac{1}{4}}
\]

from which

\[
\frac{1}{2}+\sqrt{n-\frac{3}{4}}-\sqrt{n} \leqq a_{n}-\sqrt{n} \leqq \frac{1}{2}+\sqrt{n+\frac{1}{4}}+\sqrt{n}
\]

For any constant $c$,

\[
\sqrt{n+c}-\sqrt{n}=\frac{c}{\sqrt{n+c}+\sqrt{n}} \rightarrow 0, \quad \text{if} \quad n \rightarrow \infty
\]

that is, $\lim _{n \rightarrow \infty}\left(a_{n}-\sqrt{n}\right)=\frac{1}{2}$

Páles Zsolt (Sátoraljaújhely, Kossuth L. (Gimn.))