Le raisonnement par récurrence

Chapitre 1. Le raisonnement par récurrence

I. Découverte du raisonnement par récurrence

On considère la suite de nombres (un)n∈N

définie par :

u0 = 1 et pour tout entier naturel n, un+1 = 2un + 1.

Ainsi, u0 = 1 puis u1 = 2 × u0 + 1 = 2 × 1 + 1 = 3 puis u2 = 2 × u1 + 1 = 2 × 3 + 1 = 7 puis u3 = 2 × u2 + 1 = 2 × 7 + 1 = 15.

Décrivons les premières valeurs de un dans un tableau et comparons ces valeurs aux premières puissances de 2.

n 0 1 2 3 4 5 6 7 8 9 10

un 1 3 7 15 31 63 127 255 511 1023 2047

2

n+1

2 4 8 16 32 64 128 256 512 1024 2048

Il semblerait que chaque terme de la suite soit 1 au-dessous d’une certaine puissance de 2. On conjecture donc ou

encore on pense fortement que pour tout entier naturel n, un = 2

n+1 − 1.

Conjecture : pour tout entier naturel n, un = 2

n+1 − 1.

Nous avons la sensation que ce résultat est vrai mais nous ne l’avons jamais démontré et il s’agit maintenant de le

montrer. Le tableau donné plus haut montre la formule quand n est un entier compris entre 0 et 10 au sens large. Mais

ce tableau ne montre pas la formule quand n = 11. On peut bien sûr vérifier « à la main » si oui ou non le nombre u11

est égal à 2

12 − 1 :

u11 = 2 × u10 + 1 = 2 × 2047 + 1 = 4095 = 4096 − 1 = 2

12 − 1,

et la formule est encore vraie pour n = 11. Mais elle n’est pas démontrée pour n = 12 . . .

Lançons nous maintenant dans ce que l’on appellera au paragraphe suivant, un raisonnement par récurrence. Nous

ne savons pas si la formule est vraie quand n = 12 car nous n’avons pas pris la peine de le vérifier. Par contre,

si la formule est vraie au rang 12, alors elle sera vraie au rang 13.

En effet, si u12 = 2

13 − 1, alors u13 = 2 × u12 + 1 = 2 × (2

13 − 1) + 1 = 2

14 − 2 + 1 = 2

14 − 1. Ainsi, nous ne savons pas que la

formule est vraie au rang 12 mais nous savons que si elle est vraie au rang 12, alors elle est encore vraie au rang 13.

De même, si la formule est vraie au rang 17 ou encore si u17 = 2

18 − 1 alors

u18 = 2 × u17 + 1 = 2 × (2

18 − 1) + 1 = 2

19 − 2 + 1 = 2

19 − 1,

et la formule est alors vraie au rang 18. Plus généralement, si on suppose que la formule est vraie pour un certain rang

n donné, alors la formule est automatiquement vraie au rang suivant. En effet, si on suppose que un = 2

n+1 − 1, alors

un+1 = 2 × un + 1 = 2 × (2

n+1 − 1) + 1 = 2

(n+1)+1 − 2 + 1 = 2

(n+1)+1 − 1.

Ainsi, si on savait que la formule était vraie pour n = 0 alors elle serait automatiquement vraie pour n = 1 et si on

savait que la formule était vraie pour n = 1 alors elle serait automatiquement vraie pour n = 2 et si on savait que la

formule était vraie pour n = 2 alors elle serait automatiquement vraie pour n = 3 . . .

Finalement, il ne reste plus qu’à se convaincre que la formule est vraie quand n = 0 car alors la formule devient vraie

pour n = 1 puis n = 2 puis, de proche en proche, pour tout entier naturel n.

Comme 2

0+1 − 1 = 2 − 1 = 1 et que u0 = 1, on a effectivement u0 = 2

0+1 − 1. Mais alors, d’après la remarque précédente,

on a montré que pour tout entier naturel n, un = 2

n+1 − 1.

Le type de raisonnement que nous avons tenu est un raisonnement par récurrence et le type de démonstration

que l’on a effectué est une démonstration par récurrence. Dans le paragraphe suivant, on va formaliser ce type de

démonstration.

© Jean-Louis Rouget, 2015. Tous droits réservés. 1 http ://www.maths-france.fr

II. Le raisonnement par récurrence

On énonce maintenant le principe du raisonnement par récurrence. On admet le théorème suivant :

Théorème. On veut prouver qu’une certaine propriété P(n), dépendant d’un entier naturel n, est vraie

pour tout entier naturel n.

Si

• P(0) est vraie,

• pour tout entier naturel n, P(n) vraie implique P(n + 1) vraie,

alors

pour tout entier naturel n, P(n) est vraie.

Il se peut que la propriété P(n) ne soit pas vraie pour quelques valeurs de n parmi les premières et ne commence à

être vraie qu’à partir d’un certain rang n0 auquel cas on utilise le théorème suivant :

Théorème. On veut prouver qu’une certaine propriété P(n), dépendant d’un entier naturel n, est vraie

pour tout entier naturel n supérieur ou égal à un certain entier naturel n0.

Si

•

...