It all boils down to to prove that f(2k)<=f(2k-1) and f(2k)<=f(2k+1)

We have f(2k)=f(k)+1

Prove f(2k)<=f(2k-1)

f(2k-1)=Min(f(2k)+1, f(2k-2)+1). Clearly, f(2k)+1 > f(2k), we only need to compare

f(2k) vs. f(2k-2)+1

<==> f(k)+1 vs. f(2k-2)+1

<==> f(k) vs. f(k-1)+1.

Now, if k is odd, we have f(k)=Min(f(k+1)+1, f(k-1)+1), therefore, f(k)<=f(k-1)+1 --> f(2k)<=f(2k-1);

if k is even, say k=2m,

f(2m) vs. f(2m-1)+1

<==> f(2m) vs. (f(2m-2)+1)+1

<==> f(2m) vs (f(2m-2)+2)

<==> f(m) vs. f(m-1)+2.

From the above, let k=2^r*t, where t is an odd number, eventually the comparison becomes

f(t) vs. f(t-1)+(r+1),

since t is odd, we have f(t)<=f(t-1)+1<=f(t-1)+(r+1).

therefore we have f(2k)<=f(2k-1).