Question

Induction

Say which of the following statement is correct. The implicit domain of all quantifiers is
N = {0, 1, 2, ...}. If you mark a statement as incorrect then state briefly what the problem is.
1. If p(0) and ∀n>0 (p(n) → p(n+1)) then ∀n p(n)
2. If p(1) and ∀n>0 (p(n−1) → p(n)) then ∀n p(n)
3. If p(0) and ∀n>0 (p(n−1) → p(n)) then ∀n>3 p(n)
4. If p(0) and ∀n>0 (p(n−1) → p(n+1)) then ∀n p(2n)
5. If p(0) and ∀n≥0 (¬p(n) ∨ p(n+1)) then ∀n p(n)

don't understand these questions.

Answer 1

1) If p(0) and ∀n>0 (p(n) → p(n+1)) then ∀n p(n)

This is the correct version of Induction. Base case is true p(0) and then the induction step. This implies p(n) is true for all n

2) If p(1) and ∀n>0 (p(n−1) → p(n)) then ∀n p(n)

This is wrong because in the induction step, for n=1 we get p(0)->p(1), but our base case is p(1)

3) If p(0) and ∀n>0 (p(n−1) → p(n)) then ∀n>3 p(n)

This is wrong because the base case is p(0) whereas the truth statement is for all n>3

4) If p(0) and ∀n>0 (p(n−1) → p(n+1)) then ∀n p(2n)

This is wrong because p(2n) doesn't follow in induction's statement. Also p(n-1)->p(n+1) but it should be p(n)->p(n+1) or p(n-1)->p(n) (the previous implies the next, there should be no gap)

5) If p(0) and ∀n≥0 (¬p(n) ∨ p(n+1)) then ∀n p(n)

¬p(n) ∨ p(n+1) is equivalent p(n)->p(n+1) so the statement reads

If p(0) and ∀n≥0 (p(n) -> p(n+1)) then ∀n p(n)

This is the statement of mathematical induction so this statement is a correct version of the statement of mathematical induction

Please don't forget to rate positively if you found this response helpful. Feel free to comment on the answer if some part is not clear or you would like to be elaborated upon. Thanks and have a good day!