GATE 2025 CS2 Q.15: solution and answer

Official answer: ASource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. Mathematical induction over the natural numbers says: if $P(0)$ holds and $\forall x[P(x)\Rightarrow P(x+1)]$ holds, then $\forall xP(x)$ holds.

2. Option (A) is exactly this principle, with base case $P(0)$ and an upward step $x\to x+1$. It is true for every predicate $P$ over the naturals.

3. Option (B): the step goes downward. Take $P(x)$ true only for $x=0$. Then $P(0)$ holds. For $x\ge 1$, $P(x)$ is false, so $P(x)\Rightarrow P(x-1)$ is true. For $x=0$, $P(0)\Rightarrow P(-1)$ has a true premise, but $-1$ is not a natural number, so the step is only a claim over the naturals. Reading the step as ranging over $x\ge 1$ (the only values for which $x-1$ is a natural number), the hypothesis holds while $\forall xP(x)$ is false. So (B) is not true for every predicate.

4. Option (C): take $P(x)\equiv (x\le 1000)$. Then $P(1000)$ holds. For $x\ge 1$, $P(x)\Rightarrow P(x-1)$ holds, since $x\le 1000$ implies $x-1\le 1000$. The hypothesis therefore holds, but $P(1001)$ is false, so $\forall xP(x)$ fails.

5. Option (D): take $P(x)\equiv (x\ge 1000)$. Then $P(1000)$ holds, and $P(x)\Rightarrow P(x+1)$ holds for every $x$. But $P(0)$ is false, so $\forall xP(x)$ fails.

6. Only (A) holds for every predicate $P$.