Votre navigateur n'accepte pas le Javascript. La navigation sur ce site risque de ne pas fonctionner correctement.

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

17/07/2020 - 0064

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{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}< \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{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$ 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{align*}
f(n) \geq \frac{n+\frac{N}{n}}{2} \\
\geq \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$, 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.$

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.