Feynman's 'Representation Theory' for Numbers Between $1$ and $2$

You'll find in the wikipedia Logarithm article a section called Feynman's algorithm.

The paragraph makes claims about uniqueness that, when interpreted mathematically, is incorrect; see this math.stackexchange post,

Feynman's Algorithm for computing a logarithm of a number in [1,2]

But there can be little doubt that the algorithm work:

We define for $$n \ge 1$$

$$\tag 1 H_n = \frac{1}{2^n}$$

Let $$x$$ be a real number between $$1$$ and $$2$$ and set $$P_0 = 1$$

Let $$P_n$$ be recursively defined. If $$P_n * (1 + H_{n+1}) \gt x$$ set

$$\tag 2 P_{n+1} = P_n$$

Else set

$$\tag 3 P_{n+1} = P_n * (1 + H_{n+1})$$

Claim; The monotone increasing sequence $$P_n$$ converges to $$x$$.

Provide a proof that this is true.

My Work

We know that the bounded sequence converges, and by construction it looks like it is doing everything it can to 'get to $$x$$', but this is not the usual binary subdivision of intervals that is easy to work with.

When an update occurs at $$n+1$$ we get $$P_{n+1} = P_n + H_{n+1} * P_n$$. So we 'add in' the new term $$H_{n+1}$$ and then $$H_{n+1}$$ applied to other terms 'shifts them down' into lower order terms. It might be a matter of solving equations along with each step of the algorithm, but it isn't easy to see how we are guaranteed to build $$x$$ that has the form,

$$\tag 4 x = 1 + \sum_{k=1}^\infty b_k H_k \; \text{ with } b_k \in \{0,1\}$$

Also, I searched for a proof of this but couldn't find one. So any comments with links would be much appreciated.

Let $$y$$ be the limit of the $$P_n$$ and suppose for a contradiction that $$y. There is a minimal $$m$$ such that $$y(1+H_m).
Then $$1+H_m$$ must be one of the terms in the product defining $$y$$, for the sequence of $$P_n$$ is increasing and so $$P_{m-1}(1+H_m) \leq y(1+H_m) < x$$. Similarly every $$1+H_{m+k}$$ for $$k\geq 0$$ is a factor in $$y$$, and $$y = (1+a_1 2^{-1})(1+a_2 2^{-2})\cdots (1+a_{m-1}2^{-(m-1)}) (1+2^{-m})(1+2^{-m-1})(1+2^{-m-2})\cdots$$ where each $$a_i$$ is 0 or 1. Now $$a_{m-1}$$ might not be zero, but there is a biggest $$r$$ such that $$a_{r-1}=0$$ (at least one must be zero since $$\prod_{k=1}^\infty (1+2^{-k}) >2 \geq x$$) and we have $$y = P_{r-2} (1+2^{-r})(1+2^{-r-1})\cdots$$ Note that $$1+2^{-r+1} < (1+2^{-r})(1+2^{-r-1})\cdots$$ since the rhs is greater than $$1+ 2^{-r}+2^{-r-1}+2^{-r-2}+\cdots = 1+2^{-r+1}$$. That means $$P_{r-2} (1+H_{r-1}) < y < x$$, contradicting $$a_{r-1}=0$$
• Really cool that $\prod_{k=1}^\infty (1+2^{-k}) >2$. Too bad it is not equal to $e$. Hmm, kinda makes you think that looking at $\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}$ might be fun! Commented Dec 14, 2018 at 14:46