0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel W. Farlow Feb 25 '15 at 3:58
  • $\begingroup$ @crash I've been using and learning MathJax. I didn't need to in this question. $\endgroup$ – committedandroider Feb 25 '15 at 4:12
  • $\begingroup$ How can you say that? What makes you think not using it in this question is appropriate? $\endgroup$ – Daniel W. Farlow Feb 25 '15 at 4:13
  • $\begingroup$ Check my last question. There weren't any exponents, fractions, etc in this one. $\endgroup$ – committedandroider Feb 25 '15 at 4:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel W. Farlow Feb 25 '15 at 4:41
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 25 '15 at 4:26
  • $\begingroup$ 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? $\endgroup$ – committedandroider Feb 25 '15 at 4:29
  • 1
    $\begingroup$ @committedandroider: Yes, that’s exactly right. $\endgroup$ – Brian M. Scott Feb 25 '15 at 4:30
  • $\begingroup$ Would the overall summary be "We have shown that if the first n dominoes fall, the (n+1) domino will fall as well because the domino that causes it to fall, (n-2) domino, lies in the first n dominoes. Therefore since the n+1 domino will fall, the rest of them will fall as well"? $\endgroup$ – committedandroider Feb 25 '15 at 4:36
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 25 '15 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.