 Solution

Observe the lazy walk on ${\mathbb{Z}}_{2^k}$ only after every second genuine jump. Two independent nearest-neighbor signs have sum $-2,0,2$ with probabilities $1/4,1/2,1/4$. Division by two therefore produces one step of the lazy simple random walk on ${\mathbb{Z}}_{2^{k-1}}$. The Strong Markov property at successive jump times proves