The problem:
This question is inspired by a proof of correctness for the algorithms question that can be found here
To summarize, starting from $0$, you want to get to some target $i > 0$.
You may only travel in increasing powers of two. For instance, starting from 0, you could do: $0 \rightarrow 1 \rightarrow 3 \rightarrow 7 \rightarrow 15...$
In other words, you can travel any distance $2^m -1, \quad m \in \mathbb{Z}^+$
At any point, you may reverse and similarly travel a distance $2^n -1$ in the opposite direction.
You may do this as many times as you want until you get to the target $i$, and the goal is to get to $i$ in the least number of "steps". Reversing your direction counts against you as a step.
The question:
I'm not sure if this question belongs here, but there is a detail in a supposedly valid algorithm (in fact, in many supposedly valid algorithms) that is often taken for granted, and which I have been unable to prove.
One such algorithm is a breadth first search algorithm, which simply looks at every possible position on the number line you could be after 1 step, 2 steps, 3 steps, and so on, until you get to $i$. This is wildly inefficient, so to speed this up, a trick is used that you only need to search within the interval $[0, 2i]$. That is, if you ever find yourself outside this interval, you can immediately give up searching any further down this branch.
I understand why you would never want to find yourself at some value on the number line $j < 0$, because you would eventually have to find a way to traverse a positive distance of $i + j$. However, you could have simply traversed a distance $i+j$ first, and then backtracked a distance $j$ to arrive at $i$, hence never having to find yourself at $j < 0$.
However, the detail which I am unable to prove is that you would never want to find yourself past the bound $2i$. I tried for a while to come up with possible counterexamples where the optimal path to $i$ was to first traverse to some $j > 2i$, and then backtrack to $i$, but I cannot find any counterexamples of this. I believe that this detail should intuitively be true, but I could not find a satisfying proof of this detail. Most people who "prove" the correctness of this detail simply say something along the lines of "well you would have to backtrack a distance $k := j - i > i$, and traversing any distance $k > i$ would have to take more steps."
However, I can immediately show that this is not true, because if we suppose that $k = 7$ and $i = 6$, then we could get to $k$ in 3 steps ($0 \rightarrow 1 \rightarrow 3 \rightarrow 7$), while we would get to $i$ in 5 steps ($0 \rightarrow 1 \rightarrow 3 \rightarrow 7 \rightarrow 7 \rightarrow 6$) (because that reversing takes a step). So it is certainly possible to traverse greater distances in less steps, so why would we not travel past $2i$?
I hope that made sense and I hope this is the correct place to ask this question. This detail struck me as something that had to be proven algebraically which is why I came here. Thank you!
We want to get to $i$ and you ask
Between $i$ and $2i$, if you have a $2^j - 1$ for some $j$, you can reach $2^j-1$ in fewer steps than getting to $2i+\delta$. If you reach $2^j-1$ then you can reverse to reach $i$ in fewer steps than reversing from $2i + \delta$ to $i$.
If there is a power of $2$, say $2^j$ satisfying $i \lt 2^j \le 2i$ then $i \le 2^j - 1 \lt 2i$.
See this MathOverflow answer for proof that there is a power of $2$ between $i$ and $2i$. In essence, write $2i$ in binary and replace all digits with $0$s after the leading $1$. That is a power of $2$ between $i$ and $2i$
That is because any position of the form $2^j - 1$ can be reached in $j+1$ steps using the sequence $1 \rightarrow 3 \rightarrow 7 \rightarrow \cdots \rightarrow (2^{j-1} - 1) \rightarrow (2^j - 1)$.
Let $i$ satisfy the inequality
$$\overbrace{(2^{j-1} - 1)}^{A} \lt i \lt \overbrace{(2^j - 1)}^B \lt 2i < \overbrace{(2i + \delta)}^{C} < \overbrace{(2^{j+1}-1)}^{D}$$
Let it take $A_i$ steps to get to $i$ through $A$ following the path taken so far. Similarly let it take $B_i$ steps to get to $i$ through $B$ with a reversal. There are three possibilities:
$A_i < B_i$
$A_i = B_i$
$A_i \gt B_i$
In each of these possibilities, we did not have to go beyond $2i$.
Now, replace $A,B,D$ with general integers you might reach if you continued down the path that you have taken so far where the inequality
$$A < i < B < 2i < \overbrace{(2i + \delta)}^{C} < D$$
holds i.e., $A, B, D$ are not of the form $2^\lambda - 1$. You can use the same argument as before to see that we don't need to go beyond $2i$.