Raisonnement par récurrence

La récurrence est une méthode de démonstration très utilisée en mathématiques, le plus souvent quand on travaille avec les entiers naturels ou avec une autre suite.

Principe

Le principe de base est de démontrer l’affirmation pour un premier élément ; dans les entiers naturels non nuls, c’est le plus souvent n = 1. On le vérifie par simple substitution : c’est l’initialisation. Dans la deuxième étape, l’hérédité, on démontre l’implication « si l’affirmation est vraie pour n = a, alors elle est aussi vraie pour n = a + 1 ».

De ces deux étapes, on peut déduire que l’expression est vraie pour tous les n (d’un ensemble avec lequel on travaille). Pourquoi ? Au départ, on a démontré que l’expression est vraie pour n = 1. On sait aussi que si elle est vraie pour n = a, elle est vraie pour n = a + 1. Choisissons donc a = 1. On sait que l’expression est vraie pour a = 1, et on sait aussi qu’elle est vraie pour a + 1 = 2. À cet instant, on sait qu’elle est vraie pour a = 2. Mais comme elle est aussi vraie pour a + 1, elle doit être vraie pour 2 + 1 = 3. Et ainsi de suite.

Premier exemple

Le premier exemple sera trivial. Démontrons que si l’on ajoute deux à un nombre pair quelconque, on obtient de nouveau un nombre pair. Comme on travaille dans les entiers naturels non nuls, on écrit un nombre pair quelconque sous la forme 2n, où n est un entier naturel non nul. Si l’on remplace n par n’importe quel entier naturel non nul, on obtient un nombre pair, c’est évident au premier coup d’œil. La divisibilité s’écrit à l’aide d’une barre verticale, de cette façon :

$$2\mid 2n$$

Cette écriture signifie que 2 divise l’expression 2n sans reste. Maintenant que l’on sait écrire la divisibilité, on peut aussi écrire ce que l’on doit démontrer par récurrence.

$$2\mid 2n+2;n\in {\mathbb{N}}^{\ast }$$

C’est ce que l’on doit démontrer dans le premier exemple, c’est-à-dire que 2 divise l’expression 2n + 2 – cela correspond exactement à l’énoncé initial « si l’on ajoute deux à un nombre pair quelconque, on obtient de nouveau un nombre pair ».

Dans la première étape de la récurrence, l’initialisation, on le démontre pour le premier élément, pour un. On prend n = 1 dans l’expression :

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

2 divise 4 sans reste, donc l’affirmation est vraie pour le premier élément. Vient ensuite l’hérédité, où l’on doit démontrer que si l’affirmation est vraie pour le a-ième élément, alors elle est vraie aussi pour le (a + 1)-ième élément. Au départ, on suppose que l’affirmation est vraie pour n = a ; c’est notre hypothèse :

$$2\mid 2a+2$$

On suppose que cette expression est vraie – on s’en servira pour construire la démonstration. Nous voulons maintenant démontrer que

$$2\mid 2(a+1)+2.$$

Qu’avons-nous fait ? À la place de a, nous avons écrit (a + 1). Les parenthèses sont importantes : l’expression 2a + 1 + 2 serait fausse. On n’ajoute pas un à l’expression entière, on remplace vraiment a par une expression plus grande d’un, c’est-à-dire (a + 1). On transforme l’expression en développant la parenthèse.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Faisons maintenant une petite parenthèse sur la divisibilité. Si l’on a deux nombres, disons p et q, qui sont divisibles par un même nombre, disons r, alors leur somme est elle aussi divisible par r. On a donc :

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

On peut y prendre par exemple p = 8, q = 20 et r = 4. On voit que 4 divise 8 comme 20. Et il divise aussi leur somme 8 + 20 = 28.

Comment s’en sert-on dans notre exemple ? On sépare le membre de droite en deux nombres p et q de cette façon :

$$p=2a+2;q=2$$

Le nombre q, c’est-à-dire 2, est trivialement divisible par 2. Et l’expression p est elle aussi divisible par 2, puisque c’est ce que nous dit l’hypothèse. L’expression p correspond exactement à notre hypothèse, que l’on suppose vraie. Et si p est divisible par 2 et que q est divisible par 2, alors leur somme est aussi divisible par 2.

Revenons encore une fois à l’hypothèse. Au début, nous avons dit que nous supposions vraie la relation

$$2\mid 2a+2.$$

