158. Démonstration de la convergence d’une suite qui donne la racine carrée entière d’un nombre entier (partie 1/2)

Soit $N$ un nombre naturel supérieur ou égal à $1.$ Pour tout réel $x\comma$ notez $\left\lfloor x \right\rfloor$ la partie entière de $x\comma$ 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) \lt u_n\\ u_n \quad\text{ si } f(u_n) \geq u_n.\\ \end{cases}

Ce contenu 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\comma$ c’est-à-dire l’unique entier $m$ tel que $m^2\leq N \lt (m+1)^2.$

Le but de ce contenu 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} \lt p+1$ est vérifié.

Par suite, $n+p \leq n+ \frac{N}{n} \lt n+p+1$ et après division par $2$ il vient $\frac{n+p}{2} \leq \frac{n+ \frac{N}{n} }{2}\lt \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}\lt \ell +\frac{1}{2} \lt \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{align*} \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{align*}

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}\lt \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} \lt \ell +1.$

Ainsi, comme précé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} \lt \ell +1$ donc $\ell = \left\lfloor \frac{n+ p }{2} \right\rfloor\comma$ 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{align*} \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{align*}

La positivité du carré et de l’entier $n$ montre 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.

D’après le premier lemme, vous avez :

\begin{align*} f(n) = \left\lfloor \frac{n+\frac{N}{n}}{2} \right\rfloor. \end{align*}

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\comma$ notez $P(n)$ la propriété : « $u_n \geq \left\lfloor \sqrt{N} \right\rfloor$ ».

Initialisation. Pour $n = 0\comma$ $u_0 = N.$ Comme $N$ est un entier naturel non nul, $N\geq 1.$ En multipliant par $N\comma$ 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.

Premier cas : $u_{n+1} = f(u_n).$ Il a été établi ci-dessus que, pour tout entier $m\geq 1\comma$ $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\comma$ il vient $u_{n+1} \geq \left\lfloor \sqrt{N} \right\rfloor.$

Second 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.$