3.7 Comportements polynômiaux, logarithmiques, exponentiels


Suites et fonctions élémentaires

La plupart des suites définies à l'aide de fonctions élémentaires sont des suites qui tendent vers l'infini:

Or toutes ces suites ne tendent pas vers l'infini de la même manière: certaines tendent vers l'infini plus vite que d'autres.



Hiérarchie de comportements à l'infini
Soient \((a_n)\) et \((b_n)\) deux suites qui tendent vers l'infini: \[ a_n\to\infty\,,\qquad b_n\to\infty\,. \] On dit que \(b_n\) tend vers l'infini plus vite que \(a_n\) si \[ \frac{a_n}{b_n}\to 0\,. \]

Exemple: Les suites \(a_n=n^2\) et \(b_n=n^3\) tendent toutes deux vers l'infini, mais \(b_n\) tend vers l'infini plus vite que \(a_n\), car \[\frac{a_n}{b_n}=\frac{n^2}{n^3}=\frac{1}{n}\to 0\,.\]

Il est donc naturel d'établir une certaine hiérarchie parmis les comportements typiques des suites qui tendent vers l'infini. Les comportements les plus classiques sont ceux de types polynomial (puissances), logarithmique et exponentiel.

Théorème: (Comportements à l'infini)

  1. Un exponentielle tend vers l'infini plus vite que n'importe quelle puissance: pour toute base \(r\gt 1\) et toute puissance \(\alpha>0\), \[ \frac{n^\alpha}{r^n}\to 0\,. \]
  2. Une puissance tend vers l'infini plus vite que n'importe quelle puissance de logarithme: pour toute base \(r>1\), et toutes puissances \(\alpha,\beta>0\), \[ \frac{\bigl(\log_r (n)\bigr)^\beta}{n^\alpha}\to 0\,. \]

1. Remarquons d'abord que si on sait traiter les cas où \(\alpha\) est entier, alors on sait aussi traiter le cas d'un \(\alpha\) quelconque. (En effet, pour tout \(n\geqslant 1\), \(\frac{n^\alpha}{r^n}\leqslant \frac{n^{\lfloor\alpha\rfloor+1}}{r^n}\), donc si \(\frac{n^{\alpha'}}{r^n}\to 0\), avec \(\alpha'=\lfloor\alpha\rfloor+1\geqslant \alpha\), alors \(\frac{n^\alpha}{r^n}\to 0\) aussi.)

Pour simplifier, considérons le cas \(\alpha=r=2\). On aimerait donc montrer que \[ \frac{n^2}{2^n}\to 0\,. \] L'idée est d'utiliser la formule du binôme pour montrer que le dénominateur est plus grand qu'une puissance supérieure à \(n^2\). En effet, la formule du binôme avec \(x=y=1\) donne \[ 2^n=(1+1)^n=\sum_{k=0}^n\binom{n}{k}1^{n-k}1^k=\sum_{k=0}^n\binom{n}{k}\,.\] Or comme tout les termes de cette dernière somme sont positifs, la somme est plus grande que n'importe lequel de ces termes. Dans notre cas, il suffit de ne garder que le terme correspondant à \(k=3\) \[\sum_{k=0}^n\binom{n}{k}\geqslant \binom{n}{3}=\frac{n!}{(n-3)!3!} =\frac{n(n-1)(n-2)}{6}\,.\] Ceci implique que \[ 0\leqslant \frac{n^2}{2^n}\leqslant \frac{n^2}{\frac{n(n-1)(n-2)}{6}} =\frac{6n^2}{n(n-1)(n-2)}\,. \] On voit que dans ce dernier quotient, le numérateur se comporte en \(n^2\), alors que le dénominateur se comporte en \(n^3\), ce qui implique que sa limite est nulle. Plus précisément, \[ \lim_{n\to \infty}\frac{6n^2}{n(n-1)(n-2)} =\lim_{n\to \infty}\underbrace{\frac{1}{n}}_{\to 0} \underbrace{\frac{6}{(1-\frac1n)(1-\frac2n)}}_{\to 6}=0\,. \] Par le théorème des deux gendarmes, on conclut donc que \(\frac{n^2}{2^n}\to 0\).

Dans le cas général, pour une exponentielle de base \(r>1\) et une puissance entière \(\alpha\) quelconque, on peut adapter la preuve ci-dessus. En effet, en écrivant \(r=1+\delta\), où \(\delta>0\), et en utilisant à nouveau la formule du binôme, on peut minorer \[ r^n=(1+\delta)^n\geqslant \binom{n}{\alpha+1}\delta^{\alpha+1}\,. \] Le reste de la preuve s'adapte facilement, et mène à \(\frac{n^\alpha}{r^n}\to 0\).

Une preuve semblable de cette première affirmation, même si ça ne se voit pas tout de suite, peut se trouver ici.

2. On peut démontrer la deuxième affirmation à l'aide de la première.

\(\bigstar\) Le théorème implique par exemple que \[\frac{(\log n)^{1000}}{n^{0.0001}}\to 0\,.\] Pourtant, la petitesse du quotient est difficile à observer (avec une calculatrice par exemple), dans le sens où il faut que \(n\) soit vraiment très grand pour que ce quotient commence à se rapprocher de zéro...





---- (Dernière modification: 2022-10-31 (07:27:51)) ----