Image des dominos : le premier doit tomber, et chaque chute doit provoquer la suivante.4
Piège n°1 : tester quelques valeurs ne prouve rien ; piège n°2 : sauter l'initialisation.
Au Bac, l'énoncé ne dit pas toujours « par récurrence » : sache le reconnaître.3
L'idée et le principe
Imagine une file infinie de dominos numérotés 0,1,2,3,… Deux conditions suffisent pour que tous tombent : le domino 0 est poussé, et chaque domino n qui tombe fait tomber le domino n+1.4 Notons P(n) l'affirmation « le domino n tombe ». Le domino 0 qui tombe, c'est l'initialisation ; la transmission de n à n+1, c'est l'hérédité.4
Les trois étapes à rédiger
Exemple rédigé
Où la retrouve-t-on ensuite
Questions flash
5 questions · correction immédiate · ton score reste sur ton appareil.
Les trois étapes sont l'initialisation, l'hérédité et la conclusion.3 Vérifier trois valeurs relève de l'induction incomplète, qui ne prouve rien pour tous les entiers.4
On part de P(n) vraie pour un n fixé et on en déduit P(n+1).3 Supposer P(n) vraie pour tout n revient à admettre ce qu'on veut démontrer.
C'est faux : quelques vérifications ne remplacent pas la preuve de l'hérédité, et cette méthode du « ainsi de suite » a été critiquée dès le XVIIe siècle.4 Il faut démontrer que la propriété se transmet de n à n+1.
On calcule de proche en proche : u1=2×1+1=3, u2=2×3+1=7, u3=2×7+1=15. La formule 24−1=15 de l'exemple confirme le résultat. L'erreur tentante est de s'arrêter à u2=7 ou de décaler l'indice : u3 est bien le quatrième terme de la liste, puisqu'on part de u0.
Le domino 0 qui tombe correspond à l'initialisation.4 La transmission de n à n+1 est l'hérédité, et « tous tombent » est la conclusion ; il n'existe pas de « dernier » domino puisque la file est infinie.
Les questions qu'on se pose
Comment savoir si je dois utiliser une récurrence alors que l'énoncé ne le dit pas ?
Un énoncé ne l'annonce pas toujours.3 Le signal le plus courant est une propriété à prouver « pour tout entier n » sur une suite définie par un+1=f(un) : formule explicite, encadrement, conjecture à justifier. Quand tu ne peux pas calculer un sans connaître le terme précédent, la récurrence est souvent la bonne piste.
L'initialisation doit-elle toujours se faire au rang 0 ?
Non. Elle se fait au premier rang où la propriété est énoncée : n0=0, n0=1, ou un autre entier. L'hérédité se démontre alors pour tout n⩾n0, et la conclusion vaut pour tout entier à partir de n0.
Que faire si je n'arrive pas à passer de $P(n)$ à $P(n+1)$ ?
Écris précisément ce que dit P(n+1) : c'est ton but. Puis exprime un+1 grâce à la relation de la suite, remplace un en utilisant l'hypothèse de récurrence, et transforme jusqu'à retrouver la forme visée.3 Pour un encadrement, applique les opérations de la relation à chaque membre de l'inégalité de départ.