I feel like I struggle a lot for these kinds of problems. I was wondering if someone could verify my answers and reasoning and possibly give some tips on how to solve these kinds of problems. Thank you.
The problem: Alice wants to prove by induction that a predicate P holds for certain nonnegative integers. She has proven that for all nonnegative integers n = 0, 1, 2, …
P(n) IMPLIES P(n+3)
Suppose Alice also proves that P(5) holds. Which of the following propositions can she infer?
So because Alice proved P(5) that means P(8), P(11), P(14) … holds.
- P(n) holds for all n ≥ 5
Can't infer this because we do not know, for example, if P(6) holds for the predicate.
- P(3n) holds for all n ≥ 5
Can't infer this because we not know, for example, if P(18) holds for the predicate.
- P(n) holds for n = 8, 11, 14, …
Yes, because Alice proved P(5) holds, so P(8), P(11), P(14) … holds.
P(n) does not hold for n < 5
We can't infer this statement because we don't know if P(1), P(2), P(3), and P(4) holds for the predicate or not.
- ∀n. P(3n + 5)
We can infer this because the smallest natural number is 0. And when we plug it in we get P(3(0) + 5) = P(5). And then we add three because of the statement Alice proved. So for n = 0 -> P(8). For n = 1,2,3 -> P(11), P(14), P(17).
- P(0) IMPLIES ∀n. P(3n + 2)
- P(0) IMPLIES ∀n: P(3n)
For these last two, we cannot infer either of these because for n = 0, the first statement gives P(2) and the second gives P(0). We do not know if the predicate holds for these values.
Your very last statement is incorrect. $P(0) \Rightarrow P(3) \Rightarrow P(6) \cdots$.
The only reason it's not true that $P(0)$ (and your initial assumption that Alice has proved $P(5)$) implies $P(3n+2) \forall n \in \Bbb N$ is that you still don't know $P(2)$.