Récurrence

Commençons par une vidéo

Voici une des nombreuses vidéos de chutes de dominos.
Un seul mouvement permet de faire tomber un dominos et tous tombent. 

Comment savait-on que ces tous ces dominos allaient tomber ?

Numérotons les dominos dans l'ordre dans lequel ils tombent : 1,2,3,4,5,......

 

Si le domino 1 tombe, il fait tomber le domino 2.

Si le domino 2 tombe, il fait tomber le domino 3.

etc...

 

On peut continuer comme çà mais s'il y a 5 000 dominos, il me faudra 4 997 lignes de plus.

1. Amorce : Le premier domino est tombé
2. Hérédité : Les dominos sont placés de telle manière que la chute d'un domino entraîne la chute du domino suivant 

Mathématiquement, il s'agit du théorème de récurrence : 

Principe de récurrence.   Étant données des propriétés P(1), P(2), P(3), ........... Si la propriété P(1) est vraie pour tout k, la propriété P(k) implique la propriété suivante P(k+1), alors la propriété P(n) sera vraie pour tous les n.

 

 
 
Remarque : Le principe de récurrence est un théorème. Il nécessite une démonstration.
 
Je vais utiliser ce théorème pour montrer que tous les dominos devaient tomber.
 

Je note
P(1) : le domino 1 tombe
P(2) : le domino 2 tombe
....
P(n) : le domino n tombe
 
Chacune de ses propriété peut être vraie ou fausse.
 
En poussant le premier domino, on le fait tomber. Donc P(1) (est vraie). 
 
Remarque : je n'écrirai plus est vraie pour dire qu'une propriété est vraie mais simplement le nom de la propriété.
 
En disposant dans l'ordre (un devant et un derrière), et assez proches l'un de l'autre, on est certain que chaque domino numéroté k tombé entraînera celui qui le suit, le domino k+1. Donc pour tout k, P(k) implique P(k+1).

D'après le principe de récurrence, on en déduit que pour tout n : P(n). Autrement dit, tous les dominos tombent.