C’est pourquoi, quand nous sommes tombés sur l’expression 2a + 2 pendant la construction de la démonstration, nous avons pu dire qu’elle est divisible par 2. Précisément parce que c’est notre hypothèse. C’est d’ordinaire l’étape la plus difficile de la récurrence – comprendre quand et pourquoi on peut utiliser l’hypothèse de récurrence.

Ainsi s’achève la récurrence : la démonstration est faite, la propriété est vraie.

Si tu préfères, tu peux décomposer autrement et ne pas utiliser l’hypothèse. Prends p = 2n et q = 2 + 2. Le nombre q = 4 est trivialement divisible par 2, et p = 2n aussi, car après la division par 2 il reste le nombre n, qui est un entier naturel, donc un entier. Nous avons de nouveau obtenu deux expressions divisibles par 2, donc leur somme est elle aussi divisible par 2.

Dans les deux cas, nous avons toutefois démontré que

1. l’expression est vraie pour n = 1,
2. si l’expression est vraie pour n, alors elle est vraie aussi pour n + 1.

On peut en déduire :

• On sait que l’expression est vraie pour n = 1.
• Si elle est vraie pour n, elle doit être vraie pour n + 1, c’est-à-dire pour 1 + 1, donc l’expression est vraie pour n = 2.
• Si elle est vraie pour n, elle doit être vraie pour n + 1, c’est-à-dire pour 2 + 1, donc l’expression est vraie pour n = 3.
• Si elle est vraie pour n, elle doit être vraie pour n + 1, c’est-à-dire pour 3 + 1, donc l’expression est vraie pour n = 4.
• Si elle est vraie pour n, elle doit être vraie pour n + 1, c’est-à-dire pour 4 + 1, donc l’expression est vraie pour n = 5.
• …

Deuxième exemple

Démontrons maintenant par récurrence une affirmation simple :

$$2^n\ge 2n;n\in {\mathbb{N}}^{\ast }.$$

D’abord l’initialisation : on vérifie si l’affirmation est vraie pour n = 1, le premier élément des entiers naturels non nuls dans lesquels on choisit n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

C’est trivialement vrai. Passons à l’hérédité, où l’on doit vérifier que si l’affirmation est vraie pour n = a, elle est vraie aussi pour n = a + 1. Notre hypothèse est donc que

$$2^a\ge 2a$$

et nous voulons démontrer que :

$$2^{a+1}\ge 2(a+1)$$

On commence par réécrire le membre de gauche à l’aide des règles de calcul sur les puissances, et l’on développe simplement le membre de droite.

$$2\cdot 2^a\ge 2a+2$$

Dans le membre de gauche, on utilise une addition à la place de la multiplication, et l’on laisse le membre de droite inchangé.

$$2^a+2^a\ge 2a+2$$

On utilise maintenant l’hypothèse. L’hypothèse est une proposition que l’on suppose vraie. Dans l’inéquation, il y a de chaque côté deux termes qui s’additionnent. Mais on sait aussi que

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

La première ligne est notre hypothèse et la seconde proposition est triviale (la plus petite valeur de 2^a est obtenue pour a = 1, et elle vaut justement deux). On sait donc que, dans le membre de gauche, chacun des deux termes est supérieur ou égal à chacun des deux termes du membre de droite. On a ainsi démontré par récurrence que si l’expression est vraie pour a, alors elle est vraie aussi pour (a + 1), et comme elle est vraie pour un, l’expression est vraie.

Troisième exemple

Essayons de démontrer l’affirmation suivante :

$$3\mid n\Rightarrow 3\mid n^2;n\in {\mathbb{N}}^{\ast }$$

En mots : si n est divisible par trois, alors n² est lui aussi divisible par trois. Si n n’est pas divisible par trois, l’expression est trivialement vraie (par définition de l’implication), donc nous nous occuperons des cas où n est divisible par trois. Cela nous donne la suite d’entiers naturels u_i = 3 ; 6 ; 9 ; 12 ; 15… À partir de maintenant, nous travaillons dans cette suite u_i.

On commence la démonstration par récurrence par l’initialisation, c’est-à-dire en vérifiant si l’affirmation est vraie pour le premier élément. Rappelons que l’on travaille dans la suite u_i, donc on prend le premier élément de cette suite, c’est-à-dire l’élément u₁, qui vaut trois. Pour trois, l’expression est vraie :

$$3\mid 3\Rightarrow 3\mid 3^2$$

