GATE CS 2022 (Forenoon) — Question 51

Discrete MathematicsRecurrence Relations and Generating FunctionsMSQ2 marksHard

Consider the following recurrence:
\[ f(1) = 1; \]
\[ f(2n) = 2f(n) - 1, \text{ for } n \geq 1; \]
\[ f(2n + 1) = 2f(n) + 1, \text{ for } n \geq 1; \]
Then, which of the following statements is/are TRUE?
  1. A
    \(f(2^n - 1) = 2^n - 1\)
  2. B
    \(f(2^n) = 1\)
  3. C
    \(f(5.2^n) = 2^{n+1} + 1\)
  4. D
    \(f(2^n + 1) = 2^n + 1\)
Practise the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkDiscrete Mathematics and Its Applications (Rosen)Logic, sets, relations, combinatorics and graph theory, with worked examples.
Practise more on Recurrence Relations and Generating FunctionsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group