The domino analogy

An image to understand

Proof by induction is very well understood with the image of an infinite row of standing dominoes, numbered 0, 1, 2, 3... We want to show that ALL the dominoes will fall.

Diagram of the cascade of falls

Row of dominoes (each numbered, all standing at the start):

  domino 0   domino 1   domino 2   domino 3   domino 4   ...
     |          |          |          |          |
    [#]        [#]        [#]        [#]        [#]      (all standing, has not fallen yet)

Step 1 (base case): we push domino 0

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

Step 2 (inductive step): each domino that falls pushes the next one

    [/]  ->    [/]  ->    [#]        [#]        [#]        (domino 1 falls in turn)
    [/]  ->    [/]  ->    [/]  ->    [#]        [#]        (domino 2 falls in turn)
    [/]  ->    [/]  ->    [/]  ->    [/]  ->    [#]        (domino 3 falls in turn)
    [/]  ->    [/]  ->    [/]  ->    [/]  ->    [/]        (all fall, all the way to infinity)

(each [/] = a fallen domino = the property P is true at this rank)

Matching the image and the proof

Pushing domino 0 corresponds exactly to the base case: we trigger the fall at the first rank. The fact that "each domino that falls pushes the next one" corresponds exactly to the inductive step: if P(k) is true (domino k falls), then P(k+1) is true (domino k+1 falls too).

Why both conditions are essential in the image

If the dominoes are well spaced and aligned (the inductive step works, each falling domino does push the next) but nobody pushes the first domino (no base case), then NO domino falls: the cascade never starts. Conversely, if the first domino is pushed but the dominoes are too far apart (the inductive step fails at some rank), the fall stops dead at that exact spot.

Common pitfall

The domino image clearly shows that it is not enough for just one of the two conditions to be met: you need both an initial trigger (base case) AND a guaranteed transmission from one rank to the next (inductive step), otherwise the property never propagates to infinity.