Bài 3

Khi chuyển từ $k$ sang $k+1$, ta bỏ $k+1$ và thêm $2k+1$ cùng $2k+2$. Biểu diễn nhị phân của $2k+2$ là biểu diễn của $k+1$ ghép thêm số 0, nên hai đóng góp này triệt tiêu. Vì vậy $f(k+1)=f(k)+1$ đúng khi $2k+1$ có ba chữ số $1$; nếu không thì $f(k+1)=f(k)$.