Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

(P(0) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x))
(P(0) ∧ (∀x [P(x) ⇒ P(x − 1)])) ⇒ (∀x P(x))
(P(1000) ∧ (∀x [P(x) ⇒ P(x − 1)])) ⇒ (∀x P(x))
(P(1000) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x))

Correct answer: (P(0) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x))

Solution

This statement is an application of mathematical induction, where proving that a property holds for the base case (P(0)) and that if it holds for an arbitrary case (P(x)), it also holds for the next case (P(x + 1)) ensures that the property is true for all natural numbers.

Related GATE Technical questions

Which one of the following options is correct for the given data in the table? Iteration (i): 0, 1, 2, 3 Input (I): 20, -4, 10, 15 Output (X): 20, 16, 26, 41 Output (Y): 20, -80, -800, -12000
Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?
Let L, M, and N be non-singular matrices of order 3 satisfying the equations L² = L⁻¹, M = L⁸ and N = L². Which ONE of the following is the value of the determinant of (M - N)?
Consider the following statements: (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S. Which ONE of the following is CORRECT?
A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?
Consider the following statements about the use of backpatching in a compiler for intermediate code generation: (I) Backpatching can be used to generate code for Boolean expression in one pass. (II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?

⚔️ Practice GATE Technical free + battle 1v1 →