1.8 Induction

Alice wants to prove by induction that predicate \(P\) holds for certain nonnegative integers. She has proven that for all nonnegative integers \(n = 0,1,2,3\ldots \)

1. Suppose Alice also proves that \(P(5)\) holds. Which of the following propositions can she infer? The universe of discourse for \(n\) is the nonnegative integers.
   Exercise 1

    \(P(n)\) holds for all \(n \geq 5 \) 

    \(P(3n)\) holds for all \(n \geq 5 \) 

    \(P(n)\) holds for \(n = 8, 11, 14, \ldots \) 

    \(P(n)\) does not hold for \(n \leq 4 \) 

    \(\forall n.\; P(3n + 5) \) 

    \(\forall n > 2.\; P(3n - 1) \) 

    \(P(0) \text{ IMPLIES } \forall n.\; P(3n + 2) \) 

    \(P(0)\text{ IMPLIES }\forall n. P(3n) \) 

   \(P\) will be true on 5 and all numbers that are greater by a multiple of 3. That is, 5, 8, 11, 14, etc. This is exactly what answer (5) says. Answers (3) and (6) talk of the same sequence except number 5, so they are still propositions that Alice can infer, although not the strongest possible. Answer (8) is also a valid conclusion: if Alice knows \(P\) is true on 0, she knows it will also be true on 3, 6, 9, etc.; so, it will be true on all multiples of 3 (note that the truth of \(P\) on 5 is not relevant here).
2. Which of the following could Alice prove in order to conclude that \(P(n)\) holds for all \(n \geq 5\)?
   Exercise 2

     \(P(0)\) 

    \(P(5)\) 

     \(P(5) \text{ and } P(6)\) 

    \(P(0), P(1), \text{ and } P(2)\) 

    \(P(5), P(6), \text{ and } P(7)\) 

    \(P(2), P(4), \text{ and } P(5)\) 

    \(P(2), P(4), \text{ and } P(6)\) 

    \(P(3), P(5), \text{ and } P(7)\) 

   Once Alice proves \(P(5), P(6), \text{ and } P(7)\), she can conclude that \(P(n)\) holds for all \(n \ge 5\). \(P(5), P(6), \text{ and } P(7)\) can also follow from proving \(P\) of any three nonnegative intergers, up to 7, that leave remainders on division by 3 as 0, 1, and 2.
   CheckShow Answer