Suites recurrentes et croissances comparees

Suites recurrentes u_(n+1) = f(u_n)

Beaucoup de suites sont definies par une relation de recurrence et une fonction f continue. Si (u_n) converge vers l et si f est continue en l, alors en passant a la limite dans u_(n+1) = f(u_n), on obtient l = f(l) : l est un point fixe de f.

Exemple

Soit u_0 = 1, u_(n+1) = sqrt(2 + u_n). On montre par recurrence que (u_n) est croissante et majoree par 2, donc elle converge vers une limite l >= 0 verifiant l = sqrt(2 + l), soit l^2 = 2 + l, soit l^2 - l - 2 = 0, soit (l - 2)(l + 1) = 0. Comme l >= 0, on conclut l = 2.

Piege classique

Trouver un point fixe candidat ne suffit pas a prouver la convergence : il faut d'abord etablir que la suite converge (monotonie + bornee, ou autre argument), puis seulement identifier l par l'equation du point fixe. Sans preuve de convergence prealable, l'equation l = f(l) peut avoir des solutions qui ne sont pas la limite reelle, voire aucune limite n'exister.

Croissances comparees

Pour comparer la vitesse a laquelle des suites tendent vers l'infini, on retient la hierarchie (a > 0, k entier) :

Suite	Croissance
ln(n)^k	plus lente
n^a	intermediaire
a^n (a > 1)	rapide
n!	tres rapide
n^n	ultra rapide

Concretement : ln(n)/n -> 0, n^a/a^n -> 0 (a > 1), a^n/n! -> 0, n!/n^n -> 0.

Exemple d'application

lim(n->+infini) n^2/2^n = 0, car l'exponentielle « ecrase » toute puissance de n. Reconnaitre cette forme evite de nombreux calculs fastidieux.