GATE CS 2022 Q41 — Combinatorics: Counting, Recurrence Relations, Generating Functions

The given recurrence relation is the classic Josephus recurrence:

Any positive integer $N$ can be uniquely written in the form $N = 2^m + l$, where $m \geq 0$ and $0 \leq l < 2^m$. The closed-form solution for this recurrence is:

Let us evaluate each option using this closed-form expression:

• Option A: For $f(2^n - 1)$, we can write $2^n - 1 = 2^{n-1} + (2^{n-1} - 1)$. Here, $m = n-1$ and $l = 2^{n-1} - 1$.
  Applying the formula: $$f(2^n - 1) = 2(2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1$$ Thus, Option A is TRUE.
• Option B: For $f(2^n)$, we can write $2^n = 2^n + 0$. Here, $m = n$ and $l = 0$.
  Applying the formula: $$f(2^n) = 2(0) + 1 = 1$$ Thus, Option B is TRUE.
• Option C: For $f(5 \cdot 2^n)$, we can write $5 \cdot 2^n = 2^{n+2} + 2^n$. Here, $m = n+2$ and $l = 2^n$ (since $2^n < 2^{n+2}$).
  Applying the formula: $$f(5 \cdot 2^n) = 2(2^n) + 1 = 2^{n+1} + 1$$ Thus, Option C is TRUE.
• Option D: For $f(2^n + 1)$, we can write $2^n + 1 = 2^n + 1$. Here, $m = n$ and $l = 1$.
  Applying the formula: $$f(2^n + 1) = 2(1) + 1 = 3$$ This is not equal to $2^n + 1$ for $n > 1$. Thus, Option D is FALSE.