Soit $N$ un nombre naturel supérieur ou égal à $1$. Pour tout réel $x$, notez $\left\lfloor x \right\rfloor$ la partie entière de $x$, désignant le plus grand entier inférieur ou égal à $x.$
Pour simplifier les notations, définissez la fonction $f$ sur $\N^{*}$ par $\forall n\in\N^{*}, f(n) =\left\lfloor \frac{n+\left\lfloor \frac{N}{n}\right\rfloor}{2}\right\rfloor.$
Considérez la suite définie par $u_0 = N$ et
\forall n\in\N, u_{n+1}=\begin{cases}
f(u_n) \quad\text{ si } f(u_n) < u_n\\
u_n \quad\text{ si } f(u_n) \geq u_n.\\
\end{cases}Cet article s’inscrit dans la preuve du résultat suivant : la suite $(u_n)$ est stationnaire à partir d’un certain rang et sa limite est égale à la racine carrée entière de $N$, c’est–à-dire l’unique entier $m$ tel que $m^2\leq N < (m+1)^2.$
Le but de cet article est de mettre en exergue une démonstration de la proposition suivante :
$\left\lfloor \sqrt{N} \right\rfloor$ minore la suite $(u_n)_{n\geq 0}.$
Afin de parvenir à ce résultat, vous allez démontrer les lemmes suivants, qui faciliteront les calculs pour la suite.
Démontrez le lemme $\forall n\in\N^{*}, f(n) = \left\lfloor \frac{n+ \frac{N}{n}}{2}\right\rfloor$
Pour voir pourquoi cela est bien le cas, considérez un entier $n\in\N^{*}$ et posez $p = \left\lfloor \frac{N}{n}\right\rfloor.$
Par définition de la partie entière, l’encadrement $p\leq \frac{N}{n} < p+1$ est vérifié.
Par suite, $n+p \leq n+ \frac{N}{n} < n+p+1$ et après division par $2$ il vient $\frac{n+p}{2} \leq \frac{n+ \frac{N}{n} }{2}< \frac{n+p+1}{2}.$
Premier cas : l’entier naturel $n+p$ est pair
Il existe $\ell\in\N$ tel que $n+p = 2\ell.$
D’autre part, vous avez $\ell \leq \frac{n+ \frac{N}{n} }{2}< \ell +\frac{1}{2} < \ell + 1.$
Vous déduisez que $\ell = \left\lfloor \frac{n+ \frac{N}{n} }{2} \right\rfloor.$
Or, comme $\ell$ est entier, il vient successivement :
\begin{aligned}
\ell &= \left\lfloor \ell \right\rfloor \\
&= \left\lfloor \frac{n+ p }{2} \right\rfloor\\
&= \left\lfloor \frac{n+ \left\lfloor \frac{N}{n}\right\rfloor }{2} \right\rfloor\\
\end{aligned}
ce qui prouve le résultat.
Second cas : l’entier naturel $n+p$ est impair
Il existe $\ell\in\N$ tel que $n+p = 2\ell+1.$
Vous avez $\ell +\frac{1}{2} \leq \frac{n+p}{2} \leq \frac{n+ \frac{N}{n} }{2}< \frac{n+p+1}{2}\leq \frac{2\ell + 2}{2} \leq \ell + 1.$
Vous déduisez $\ell \leq \frac{n+ \frac{N}{n} }{2} < \ell +1.$
Ainsi, comme prédédemment $\ell = \left\lfloor \frac{n+ \frac{N}{n} }{2} \right\rfloor.$
Comme $\frac{n+p}{2}= \ell+\frac{1}{2}$ vous avez $\ell \leq \frac{n+p}{2} < \ell +1$ donc $\ell = \left\lfloor \frac{n+ p }{2} \right\rfloor$, ce qui prouve $\ell = \left\lfloor \frac{n+ \left\lfloor \frac{N}{n}\right\rfloor }{2} \right\rfloor.$
Démontrez que, pour tout $n\in\N^{*}, \sqrt{N}\leq \frac{n+\frac{N}{n}}{2}$
Cette inégalité s’obtient par soustraction et utilisation d’identités remarquables.
\begin{aligned}
\frac{n+\frac{N}{n}}{2} – \sqrt{N} &= \frac{n+\frac{N}{n} – 2\sqrt{N}}{2}\\
&=\frac{n^2+N – 2n\sqrt{N}}{2n}\\
&=\frac{(n-\sqrt{N})^2}{2n}.
\end{aligned}
La positivité du carré et de l’entier $n$ montrent que la fraction obtenue est positive ce qui conclut.
Démontrez la minoration $\forall n\in\N^{*}, f(n) \geq \left\lfloor \sqrt{N} \right\rfloor$
Soit $n$ un entier naturel non nul.
De ce qui précède, vous avez successivement :
\begin{aligned}
f(n) \geq \frac{n+\frac{N}{n}}{2} \\
\geq \left\lfloor \frac{n+\frac{N}{n}}{2} \right\rfloor.
\end{aligned}
Or, $ \frac{n+\frac{N}{n}}{2} \geq \sqrt{N}.$
Comme la fonction partie entière est croissante, vous déduisez $\left\lfloor \frac{n+\frac{N}{n}}{2}\right\rfloor \geq \left\lfloor \sqrt{N} \right\rfloor.$
Concluez en utilisant une récurrence
Pour tout entier naturel $n$, notez $P(n)$ la propriété : « $u_n \geq \left\lfloor \sqrt{N} \right\rfloor$ ».
Initialisation. Pour $n = 0$, $u_0 = N.$ Comme $N$ est un entier naturel non nul, $N\geq 1.$ En multipliant par $N$, il vient $N^2\geq N$ et par croissance de la fonction racine carrée, $N\geq \sqrt{N}.$ Par définition de la partie entière, $\sqrt{N} \geq \left\lfloor \sqrt{N} \right\rfloor.$ Mis bout à bout, vous obtenez $N \geq \left\lfloor \sqrt{N} \right\rfloor$ et $u_0 \geq \left\lfloor \sqrt{N} \right\rfloor$ donc $P(0)$ est vérifiée.
Hérédité. Soit $n$ un entier naturel tel que $P(n)$ soit vérifiée.
1er cas : $u_{n+1} = f(u_n).$ Il a été établi ci-dessus que, pour tout entier $m\geq 1$, $f(m) \geq \left\lfloor \sqrt{N} \right\rfloor.$
Par hypothèse de récurrence, $u_n\geq \left\lfloor \sqrt{N} \right\rfloor$. Or $N\geq 1$ donc $\sqrt{N} \geq 1$ et par croissance de la partie entière, $\left\lfloor \sqrt{N} \right\rfloor \geq 1$ donc $u_n \geq 1$. En prenant $m=u_n$, il vient $u_{n+1} \geq \left\lfloor \sqrt{N} \right\rfloor.$
2ème cas : $u_{n+1} = u_n$ et le résultat est acquis par hypothèse de récurrence.
Vous venez de démontrer, par récurrence, que $\forall n\in\N, u_n \geq \left\lfloor \sqrt{N} \right\rfloor.$
