GATE 2022 CS Q.51: solution and answer

GATE 2022 · CSQ.51 · 2 marks · MSQ

Consider the following recurrence:

f (1) f (2 n) f (2 n + 1) = 1; = 2 f (n) - 1, for n \geq 1; = 2 f (n) + 1, for n \geq 1.

Then, which of the following statements is/are TRUE?

(A)
$f (2^{n} - 1) = 2^{n} - 1$
(B)
$f (2^{n}) = 1$
(C)
$f (5 \cdot 2^{n}) = 2^{n + 1} + 1$
(D)
$f (2^{n} + 1) = 2^{n} + 1$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The TRUE statements are A, B and C; only D is false. Final answer: A, B, C.

Official answer: A, B, CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

Compute small values directly from the recurrence: $f (1) = 1$ , and using $f (2 n) = 2 f (n) - 1$ , $f (2 n + 1) = 2 f (n) + 1$ repeatedly gives $f (2) = 1, f (3) = 3, f (4) = 1, f (5) = 3, f (6) = 5, f (7) = 7, f (8) = 1, \dots, f (15) = 15, f (16) = 1$ .
Within the block $n \in [2^{k}, 2^{k + 1} - 1]$ the values traced above are exactly the consecutive odd numbers $1, 3, 5, \dots, 2^{k} - 1$ , so conjecture the closed form $f (n) = 2 n - 2^{k + 1} + 1$ for $n$ in that block.
Verify by induction: if $n = 2 m$ lies in block $k$ , then $m$ lies in block $k - 1$ , so $f (n) = 2 f (m) - 1 = 2 (2 m - 2^{k} + 1) - 1 = 2 n - 2^{k + 1} + 1$ , matching the conjectured formula; the odd case $n = 2 m + 1$ checks the same way using $f (n) = 2 f (m) + 1$ . So the closed form $f (n) = 2 n - 2^{k + 1} + 1$ for $n \in [2^{k}, 2^{k + 1} - 1]$ holds for all $n \geq 1$ .
Option A: $2^{n} - 1$ is the top of block $k = n - 1$ (range $[2^{n - 1}, 2^{n} - 1]$ ). Then $f (2^{n} - 1) = 2 (2^{n} - 1) - 2^{n} + 1 = 2^{n} - 1$ , which matches the claim — TRUE.
Option B: $2^{n}$ is the bottom of block $k = n$ (range $[2^{n}, 2^{n + 1} - 1]$ ). Then $f (2^{n}) = 2 \cdot 2^{n} - 2^{n + 1} + 1 = 1$ , which matches the claim — TRUE.
Option C: $5 \cdot 2^{n} = 2^{n + 2} + 2^{n}$ lies strictly between $2^{n + 2}$ and $2^{n + 3} - 1$ , so it is in block $k = n + 2$ . Then $f (5 \cdot 2^{n}) = 2 (5 \cdot 2^{n}) - 2^{n + 3} + 1 = 10 \cdot 2^{n} - 8 \cdot 2^{n} + 1 = 2^{n + 1} + 1$ , which matches the claim — TRUE.
Option D: $2^{n} + 1$ lies in block $k = n$ (range $[2^{n}, 2^{n + 1} - 1]$ , for $n \geq 1$ ). Then $f (2^{n} + 1) = 2 (2^{n} + 1) - 2^{n + 1} + 1 = 3$ , a constant, not equal to $2^{n} + 1$ in general. Testing $n = 2$ : $f (2^{2} + 1) = f (5) = 3 \neq = 2^{2} + 1 = 5$ — FALSE.
So the TRUE statements are A, B and C.

KEY IDEA

The recurrence generates, block by block ( $n$ from $2^{k}$ to $2^{k + 1} - 1$ ), the consecutive odd numbers $1, 3, 5, \dots, 2^{k} - 1$ , giving the closed form $f (n) = 2 n - 2^{k + 1} + 1$ whenever $2^{k} \leq n \leq 2^{k + 1} - 1$ . Once this closed form is established (and proved by induction using the two recurrence cases), every option reduces to identifying which block the given $n$ falls in and substituting.

WATCH OUT FOR

Two common traps: (1) assuming the closed form applies uniformly without first identifying which power-of-two block the argument falls into — e.g. for option D, plugging $n = 2^{n} + 1$ into the wrong block's formula, or not testing a concrete value, can hide that $f (2^{n} + 1) = 3$ is constant rather than $2^{n} + 1$ ; (2) for option C, misjudging the block of $5 \cdot 2^{n}$ (it is easy to mistake it for block $k = n + 1$ instead of the correct $k = n + 2$ , since $5 \cdot 2^{n}$ sits just above $4 \cdot 2^{n} = 2^{n + 2}$ ).

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2022 CS Q.51: solution and answer

Answer and solution

More Complexity questions