Raisonnement par récurrence Terminale : cours

Le raisonnement par récurrence démontre une infinité d'énoncés reliés par le passage d'un entier au suivant. Il ne remplace pas un calcul direct : il organise une transmission logique, comme une rangée de dominos dont on vérifie le premier puis le mécanisme de chute.

La difficulté principale est rédactionnelle. Une initialisation correcte, une hypothèse clairement fixée et une hérédité qui vise exactement la propriété au rang suivant sont indispensables. Quelques valeurs numériques peuvent suggérer le résultat, jamais le prouver pour tous les rangs.

Table des Matières

Quand une récurrence est-elle adaptée ?

Famille de propositions

On note $P(n)$ une proposition dépendant d'un entier $n\geq n_0$ . Une récurrence convient lorsqu'on peut établir $P(n_0)$ , puis déduire $P(k+1)$ de $P(k)$ pour un entier k quelconque.

Les situations classiques sont une formule explicite pour une suite définie par récurrence, une inégalité dépendant de n, une somme ou une propriété de divisibilité. Si la propriété ne relie pas naturellement deux rangs successifs, une preuve directe, un calcul algébrique ou un raisonnement par l'absurde peut être plus simple.

Les trois étapes logiques

Principe de récurrence

Si $P(n_0)$ est vraie et si, pour tout entier $k\geq n_0$ , la vérité de $P(k)$ entraîne celle de $P(k+1)$ , alors $P(n)$ est vraie pour tout entier $n\geq n_0$ .

Initialisation : vérifier la propriété au premier rang $n_0$ .
Hérédité : fixer $k\geq n_0$ , supposer $P(k)$ vraie et démontrer $P(k+1)$ .
Conclusion : invoquer le principe et préciser l'ensemble des entiers concernés.

L'hypothèse de récurrence est locale à l'étape d'hérédité. Elle n'est ni un résultat déjà démontré pour tous les entiers ni une permission de supposer directement la conclusion au rang k+1.

Choisir le premier rang et écrire la propriété à transmettre

L’initialisation dépend de l’énoncé, pas d’une habitude

Pour une somme commençant à 1, le premier rang est souvent 1 ; pour une suite définie par son terme initial $u_0$ , on commence souvent à 0. Mais une inégalité peut n'être vraie qu'à partir d'un autre entier. Il faut d'abord vérifier ce que l'on veut démontrer, et non écrire automatiquement « pour n égal à zéro ».

Considérons $2^n\geq n^2$ . Elle est fausse pour $n=3$ , puisque $8\lt 9$ , mais vraie pour $n=4$ . Pour établir le résultat pour tout $n\geq4$ , on initialise donc à 4. Pour un entier $k\geq4$ , l'hypothèse $2^k\geq k^2$ donne $2^{k+1}\geq2k^2$ . Or $2k^2-(k+1)^2=(k-1)^2-2\geq7\gt 0$ . Ainsi $2^{k+1}\geq(k+1)^2$ . Par récurrence, l'inégalité vaut pour tout entier $n\geq4$ .

Ne pas confondre hypothèse et objectif

Si $P(n)$ signifie $u_n\leq u_{n+1}$ , l'hypothèse au rang k est $u_k\leq u_{k+1}$ , et l'objectif au rang suivant est $u_{k+1}\leq u_{k+2}$ . Tous les indices doivent avancer d'un rang. Écrire les deux lignes avant les calculs permet de savoir exactement ce que l'on a le droit d'utiliser et ce qui reste à établir.

La lettre k n'a rien de magique : n convient aussi si l'on écrit « fixons un entier n » et si l'on garde le sens de l'implication. L'erreur logique est de supposer la propriété vraie pour tous les entiers, pas de choisir telle ou telle lettre.

Exemple : somme des premiers entiers

On veut prouver, pour tout $n\geq1$ , que $1+2+\cdots+n=\frac{n(n+1)}2$ . Au rang 1, les deux membres valent 1. Supposons l'égalité vraie au rang k. Alors :

1+2+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1)=\frac{(k+1)(k+2)}2

La dernière expression est précisément la formule attendue lorsque n est remplacé par k+1. L'hérédité est établie, donc l'égalité vaut pour tout entier n supérieur ou égal à 1. Chaque transformation a un rôle : l'hypothèse remplace seulement la somme jusqu'à k.

Prouver une inégalité ou une divisibilité

Faire apparaître l’hypothèse utile

Pour une inégalité, on part souvent du membre au rang k+1 et on isole une expression contrôlée par l'hypothèse au rang k. Il faut surveiller le signe avant de multiplier ou de comparer. Pour une divisibilité, on écrit l'expression au rang k sous la forme $dq$ , puis on montre que le terme ajouté au rang suivant est encore multiple de d.

