Consider the following recurrence: aligned f(1) &= 1; \\ f(2n) &= 2f(n) - 1, for n ≥ 1; \\ f(2n+1) &= 2f(n) + 1, for n ≥ 1. aligned Then, which of the following statements is/are TRUE?

GATE CSE 2022 Q51: Values of a recurrence on 2n and 2n + 1

Consider the following recurrence:

$\begin{aligned} f(1) &= 1; \\ f(2n) &= 2f(n) - 1, \quad \text{for } n \ge 1; \\ f(2n+1) &= 2f(n) + 1, \quad \text{for } n \ge 1. \end{aligned}$

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

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, B, C (official GATE 2022 final answer key)

Concept used: Compute small values and prove the patterns by induction on $n$ .

First step: Tabulate $f(1), \ldots, f(10)$ : e.g. $f(2) = 1$ , $f(3) = 3$ , $f(4) = 1$ , $f(5) = 3$ , and compare with each formula.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key