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,...

Question

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(2^n - 1) = 2^n - 1  for all n >= 1
B. f(2^n) = 2^(n-1)  for all n >= 1
C. f(2^n + 1) = 3  for all n >= 1
D. f(2^n) = 1  for all n >= 1

Accepted Answer

Statements A, C, and D are TRUE. Statement B is FALSE. The recurrence is a divide-and-halve rule identical to the previous question's a_n. We need to check each statement by computing f on structured inputs like powers of 2 and neighbors. The function f maps n to a value related to the signed binary expansion of n, so special inputs like 2^k (all trailing zeros in binary) and 2^k - 1 (all ones in binary) have predictable behavior.

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(2^n - 1) = 2^n - 1 for all n >= 1 B. f(2^n) = 2^(n-1) for all n >= 1 C. f(2^n + 1) = 3 for all n >= 1 D. f(2^n) = 1 for all n >= 1

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