Prove that any real non negative number can be expresed in golden ratio base using only 1 and 0

67 Views Asked by At

I´ve been thinking about this problem for a long time but I don´t reach any conclusion and I don´t find any related information. I would be grateful if someone could help me. Here is the problem:

Prove that any real non negative number can be expresed in golden ratio base using only 1 and 0.

(Remark: Some sources mention that we can express uniquely the number without any 1 being repeated consecutively in the expression, however for me it´s enough to proof that for any number we can express it in at least one way).

1

There are 1 best solutions below

0
On BEST ANSWER

A "greedy algorithm" should work. Let's denote the golden ratio as $\varphi$, which we can define explicitly as the positive root of $x^2-x-1=0$. Let $\alpha_0$ be our real, non-negative number. Then there is some $N_0$ such that $\varphi^{N_0}$ is the largest power of $\varphi$ less than or equal to $\alpha_0$. Now consider $\alpha_1:=\alpha_0-\varphi^{N_0}$. Since

$$\varphi^{N_0}\le\alpha_0<\varphi^{N_0+1},$$

we also have

$$0\le\alpha_1<\varphi^{N_0+1}-\varphi^{N_0}.$$

The expression on the right, rewritten as

$$\varphi^{N_0}\left(\varphi-1\right)=\varphi^{N_0}\left(\varphi^{-1}\right)<\varphi^{N_0}$$

What does this show us? By taking the leading "digit" of our representation to be $1$, we leave behind a smaller number, which doesn't need any more representation in the $N_0$ column.

(In fact, we've shown that $\alpha_1<\varphi^{N_0-1}$, which is why the digit after the $1$ will always be a $0$.)


Another way of looking at this: If any digit, say in place $N$, is greater than 1, then it represents at least $2\varphi^{N}$, which is greater than $\varphi^{N+1}$, so we're able to "carry" over to the next column.