Vérification par récurrence

Il est fréquent que l'on ne parvienne pas à exprimer $u_n$ en fonction de $u_0$ et de $n$, certaines récurrences sont très difficile à résoudre. Une autre façon de classifier une suite $u_n$ dans un $\mathcal{O}$ est de conjecturer ce $\mathcal{O}$, puis de le démontrer par récurrence. Par exemple, démontrons par récurrence que $u_n \in \mathcal{O}(n)$. Si c'est le cas, supposons que $u_n$ est majorée par une suite linéaire, c'est à dire de la forme $an + b$. Choisissons $b$ tel que $b \geq u_0 = 1$ et $a > 1$.

• L'hypothèse sur $b$ implique que $a(0)+ b \geq u_0$.
• Supposons que si $an + b \geq u_n$, alors montrons que $a(n+1) + b \geq u_{n+1}$. On a $u_{n+1} = u_{n} + 1 \leq an + b + 1 \leq an + b + a = a(n+1) + b$.

On montre aisément que $a$ et $b$ choisis conformément aux conditions précédant la démonstration par récurrence détermine une suite $an + b$ qui majore $u_n$. On remarque que $an + b$ croît de façon linéaire, en effet $$\frac{an + b}{n} \longrightarrow a$$, donc on a $an + b \in \mathcal{O}(n)$. Comme $u_n$ est majorée par une suite linéaire, $u_n \in \mathcal{O}(n)$.

Prouvons pour le sport que si $u_n \leq v_n$ et $v_n \in \mathcal{O}(w_n)$, alors $u_n \in \mathcal{O}(w_n)$. Comme $v_n \in \mathcal{O}(w_n)$, alors $\exists k, \exists N, \forall n > N, v_n \leq k.w_n$, comme $u_n \leq v_n$, alors pour les mêmes valeurs $k$ et $N$, $u_n \leq v_n \leq k.w_n$ et de ce fait $u_n \leq k.w_n$.

Deux ensembles de méthodes ressortent dans les exemples :

• La résolution exacte, elle nécessite le connaissance de bon nombre de méthodes mathématiques, bien qu'élégante, elle devient vite très compliquée.
• La conjecture d'une majoration suivie d'une preuve par récurrence de cette majoration. La preuve est en règle générale plus simple à mettre en oeuvre, la partie la plus difficile est de conjecturer une majoration valide et la moins grossière possible.