[ Page principale - Bibliographie - Annales - Liens ]
[ Olympiades : française - internationales - académiques ]
[ Clubs : Thèmes - Universités d'été - Coordonnées ]

Le raisonnement par récurrence

(Rédigé par Yann Ollivier.)
Le raisonnement par récurrence est la version mathématique du raisonnement « de proche en proche ». Il s'énonce comme suit :
Principe de récurrence - Soient $P_0, P_1,\ldots,P_n\ldots$ des propriétés mathématiques. On sait que est vraie. On sait aussi que, pour un n quelconque, si est vraie alors $P_{n+1}$ est vraie aussi. Alors, toutes les propriétés sont vraies.
Une application simple de ce principe est la définition par récurrence : si on définit un objet puis si, pour tout entier n, on donne une manière de définir l'objet $x_{n+1}$ à partir de l'objet , alors les objets sont bien définis pour tout n.
Une démonstration par récurrence contient donc toujours deux étapes :

L'initialisation : c'est la vérification de . Il ne faut jamais l'oublier, sinon on raisonne sur du vide !
La récurrence proprement dite : on suppose que la propriété est vraie (on l'appelle hypothèse de récurrence), et on essaie de montrer $P_{n+1}$ à partir d'elle.

Exercice - On se donne deux nombres r et a. On pose et, pour tout $n\geq 0$ , on définit $S_{n+1}=S_n+r$ . Proposez une formule simple pour et démontrez-la par récurrence.
Exercice - On définit et, pour tout n, on pose $T_n=T_{n-1}+n$ . Les nombres sont appelés nombres triangulaires (pourquoi ?). Montrer que, pour tout n, on a $T_n=\frac{n(n+1)}{2}$ .
On n'est pas obligé de commencer à . La récurrence peut très bien, par exemple, commencer à ou à , si les premiers termes sont des exceptions...
Exercice - On définit et pour tout $n\geq 2$ , on pose $S_n=S_{n-1}+\frac1{n(n+1)}$ . Donner une formule simple pour .
Les raisonnements par récurrence peuvent présenter des pièges, en particulier lorsque la récurrence est mal initialisée. Que pensez-vous de la démonstration suivante : on va montrer que, dans tout groupe de n personnes, s'il y a au moins une femme alors il n'y a que des femmes. Cette propriété est bien sûr vraie pour : si dans un groupe d'une seule personne il y a une femme, alors il n'y a que des femmes. Supposons donc que la propriété est vraie pour tout groupe de n personnes. On va montrer qu'alors elle est vraie pour tout groupe de personnes. Soit donc un groupe de personnes contenant une femme. Retirons l'une des personnes qui ne soit pas la femme, on a un groupe à n personnes. Ce groupe contient une femme. Par hypothèse de récurrence, ce groupe ne contient que des femmes. Rajoutons la personne qu'on avait enlevée : si c'est une femme on a terminé. Sinon, enlevons du groupe une des n autres femmes. On obtient alors un nouveau groupe de n personnes contenant au moins une femme, et par hypothèse de récurrence il ne contient que des femmes. On a donc prouvé qu'il n'y a que des femmes. Où est l'erreur ?
Exercice - Montrer que la somme des angles d'un polygone non croisé à n côtés ( $n\geq 3$ ) vaut $(n-2)\pi$ .
Dans une récurrence, pour montrer que $P_{n+1}$ est vraie, il arrive que ne suffise pas mais qu'on ait besoin, par exemple, de connaître $P_{n}$ et $P_{n-1}$ , ou encore de savoir que toutes les propositions $P_1,\ldots,P_n$ sont vraies pour en déduire $P_{n+1}$ . Cette situation est appelée récurrence forte.
Principe de récurrence forte - Soient $P_0, P_1,\ldots,P_n\ldots$ des propriétés mathématiques. On sait que est vraie. On sait aussi que, pour un n quelconque, si toutes les propositions $P_0, P_1,\ldots,P_n$ sont vraies, alors $P_{n+1}$ est vraie aussi. Alors, toutes les propriétés sont vraies.
Cela donne immédiatement une variante de la définition par récurrence : si on a défini un objet et que, connaissant les objets $x_0,x_1,\ldots,x_n$ , on sait définir l'objet suivant $x_{n+1}$ , alors tous les objets sont bien définis.
Exercice - Sur une île déserte vit, à l'année 0, un couple de lapins. Chaque année, les couples de lapins âgés d'au moins deux ans se reproduisent et engendrent un nouveau couple de lapins. Ainsi, l'année 0 il y a un couple ; l'année 1, un couple ; l'année 2, deux couples (le premier s'est reproduit) ; l'année 3, trois couples (encore à cause du premier) ; l'année 4, cinq couples (les deux premiers couples se sont reproduits), etc.

On note le nombre de couples l'année n. Donner une formule simple pour définir par récurrence à partir de $F_{n-1}$ et $F_{n-2}$ . La suite de nombres ainsi définie est très connue et s'appelle la suite de Fibonacci.
Montrer que, pour tout n, on a la relation $F_nF_{n+2}=F_{n+1}^2+(-1)^n$ .
On se trouve face à un escalier à n marches, et on a des jambes assez grandes pour monter les marches par une ou par deux, mais pas par trois. Montrer que le nombre de manières différentes qu'on a de monter l'escalier est égal à . (Par exemple, on peut monter un escalier à trois marches de trois manières : une par une, ou une marche puis deux, ou deux marches puis une.)

Parfois, il peut être utile de ne pas essayer de prouver directement la propriété demandée, mais d'en prouver une qui soit un peu plus forte...
Exercice - Montrer que, pour tout n, on a l'inégalité
$\frac1{1^2}+\frac1{2^2}+\frac1{3^2}+\cdots+\frac1{n^2}<2$
(Indication : montrer la propriété en remplaçant par dans le terme de droite.)

[ Page principale - Bibliographie - Annales - Liens ]
[ Olympiades : française - internationales - académiques ]
[ Clubs : Thèmes - Universités d'été - Coordonnées ]

Association Animath
Institut Henri Poincaré
11 rue Pierre et Marie Curie
75231 Paris cedex 05
animath (at) animath.fr

Pour toute question concernant Animath : animath (at) animath.fr
Pour toute remarque concernant ce site : webmaster (at) animath.fr
Dernière modification : 10 juillet 2004.
Page maintenue par Yann Ollivier.

Copyright
Tous les textes et le matériel figurant sur ces pages sont la propriété de leurs auteurs.
Toute utilisation non commerciale est autorisée, avec mention de la source.
Toute utilisation commerciale est interdite.