Raisonnement par récurrence

1Le principe de récurrence

Définition. Une propriété $P(n)$ est un énoncé qui dépend d’un entier naturel $n$ et qui, pour chaque valeur de $n$, est vrai ou faux.

Théorème — principe de récurrence. Soit $n_0$ un entier naturel et $P(n)$ une propriété définie pour tout entier $n\geq n_0$. Si

• initialisation : $P(n_0)$ est vraie ;
• hérédité : pour tout entier $n\geq n_0$, «  $P(n)$ vraie  » entraîne «  $P(n+1)$ vraie  » ;

alors $P(n)$ est vraie pour tout entier $n\geq n_0$.

Remarque. On l’illustre par une file de dominos : le premier tombe (initialisation) et chaque domino qui tombe fait tomber le suivant (hérédité), donc tous tombent.

2Rédiger une récurrence

Méthode — les quatre temps de la rédaction. (1) Énoncer la propriété : «  Pour tout entier $n\geq n_0$, on note $P(n)$ la propriété : …  » (2) Initialisation : calculer séparément les deux membres pour $n=n_0$ et conclure que $P(n_0)$ est vraie. (3) Hérédité : «  Soit $n\geq n_0$ un entier quelconque. Supposons $P(n)$ vraie  » (hypothèse de récurrence) ; écrire ce que l’on veut démontrer, c’est-à-dire $P(n+1)$ ; partir de $u_{n+1}$ (ou du membre de gauche de $P(n+1)$), utiliser la relation de récurrence puis l’hypothèse. (4) Conclusion : «  $P(n_0)$ est vraie et $P$ est héréditaire : d’après le principe de récurrence, $P(n)$ est vraie pour tout entier $n\geq n_0$.  »

3Les quatre situations classiques

Propriété — expression explicite. Pour une suite définie par $u_{n_0}$ et $u_{n+1}=f(u_n)$, on conjecture $u_n$ (calculs ou programme Python), puis on démontre par récurrence la propriété $P(n)$ : «  $u_n=\dots$  ».

Propriété — somme ou produit. Le terme de rang $n+1$ s’obtient en ajoutant (ou en multipliant par) un terme au terme précédent : $S_{n+1}=S_n+(\text{terme suivant})$. On remplace alors $S_n$ par l’hypothèse de récurrence, puis on factorise.

Propriété — inégalité, encadrement, monotonie. Pour $u_{n+1}=f(u_n)$ avec $f$ croissante sur un intervalle contenant les termes, $m\leq u_n\leq M$ donne $f(m)\leq u_{n+1}\leq f(M)$ : l’encadrement se transmet lorsque $f(m)\geq m$ et $f(M)\leq M$ ; de même $u_n\leq u_{n+1}$ donne $u_{n+1}\leq u_{n+2}$ (monotonie).

Propriété — divisibilité. Un entier $a$ est divisible par $d$ lorsqu’il existe un entier $k$ tel que $a=dk$. Dans l’hérédité, on écrit l’hypothèse sous la forme $a_n=dk$ avec $k\in\Z$, on exprime $a_{n+1}$ en fonction de $a_n$, puis on factorise par $d$.

Remarque. Pour conjecturer l’expression d’un terme, on calcule les premiers termes à la main ou avec une boucle Python (u = u0 puis for k in range(n): u = …) ; la récurrence vient ensuite démontrer la conjecture.

4L’inégalité de Bernoulli

Théorème. Pour tout réel $a\geq 0$ et tout entier naturel $n$ : $(1+a)^{n}\geq 1+na$.

Idée de la démonstration (exigible). $P(0)$ : $(1+a)^{0}=1\geq 1$. Hérédité : comme $1+a>0$,

car $na^{2}\geq 0$. La multiplication par $1+a$ conserve le sens de l’inégalité parce que $1+a>0$.

Remarque. Cette inégalité sert à démontrer que $\lim\limits_{n\to+\infty}q^{n}=+\infty$ lorsque $q>1$ : en écrivant $q=1+a$ avec $a>0$, on a $q^{n}\geq 1+na$, qui tend vers $+\infty$.

5Savoir-faire du chapitre

6Exemples types