Aller au contenu Aller au menu Politique d'accessibilité

Free Sciences Site sur les mathématiques, la physique, et l'informatique.

Principe de récurrence

Nous allons voir maintenant que la structure de l'ensemble permet une nouvelle technique de démonstration: la démonstration par récurrence.

Idée générale du principe de récurrence

Supposons que nous devions démontrer une formule qui dépend uniquement d'un nombre naturel n, c'est à dire une propriété vraie pour tout n. Si cette propriété est P, on a que P(n) est vrai quel que soit n. Le problème est de savoir comment démontrer que P(n) est toujours vrai.

En effet, on peut écrire une démonstration pour démontrer que P(0) est vrai. Puis faire la même chose pour P(1), puis pour P(2), ... mais on n'aura jamais fini la démonstration. Face à ce problème, on peut tenter de prouver P(n) sans faire d'hypothèse sur n c'est à dire que l'on démontre directement P(n) mais ce n'est pas toujours possible ni toujours facile.

Il est cependant parfois possible de démontrer que si pour un certain n P(n) est vrai, alors P(s(n)) est vrai aussi. L'idée est donc de montrer d'abord que P(0) est vrai. On suppose alors que P(n) est vrai pour un certain n ce que l'on appelle l'hypothèse de récurrence. Ensuite on démontre que P(s(n)) est vrai avec cette hypothèse.

Cette démarche est suffisante pour prouver P(n) pour tout n. En effet, on sait que P(0) est vrai (car on le démontre au préalable). Puisqu'on montre ensuite que si P(n) est vrai, alors P(s(n)) est vrai aussi, cela veut dire que P(1) est vrai car P(0) est vrai. De la même manière, cela prouve que P(2) est vrai puisque P(1) est vrai, et donc P(3) et ainsi de suite. On a donc démontré P(n) pour tout n.

Écriture formelle du principe

Dans une démonstration par récurrence on démontre P(0) et on démontre n,P(n)P(s(n)). Remarquez qu'on devrait écrire formellement: n,(nP(n)P(s(n))) mais on ne le fait pas pour rendre l'écriture de la formule plus facile à lire. Désormais on va accepter ce léger abus de notation.

Le principe de récurrence nous dit donc que si ces deux choses sont prouvées, alors on a montré n,P(n). On a donc:

(P(0)n,P(n)P(s(n)))(n,P(n))

Démonstration

Il reste à démontrer cette formule. On suppose donc que P(0) et n,P(n)P(s(n)) sont vrais et on démontre n,P(n). On va le faire par l'absurde. Supposons qu'il existe n tel que P(n) soit faux. On considère le plus petit n tel que P(n) soit faux, et on le note m. m0 car on sait que P(0) est vrai. m est donc le successeur d'un entier p. p est donc plus petit que m et donc P(p) est vrai. On a donc par hypothèse que P(s(p))=P(m) est vrai et on a une contradiction.