Le squelette d'une récurrence : méthode (Terminale spé)
Le squelette d'une récurrence
Pour démontrer qu'une propriété est vraie pour tout $n\geq n_0$ :
- Énoncer la propriété : « Pour tout entier $n\geq n_0$, on note $P(n)$ : … ». Préciser $n_0$.
- Initialisation : vérifier $P(n_0)$. Calculer séparément chaque membre, puis comparer.
- Hérédité : écrire « Soit $n\geq n_0$ un entier fixé. On suppose $P(n)$ vraie. Montrons que $P(n+1)$ est vraie. » Écrire explicitement ce que dit $P(n+1)$ : c'est le but à atteindre. Partir de la quantité qui apparaît dans $P(n+1)$, la relier à celle de $P(n)$, utiliser l'hypothèse de récurrence en le signalant.
- Conclusion : « La propriété est vraie au rang $n_0$ et elle est héréditaire, donc d'après le principe de récurrence, $P(n)$ est vraie pour tout entier $n\geq n_0$. »
Expression explicite d'une suite
Soit $(u_n)$ définie par $u_0=1$ et $u_{n+1}=2u_n+1$ pour tout $n\in\mathbb{N}$. Les premiers termes sont $1,\ 3,\ 7,\ 15$ : on conjecture $u_n=2^{n+1}-1$.
Pour tout $n\in\mathbb{N}$, on note $P(n)$ : « $u_n=2^{n+1}-1$ ».
Initialisation. $u_0=1$ et $2^{0+1}-1=2-1=1$. Donc $P(0)$ est vraie.
Hérédité. Soit $n\in\mathbb{N}$ fixé. On suppose $u_n=2^{n+1}-1$. Montrons que $u_{n+1}=2^{n+2}-1$. $$u_{n+1}=2u_n+1=2\left(2^{n+1}-1\right)+1=2^{n+2}-2+1=2^{n+2}-1.$$ La deuxième égalité utilise l'hypothèse de récurrence. Donc $P(n+1)$ est vraie.
Conclusion. $P(0)$ est vraie et la propriété est héréditaire, donc pour tout $n\in\mathbb{N}$, $u_n=2^{n+1}-1$.
Une divisibilité
Montrons que, pour tout $n\in\mathbb{N}$, $4^n-1$ est divisible par $3$.
On note $P(n)$ : « il existe un entier $k$ tel que $4^n-1=3k$ ».
Initialisation. $4^0-1=0=3\times 0$. Donc $P(0)$ est vraie.
Hérédité. Soit $n\in\mathbb{N}$ fixé. On suppose qu'il existe un entier $k$ tel que $4^n-1=3k$, c'est-à-dire $4^n=3k+1$. Alors $$4^{n+1}-1=4\times 4^n-1=4(3k+1)-1=12k+3=3(4k+1).$$ Comme $4k+1$ est un entier, $4^{n+1}-1$ est divisible par $3$ : $P(n+1)$ est vraie.
Conclusion. Par récurrence, $4^n-1$ est divisible par $3$ pour tout $n\in\mathbb{N}$.
Quand penser à la récurrence
On pense à une récurrence lorsque la propriété porte sur un entier $n$ et que le passage de $n$ à $n+1$ est simple : une suite définie par $u_{n+1}=f(u_n)$, une puissance $a^{n+1}=a\times a^n$, une somme qui s'obtient en ajoutant un terme.
La récurrence ne sert pas à tout. Si $u_n=3n+2$, on a directement $u_{n+1}-u_n=3$ : aucune récurrence n'est nécessaire.
S’entraîner
- Expression explicite d'une suite définie par récurrence
- Somme des puissances de 2
- Une divisibilité par 6
- Une suite définie par un quotient
- Une première inégalité avec des puissances
Dans le cours
Raisonnement par récurrence : Le squelette d'une récurrence