L'analogie des dominos

Une image pour comprendre

Le raisonnement par récurrence se comprend très bien avec l'image d'une rangée infinie de dominos debout, numérotés 0, 1, 2, 3... On veut montrer que TOUS les dominos vont tomber.

Schéma de la chute en cascade

Rangee de dominos (chacun numerote, tous debout au depart) :

  domino 0   domino 1   domino 2   domino 3   domino 4   ...
     |          |          |          |          |
    [#]        [#]        [#]        [#]        [#]      (tous debout, n'est pas encore tombe)

Etape 1 (initialisation) : on pousse le domino 0

    [/]  ->    [#]        [#]        [#]        [#]       (domino 0 tombe)

Etape 2 (heredite) : chaque domino qui tombe pousse le suivant

    [/]  ->    [/]  ->    [#]        [#]        [#]        (domino 1 tombe a son tour)
    [/]  ->    [/]  ->    [/]  ->    [#]        [#]        (domino 2 tombe a son tour)
    [/]  ->    [/]  ->    [/]  ->    [/]  ->    [#]        (domino 3 tombe a son tour)
    [/]  ->    [/]  ->    [/]  ->    [/]  ->    [/]        (tous tombent, jusqu'a l'infini)

(chaque [/] = un domino tombe = la propriete P est vraie a ce rang)

Faire correspondre l'image et la démonstration

Pousser le domino 0 correspond exactement à l'initialisation : on déclenche la chute au premier rang. Le fait que "chaque domino qui tombe pousse le suivant" correspond exactement à l'hérédité : si P(k) est vraie (le domino k tombe), alors P(k+1) est vraie (le domino k+1 tombe aussi).

Pourquoi les deux conditions sont indispensables dans l'image

Si les dominos sont bien espacés et alignés (l'hérédité fonctionne, chaque domino qui tombe pousse bien le suivant) mais que personne ne pousse le premier domino (pas d'initialisation), alors AUCUN domino ne tombe : la chute en cascade ne démarre jamais. À l'inverse, si on pousse bien le premier domino mais que les dominos sont trop espacés (l'hérédité échoue à un rang), la chute s'arrête net à cet endroit précis.

Piège classique

L'image des dominos montre bien qu'il ne suffit pas qu'une seule des deux conditions soit remplie : il faut à la fois un déclencheur initial (initialisation) ET une transmission garantie d'un rang au suivant (hérédité), sinon la propriété ne se propage jamais jusqu'à l'infini.