Exercice 47

Les valeurs $1, \dots, k - 1$ occupent $1 + 2 + \cdots + (k - 1) = \frac{k(k - 1)}{2}$ rangs, donc la valeur $k$ occupe les rangs $\frac{k(k - 1)}{2} + 1$ à $\frac{k(k + 1)}{2}$. Ainsi $$u_{n} = k \iff \frac{k(k - 1)}{2} < n \leqslant \frac{k(k + 1)}{2},$$ et $u_{n}$ est le plus petit entier $k$ tel que $\frac{k(k + 1)}{2} \geqslant n$. Pour obtenir une formule avec la partie entière, on écrit la condition comme $k(k - 1) \leqslant 2n - 2 < k(k + 1)$. Le trinôme $k^{2} - k - (2n - 2)$ a pour racine positive $r_{n} = \frac{1 + \sqrt{8n - 7}}{2}$, et la condition devient $k \leqslant r_{n} < k + 1$. $$\boxed{u_{n} = \Big\lfloor \frac{1 + \sqrt{8n - 7}}{2} \Big\rfloor \sim \sqrt{2n}}$$ L'équivalent vient de l'encadrement $r_{n} - 1 < u_{n} \leqslant r_{n}$, dont les deux bornes sont équivalentes à $\sqrt{2n}$. Pour $n = 1, 2, 3, 4$, la formule donne bien $1, 2, 2, 3$.