Consider the following recurrence: f(1) = 1 f(2n) = 2f(n) − 1 for n ≥ 1 f(2n +…

Key idea: build numbers by their binary digits. Appending a 0 to n (making 2n) uses f(2n)=2f(n)-1, and appending a 1 (making 2n+1) uses f(2n+1)=2f(n)+1.

• f(2^n)=1 because 2^n is obtained by appending n zeros to 1. Applying f(2m)=2f(m)-1 repeatedly gives f(2^n)=2^n·f(1)-(2^n-1)=2^n-(2^n-1)=1.

• f(2^n-1)=2^n-1 because 2^n-1 has n ones in binary. Starting from f(1)=1 and applying f(2m+1)=2f(m)+1 repeatedly (or by induction: base n=1 holds and if f(2^n-1)=2^n-1 then f(2^{n+1}-1)=2f(2^n-1)+1=2^{n+1}-1) yields the result.

• If '5.2^n' means 5·2^n, then f(5·2^n)=2^{n+1}+1. Indeed, f(5)=3, and applying the even-step map T(x)=2x-1 n times gives T^n(x)=2^n x-(2^n-1). With x=f(5)=3 this yields 2^n·3-(2^n-1)=2^{n+1}+1.

• The statement f(2^n+1)=2^n+1 is false in general: for n=2, 2^n+1=5 but f(5)=3, so the equality fails.