Consider the following recurrence: f(1) = 1; f(2n) = 2 f(n) - 1, for n 1; f(2n+1) = 2 f(n) + 1, for n 1. Then, which of the following statements is/are TRUE? A) f(2n - 1) = 2n - 1 B) f(2n) = 1 C) f(5 2n) = 2n+1 + 1 D) f(2n + 1) = 2n + 1

Official answer: A) f(2n - 1) = 2n - 1; B) f(2n) = 1; C) f(5 2n) = 2n+1 + 1. Explanation: Let us compute values of f(k) for small values of k and test each statement: - Base case: f(1) = 1 - For n = 1: - f(2) = 2f(1) - 1 = 2(1) - 1 = 1 - f(3) = 2f(1) + 1 = 2(1) + 1 = 3 - For n = 2: - f(4) = 2f(2) - 1 = 2(1) - 1 = 1 - f(5) = 2f(2) + 1 = 2(1) + 1 = 3 - For n = 3: - f(6) = 2f(3) - 1 = 2(3) - 1 = 5 - f(7) = 2f(3) + 1 = 2(3) + 1 = 7 - For n = 4: - f(8) = 2f(4) - 1 = 2(1) - 1 = 1 - f(9) = 2f(4) + 1 = 2(1) + 1 = 3 - For n = 5: - f(10) = 2f(5) - 1 = 2(3) - 1 = 5 Now, evaluate each option: 1. Option (A): f(2n - 1) = 2n - 1 - For n=1: f(1) = 1 = 21 - 1. - For n=2: f(3) = 3 = 22 - 1. - By induction: f(2n - 1) = f(2(2n-1-1) + 1) = 2f(2n-1-1) + 1 = 2(2n-1-1) + 1 = 2n - 1. - Option (A) is TRUE. 2. Option (B): f(2n) = 1 - For n=1: f(2) = 1. - By induction: f(2n) = 2f(2n-1) - 1 = 2(1) - 1 = 1. - Option (B) is TRUE. 3. Option (C): f(5 2n) = 2n+1 + 1 - For n=0: f(5) = 3 = 20+1 + 1. - For n=1: f(10) = 2f(5) - 1 = 2(3) - 1 = 5 = 21+1 + 1. - By induction: f(5 2n) = 2f(5 2n-1) - 1 = 2(2n + 1) - 1 = 2n+1 + 1. - Option (C) is TRUE. 4. Option (D): f(2n + 1) = 2n + 1 - For n=2: f(22 + 1) = f(5) = 3 22 + 1 = 5. - Option (D) is FALSE. Thus, statements A, B, and C are TRUE.

Engineering Mathematics · Recurrence Relations

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2022 Q51 · MSQ · 2 marks

Consider the following recurrence: $f(1) = 1;$ $f(2n) = 2 f(n) - 1, \quad \text{for } n \ge 1;$ $f(2n+1) = 2 f(n) + 1, \quad \text{for } n \ge 1.$ Then, which of the following statements is/are TRUE?

Select one or more options

Key concept

Recurrence Relations

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Recurrence Relations

In GATE CS, Recurrence Relations under Engineering Mathematics is tested as a concise 1-mark topic focused on linear homogeneous recurrence relations of degree 2. Questions either require setting up a recurrence relation from a combinatorial constraint (e.g., restricted binary strings) or solving a second-order linear recurrence relation using characteristic roots to find either an explicit closed-form formula or its asymptotic tight bound ( ). All provided PYQs are conceptual, analytical 1-mark multiple-choice questions without diagrams.

Full Recurrence Relations guide →

More on Recurrence Relations

All 4 questions on Recurrence Relations →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Engineering Mathematics · Recurrence Relations

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2022 Q51 · MSQ · 2 marks

Consider the following recurrence: $f(1) = 1;$ $f(2n) = 2 f(n) - 1, \quad \text{for } n \ge 1;$ $f(2n+1) = 2 f(n) + 1, \quad \text{for } n \ge 1.$ Then, which of the following statements is/are TRUE?

Select one or more options

Key concept

Recurrence Relations

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Recurrence Relations

Full Recurrence Relations guide →

More on Recurrence Relations

All 4 questions on Recurrence Relations →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Consider the following recurrence: $f(1) = 1;$ $f(2n) = 2 f(n) - 1, \quad \text{for } n \ge 1;$ $f(2n+1) = 2 f(n) + 1, \quad \text{for } n \ge 1.$ Then, which of the following statements is/are TRUE?

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2022

More on Recurrence Relations

Consider the following recurrence: $f(1) = 1;$ $f(2n) = 2 f(n) - 1, \quad \text{for } n \ge 1;$ $f(2n+1) = 2 f(n) + 1, \quad \text{for } n \ge 1.$ Then, which of the following statements is/are TRUE?

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2022

More on Recurrence Relations

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2022

More on Recurrence Relations

Share this solution

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2022

More on Recurrence Relations

Share this solution