Démonstration par récurrence
La démonstration par récurrence est un outil très pratique !
La démarche se décompose essentiellement en 2 grandes phases (et l'on formalise ("rédige") en 4 phases) :
- Dans un premier temps, on démontre de manière générale que SI quelque chose est vrai à UNE étape, alors cette chose est TOUJOURS VRAIE à l'étape SUIVANTE, quelque soit l’étape ! On reste GÉNÉRAL ! On ne dit pas que si c’est vrai à l’étape 2, c’est toujours vrai à l’étape 3 ! Non ! On reste général ! On dit que si c’est vrai à une étape quelconque de rang n, alors c’est toujours vrai à l’étape suivante de rang n+1 !
- Puis, on montre que cette chose est VRAIE pour la PREMIERE étape de la série… donc comme on a déjà montré que n’importe quelle étape vraie était toujours vraie à l’étape suivante, TOUTES les étapes sont vraies !
Par exemple, montrons grâce à nos connaissances en mécanique que si un domino est debout sur sa petite tranche à moins d’un centimètre d’un autre domino, alors si ce premier domino tombe, il fera aussi tomber celui à coté de lui. Il peut y avoir seulement 2 dominos l’un à coté de l’autre, ou un millier, cela n’a pas d’importance ; nous avons montré que si l’un tombe, alors le suivant tombe aussi ! De manière générale, nous avons montré que si Dn (Domino placé à la nième position) tombe, alors Dn+1 tombe aussi ! n peut être égal à 1 000 000, comme il peut être égal à 1 (minimum !), cela n’a pas d’importance : si Dn tombe, alors Dn+1 tombe aussi et cette règle est vraie à partir de 2 dominos ! De plus, nous sommes restés GÉNÉRAL, donc ceci est valable QUELQUE SOIT la position du domino. Il peut être à la 100ième position ou à la 2ième ! Cela n’a pas d’importance ! Si le 100ième tombe, le 101ième tombe aussi, etc.
Puis montrons qu’effectivement, le PREMIER domino de la série tombe ! Alors si le 1er domino D1 tombe, le deuxième domino D2 tombera aussi puisqu’on a déjà démonté que si Dn tombe, Dn+1 tombe aussi. Ici n = 1 ! Et puisque D2 est tombé, D3 tombera aussi car nous avons montré que si Dn tombe, Dn+1 tombe aussi. Ici n = 2 ! Et ainsi de suite à l’infini !
Pour résumer, il faut montrer que si quelque chose est vraie à l’étape n, alors cette chose est toujours vraie à l’étape n+1. On appelle cette phase la démonstration du caractère héréditaire de l’hypothèse. L’hypothèse étant « si c’est vrai à l’étape n » et le caractère héréditaire est « alors c’est vrai à l’étape n+1 ». Puis, on montre que l’hypothèse est vraie à partir d’un premier élément de la série. On appelle cette étape l’initialisation !
Exemples de démonstration par récurrence
Exemple 1 : On considère la suite 
définie par :
Comment faire pour démontrer par récurrence que pour tout entier naturel n, on a 
?
Voici les étapes de la démonstration par récurrence :
- 1 ère étape : initialisation de la récurrence :
Il faut démontrer la propriété au premier rang :
le premier rang étant n = 0 puisque l'on dit dans l'énoncé pour tout entier naturel n, il faut démontrer ici que :
- 2 ème étape : hypothèse de récurrence :
on suppose qu'il existe un certain rang n pour lequel la propriété est vraie : ici on suppose que :
- 3ème étape : passage au rang suivant :
on "s'appuie" sur l'hypothèse de récurrence :
et ce que l'on sait :
pour démontrer que la propriété reste vrai au rang n + 1 c'est à dire qu'il faut montrer que :
- Dernière étape : on en conclut que la propriété est vrai pour tout entier naturel.n
Voyons l'exemple résolu avec les différentes étapes :
- u0 = 2 donc
donc la propriété est vraie au rang 0. - Supposons donc qu'il existe un n, tel que la propriété est vraie (et nous savons que c'est vrai car nous avons déjà démontré lors de l'étape précédente que cette propriété est vraie pour n = 0 )
- Démontrons que la propriété reste encore vraie au rang n+1 :
La propriété reste donc encore vraie au rang n +1.
- La propriété est donc vraie pour tout entier naturel n.
Cette page vous a plu ? N'hésitez pas à cliquer sur "J'aime" et de la sorte créer un lien sur votre compte facebook. Merci !