Le raisonnement par récurrence

1. Le principe

Tout d’abord, en mathématiques, on désigne par proposition un énoncé portant sur des « objets » mathématiques.

Par exemple, (x = 3) est une proposition mathématique.

Pour démontrer une proposition P, il faut en fait justifier que la proposition P est « vraie ».

Les démonstrations sont nombreuses et ont des principes variés : cela dépend du contenu de la proposition P.

Parmi ces principes, il en est un appelé « raisonnement par récurrence » ; il concerne des propositions qui ont deux particularités :

• la proposition doit être universelle, à savoir être vraie pour tous les éléments qui la définissent,

ET

• la proposition doit dépendre d’un entier naturel.

Exemple

Soit (un) une suite et soit P la proposition (pour tout entier naturel n, un < 3) :

« Pour tout » génère l’universalité de P et P dépend d’un entier n ; P sera alors notée Pn pour signifier qu’elle dépend de l’entier n.

La question est donc de savoir comment démontrer Pn.

Parmi les possibilités de démonstrations, il y a le raisonnement par récurrence dont le principe est comparable à l’idée de vouloir « monter un escalier ayant un nombre infini de marches », comme le montre l’illustration ci-dessous.

Formellement cela donne :

Soit N un entier naturel fixé (par exemple 0).

Soit n un entier naturel quelconque.

On pose Pn une proposition universelle dépendant de n.

Principes admis du raisonnement par récurrence :

• initialisation :

on démontre que PN est vraie, c’est-à-dire que Pn est vraie au rang initial n = N.

• hérédité :

soit k un entier quelconque supérieur ou égal à N.

On démontre la proposition : , c’est-à-dire que Pk+1 est vraie sachant que Pk l’est.

Avec ces deux principes, on dispose alors de la véracité de Pn pour tout entier n supérieur ou égal à N.

Remarques

• L’initialisation correspond au fait de pouvoir être sur la marche initiale de l’escalier. L’hérédité correspond au fait de pouvoir monter une marche quelconque. Les deux principes réunis permettent de « gravir » l’escalier…

• Pour l’hérédité, il faut bien comprendre que l’on ne démontre pas que Pk+1 est vraie, ni que Pk est vraie, MAIS que Pk+1 est vraie sachant que Pk l’est ; on démontre une IMPLICATION.

2. Un exemple pour « mieux » comprendre

Énoncé d’après un exercice du Bac S d’Amérique du Sud, session

...