# How to show the inductive step of the strong induction?

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?

• You have now asked 74 questions and been a member for 6 months. It is time for you to learn how to typeset your questions correctly. – Daniel W. Farlow Feb 25 '15 at 3:58
• @crash I've been using and learning MathJax. I didn't need to in this question. – committedandroider Feb 25 '15 at 4:12
• How can you say that? What makes you think not using it in this question is appropriate? – Daniel W. Farlow Feb 25 '15 at 4:13
• Check my last question. There weren't any exponents, fractions, etc in this one. – committedandroider Feb 25 '15 at 4:14
• OK. I just edited your post to show you what your questions from now on out should look like (please fill in the details in the section I grayed out). You generally show your work done on questions, and that is great, but you must (let me repeat, $\color{red}{\text{must}}$) typeset questions correctly if you are going to keep on using MSE frequently. Sometimes I don't even read posts when they are typeset horrendously. It's easy to avoid that problem by simply typesetting your questing correctly. Please do this from now on out. – Daniel W. Farlow Feb 25 '15 at 4:41

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.
• @committedandroider: It’s a fact that’s essential to the argument, since the induction hypothesis applies only to $k\le n$, but it’s so obvious that you probably don’t need to mention it explicitly even when you’re just learning the technique. Unless, of course, you’ve an instructor who is very fussy about the details — even fussier than I was. – Brian M. Scott Feb 25 '15 at 4:26
• Oh so basically the logic here is that since you have a domino that falls 3 before domino $n+1$, domino $n+1$ will fall? And you know that the domino that falls 3 before will fall because it is apart of your initial assumption? – committedandroider Feb 25 '15 at 4:29
• @committedandroider: I don’t think that I’d put it quite like that. If I wanted to summarize the argument in outline, I’d say something like this: We’re given that the first three dominoes fall, and we’ve shown that if $n\ge 3$ and the first $n$ dominoes fall, then so does the $(n+1$-st domino; it follows by the (strong) principle of mathematical induction that all of the dominoes fall. – Brian M. Scott Feb 25 '15 at 4:40