Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 341].
Problem: Use strong induction to show that all dominoes fall in an infinite arrangement of dominoes if you know that the first three dominoes fall, that when a domino falls, the domino three farther down in the arrangement also falls
My work: I know that the inductive step in strong induction is to show that "if $p(i)$ is true for all $i$ less than or equal to $k$ then $p(k+1)$ is true".
I know that strong induction has the the same basis step so I showed that the first domino will fall because of the stated "you know that the first three dominoes fall".
How would I describe the inductive step here?
What I tried was saying that I assume $p(k)$ is true for every $n \leq k$ or that every domino before $k$ and $k$ itself will fall. Then is $p(k+1)$ saying the next domino will fall? From the infinite staircase idea, the rest of the dominoes will fall? Now I've shown that all dominoes will fall? Am I missing something?
Best Answer
You’re missing most of the essential details, I’m afraid.
Let $P(k)$ be the assertion that domino $k$ falls. You’re given $P(1),P(2)$, and $P(3)$ to get the induction started. Now assume that for some $n\ge 3$ you know that $P(k)$ is true for each $k\le n$; that’s your induction hypothesis, and your task in the induction step is to prove $P(n+1)$.
You know that for each $k$, if $P(k)$ is true, then $P(k+3)$ is true as well. Let $$\ell=(n+1)-3=n-2\;;$$ since $n\ge 3$, $n-2\ge 1$, and therefore the truth of $P(\ell)$ is part of your induction hypothesis. Thus, $P(\ell+3)=P(n+1)$ is true, and the induction step is complete.