Traveling between integers- powers of 2 
Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. 

Consider the integers. We can only travel directly between two integers with a difference whose absolute value is a power of 2 and every time we do this it is called a step. The distance $d$ between two integers is the minimum number of steps required to get from one to the other. Note however that we can travel backwards. For instance $d(2,17)$ is 2: $2+16=18 \rightarrow 18-1=17$. 
How can we prove that for any integer n, we will always have some $d(a,b)=n$ where$b>a$? 

If we are only able to take forward steps I know that  the number of 1s in the binary representation of $b-a$ would be $d(a,b)$. However, we are able to take steps leftward on the number line...

It is easy to see that the function $s(n):=d(0,n)$ $\ (n\geq1)$ satisfies the following recursion:
$$s(1)=1,\qquad s(2n)\ =\ s(n), \qquad s(2n+1)=\min\{s(n),s(n+1)\}+1 \ .$$
In particular $s(2)=s(4)=1$, $s(3)=2$. 
Consider now the numbers $$a_r:={1\over6}(4^r+2)\qquad (r\geq2)$$ satisfying the recursion
$$a_2=3,\qquad a_{r+1}=4 a_r-1\quad (r\geq2).$$
The first few of these are $3$, $11$, $43$, $171$. I claim that
$$s(a_r-1)=s(a_r+1)=r-1,\quad s(a_r)=r\qquad (r\geq2)\ .$$
The claim is true for $r=2$. Assume that it is true for $r$.
 Then 
$$s(2a_r-1)=\min\{s(a_r),s(a_r-1)\}+1=r,\qquad s(2a_r)=r$$
and therefore
$$s(4a_r-2)=s(4a_r)=r,\quad s(4a_r-1)=\min\{s(2a_r),s(2a_r-1)\}+1=r+1\ .$$
The last line can be read as
$$s(a_{r+1}-1)=s(a_{r+1}+1)=r, \qquad s(a_{r+1})=r+1\ .$$