Une hérédité peut être vraie alors que l'initialisation est fausse. Dans ce cas, la chaîne ne démarre pas. Inversement, vérifier de nombreux premiers rangs ne compense jamais l'absence de mécanisme général.

Transmission d'une propriété de rang en rang — L'initialisation ouvre la chaîne ; chaque implication transmet ensuite la propriété au rang suivant.

Récurrence et suites définies de proche en proche

Lorsque $u_{n+1}=f(u_n)$ , la récurrence sert à établir un encadrement, un signe ou une monotonie. Pour prouver $u_n\leq M$ , on vérifie le premier terme, puis on utilise $u_k\leq M$ dans une transformation compatible avec f. Si f est croissante sur l'intervalle concerné, on peut comparer $f(u_k)$ et $f(M)$ , mais cette croissance doit être justifiée.

Objectif	Point de vigilance
Formule explicite	obtenir exactement l'expression au rang k+1
Inégalité	préserver le sens des comparaisons
Divisibilité	factoriser par le diviseur
Encadrement d'une suite	vérifier que la fonction conserve l'intervalle

Prouver une divisibilité sans utiliser de congruences

Montrons que $n^3-n$ est divisible par 6 pour tout entier $n\geq0$ . La preuve ne demande pas le cours d'arithmétique de l'option expertes : être divisible par 6 signifie être égal à six fois un entier.

Faire apparaître l’expression au rang précédent

Au rang 0, $0^3-0=0=6\cdot0$ . Fixons $k\geq0$ et supposons $k^3-k=6q$ pour un entier q. En développant, $(k+1)^3-(k+1)=(k^3-k)+3k(k+1)$ . L'hypothèse contrôle le premier terme. Pour le second, k et k+1 sont consécutifs, donc l'un est pair : $k(k+1)=2r$ pour un entier r. Ainsi l'expression vaut $6q+6r=6(q+r)$ , multiple de 6. L'hérédité est établie ; par récurrence, la divisibilité vaut pour tout entier naturel n.

Il ne suffit pas d'affirmer que le terme ajouté est un multiple de 6 : l'argument de parité justifie précisément ce point. Une preuve directe serait également possible avec $n^3-n=(n-1)n(n+1)$ , mais il faudrait alors expliquer pourquoi ce produit comporte un facteur pair et un multiple de 3.

Établir un encadrement puis la monotonie d’une suite

Soit $u_0=1$ et $u_{n+1}=(u_n+6)/3$ . Pour étudier cette suite, on peut prouver séparément deux propriétés : $1\leq u_n\lt 3$ , puis $u_n\lt u_{n+1}$ . Un encadrement n'est pas une preuve de monotonie.

Un intervalle conservé par la relation de récurrence

Au rang 0, $1\leq1\lt 3$ . Fixons $k\geq0$ et supposons $1\leq u_k\lt 3$ . L'addition de 6 puis la division par 3, positif, donnent $7/3\leq(u_k+6)/3\lt 3$ . Comme $7/3\gt 1$ , on retrouve $1\leq u_{k+1}\lt 3$ . Le principe de récurrence prouve donc cet encadrement pour tout entier naturel n.

Transmettre une comparaison entre deux termes

On a $u_1=7/3\gt u_0$ : la propriété $u_n\lt u_{n+1}$ est initialisée au rang 0. Supposons $u_k\lt u_{k+1}$ pour un entier $k\geq0$ . La fonction $f(x)=(x+6)/3$ est strictement croissante ; ainsi $f(u_k)\lt f(u_{k+1})$ , soit $u_{k+1}\lt u_{k+2}$ . La suite est strictement croissante par récurrence.

Une autre preuve, directe une fois l'encadrement établi, consiste à écrire $u_{n+1}-u_n=2(3-u_n)/3\gt 0$ . Choisir cette voie ne diminue pas la rigueur : il n'est pas nécessaire de faire une deuxième récurrence lorsque le signe de la différence suffit.

Relire une preuve avant de conclure

Erreur fréquente : écrire « supposons la propriété vraie pour tout n » suppose déjà ce que l'on cherche à démontrer. Il faut fixer un entier k arbitraire.

Contrôle utile : surligner dans l'hérédité l'unique endroit où l'hypothèse $P(k)$ est utilisée. Si elle n'apparaît jamais, la preuve est probablement directe ou incomplète.

Les définitions de proche en proche sont revues dans les suites numériques de Première. Les encadrements établis par récurrence seront utilisés pour les limites de suites.

La récurrence intervient dans plusieurs capacités de le programme officiel de Terminale, spécialité mathématiques.