Passons maintenant à l’hérédité. On voit que la suite u_i pourrait s’écrire 3n, où n est un entier naturel non nul. Ainsi, le deuxième élément est plus grand de trois que le précédent, etc. Supposons maintenant que l’expression est vraie pour n ; nous devons montrer qu’elle est vraie aussi pour (n + 3), qui est la règle générant l’élément suivant de la suite dans laquelle on travaille. On écrit d’abord l’hypothèse :

$$3\mid n\Rightarrow 3\mid n^2$$

puis ce que l’on veut démontrer

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

On développe la parenthèse de l’autre côté à l’aide de l’identité remarquable :

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Et nous voilà presque au but. À gauche, on a une expression certainement divisible par trois, car n est divisible par trois d’après l’hypothèse (on ne travaille que dans les nombres de la suite u_i) et trois est lui aussi divisible par trois. À droite, on a d’abord n², qui est divisible par trois d’après l’hypothèse. En effet, on sait que n est divisible par trois et l’hypothèse dit que si n est divisible par trois, alors n² l’est aussi :

$$3\mid n\Rightarrow 3\mid n^2$$

Vient ensuite l’expression 6n, qui est trivialement divisible par trois. Tu peux l’imaginer comme une simplification de fraction :

$$\frac{6n}{3}=2n$$

La variable n est un entier naturel, donc le produit 2n est lui aussi un entier naturel : après la division par trois, on a obtenu un entier naturel, et l’expression 6n est donc bien divisible par trois. Quant au neuf à la fin, il est de nouveau divisible par trois. L’initialisation et l’hérédité sont vérifiées, l’expression est donc vraie.

Nombre de parenthèses dans une expression

Le dernier exemple sera un peu atypique. Essayons de démontrer que le nombre de parenthèses dans une expression simple est toujours pair, pour que tu voies que la récurrence peut s’utiliser dans un tout autre contexte que celui des seuls entiers naturels. Au départ, il faut définir ce qu’est une expression simple. Une expression simple est :

• un entier naturel non nul,
• si p est une expression simple, alors (p²) est aussi une expression simple,
• si p et q sont des expressions simples, alors (p + q) est aussi une expression simple.

Voici donc des expressions simples : 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). À l’inverse, ce ne sont pas des expressions simples :

• 1 + 2 → il manque les parenthèses extérieures,
• (1 + 2 → il manque la parenthèse de droite,
• 13² → il manque les parenthèses extérieures,
• (1 + 2 + 3) → il manque des parenthèses, la bonne écriture serait (1 + (2 + 3))

Une expression simple peut se former par exemple ainsi. Au départ, on choisit l’expression simple (a + b). On remplace maintenant a par l’expression simple a = (c + d), ce qui donne ((c + d) + b), puis on remplace b par trois : ((c + d) + 3). On remplace c par dix : ((10 + d) + 3) et enfin d par (5²) : ((10 + (5²)) + 3). Il est important de respecter les parenthèses, sinon cela ne fonctionnera pas.

Démontrons maintenant qu’une expression simple contient un nombre pair de parenthèses (zéro fait partie des nombres pairs).

Dans l’initialisation, on choisit un premier élément. Ici, ce sera l’expression simple la plus triviale, c’est-à-dire un entier naturel non nul quelconque. On pose donc

$$j=n;n\in {\mathbb{N}}^{\ast }.$$

Pour l’expression j, le nombre de parenthèses est nul, donc le premier élément convient. Dans l’hérédité, on suppose que l’on a deux expressions simples p et q et que toutes les deux ont un nombre pair de parenthèses. Il faut alors démontrer que les expressions simples (p + q) et (p²) ont elles aussi un nombre pair de parenthèses.

D’abord l’addition. Définissons encore une fonction z(q) qui renvoie le nombre de parenthèses de l’expression q. L’expression (p + q) a alors z(p) + z(q) + 2 parenthèses. Elle a donc deux parenthèses de plus que la somme des parenthèses des expressions p et q. D’après l’hypothèse, z(p) et z(q) sont pairs, donc si l’on additionne trois nombres pairs, on obtient de nouveau un nombre pair. Dans ce cas, la proposition est vraie.

Passons à la puissance. De nouveau, on suppose que l’expression simple p contient un nombre pair de parenthèses. L’expression (p²) contient alors z(p) + 2 parenthèses, donc de nouveau deux de plus que l’expression p. Dans ce cas aussi, on additionne des nombres pairs, le résultat est donc pair.

L’initialisation et l’hérédité sont vérifiées, donc la proposition est vraie.