Can you add and subtract distinct powers of $\phi$? Because otherwise I do not believe this is true

Can someone please tell me which one of the two values is considered golden ratio: $\frac{\sqrt{5}+1}{2}>1$ or $\frac{\sqrt{5}-1}{2}<1$? Besides, regarding orl's question - it's possible that negative powers do the work.

It's the positive, I believe. It doesn't really matter, because the other one is just the negative power of the first.

I really don't see how one can do it by simply adding... Assuming we can subtract:

You can (must) use negative powers.

Elemennop, i think "sum" means addition only....otherwise note that the sequence {a_n}n, if n is even, a_n = phi^n + phi^(-n); if n is odd, a_n = phi^n - phi^(-n); then {a_n} gives the Lucas sequence (2, 1, 3, 4, 7, 11, 18...) , then a simple induction solves the problem (this is easy to see because if you can get all numbers from 1-7 as sums of distinct powers, add 11 to each give you 12-18 while still using distinct powers; similarly, adding 7 to 1-4 gives 8-11, so no overlap and every integer is covered.)

Can we just use the fibonacci series general formula, which include $1$ and $2$ thus we are done? :O

Sir, as an example to prove your ideas, can you show me how to write $10$ as the sum of distinct powers of $\frac{1+\sqrt{5}}{2}$ using the Fibonacci sequence?

See here https://en.wikipedia.org/wiki/Golden_ratio_base

tenniskidperson3 wrote: Sir, as an example to prove your ideas, can you show me how to write $10$ as the sum of distinct powers of $\frac{1+\sqrt{5}}{2}$ using the Fibonacci sequence? if golden ratio = t , then 10 = t^4 + t^2 + t^(-2) + t(^-4)

Use fibonacci and Lucas sequences, note that $\phi^n =\frac{f_n+L_n \sqrt{5}}{2}$ (where $f_n$ is the sequency of fibonacci and $L_n$ is Lucas' sequency), only see a recurrency with the coefficents to prove this

The key is to use the property $\tau^2 = \tau + 1$. Claim. Suppose that a positive integer $n$ can be written as the sum of powers of $\tau$. Then it can be written as a sum of powers of $\tau$ with no two exponents consecutive. Proof. Consider the largest $\tau^k$ in the expansion of $n$ such that $\tau^k$ and $\tau^{k+1}$ both appear in the expansion. Then, replacing $\tau^k$ and $\tau^{k+1}$ with $\tau^{k+2}$ yields another valid expansion, thus eliminating exactly one consecutive pair. We may repeat this process until no two powers of $\tau$ are consecutive. $\blacksquare$ Now we can induct upwards. Notice that $1 = \tau^0$, so the base case is obvious. For the inductive step, we have three scenarios. If $\tau^0$ is not in the expansion of $n$, then simply adding $\tau^0$ yields a valid expansion for $n+1$. If $\tau^0$ is in the expansion of $n$ and nor is $\tau^{-2}$, then removing $\tau^0$ and replacing it with $\tau + \tau^{-2}$ yields a valid expansion for $n+1$. (This is because an expansion of $n$ exists without consecutive powers by our first claim.) Finally, if $\tau^0$ and $\tau^2$ are both present, add $1 = \tau + \tau^{-2} - \tau^0$ to the expansion. Then, replace one of the $\tau^{-2}$ terms with $\tau^{-3}$ and $\tau^{-4}$. In general, if we have a $2\tau^{-2n}$ term, then we may replace one of the $\tau^{-2n}$ terms with $\tau^{-2n-1} + \tau^{-2n-2}$. We may repeat this process because the presence of a $\tau^{-2n}$ term means that a $\tau^{-2n-1}$ term cannot exist. Let $-2N$ be the least even power in the expansion of $n$. Then, the process must terminate and we have a valid expansion when we reach a $\tau^{-2N}$ term, as needed. Thus, our inductive step is complete, and every positive integer $n$ is representable.

We call the numbers that satisfy the problem good. Claim. There exists a finite set $X$ for a good number $n$ where $\sum\limits_{k \in X} \varphi^{k} = n$ such that $X$ does not contain any consecutive integer Proof. Let the good number $n = \sum\limits_{k \in Y} \varphi^{k}$. Suppose $a, a+1$ is the largest pair of consecutive integer in $Y$. Note that $\varphi^{a} + \varphi^{a+1} = \varphi^{a+2}$ and $a+2 \not \in Y$ since otherwise $a+1, a+2$ is an even larger pair of consecutive integers. Thus, the set $Y' = (Y-\{a,a+1\})\cup\{a+2\}$ is a possible representation of $n$. Doing this inductively for smaller pairs of consecutive integers finish the proof. Now, we will use induction to show that all positive integers are good. The base case is trivial (since $\varphi^{-2} + \varphi^{-1} = 1$). Suppose $n$ is good and $X$ is a representation of $n$ like one in the claim. If $0 \not \in X$, the set $X' = X \cup \{0\}$ will do. Otherwise, let $r,r-1$ be the largest pair of consecutive negative integers such that $r,r-1 \not \in X$, which must exist since $X$ is finite. Then, consider $T = \{-1, -3, -5, \dots, r, r-1\}$, we must have $X \cap T = \phi$ as otherwise it contradicts the maximality of $r, r-1$. Also, one can easily show that $\sum\limits_{k \in T} \varphi^{k} = 1$ by induction. Thus, $X' = X \cup T$ will do and clearly $X'$ is finite. Hence, by induction all positive integer is good. $\blacksquare$

Let $\phi$ denote the golden ratio. Thus: $\phi^2 = \phi+1$. We proceed by induction on $n$. The base case is trivial ($1 = \phi^{-1} + \phi^{-2}$). Now, assume that the result holds for some $n$. We will prove that it holds for $n+1$ too. Thus, there exists a "base" $\phi$ representation of $n$: $$n= (a_r a_{r-1} \cdots a_0. a_{-1} a_{-2} \cdots a_{-s})$$where $a_i \in \{ 0, 1\}$ for all $i$. Now, we will erase all the occurrences of $11$ in the decimal expansion of $n$. Now, consider the left-most two consecutive terms with $a_{k} = a_{k+1}=1$, then due to $\phi^2 = \phi+1$, we replace $\phi^{k}+\phi^{k+1} = \phi^{k+2}$. We repeatedly do this process until we have $a_{k} a_{k+1} = 0$ for all $k$. Thus: we have an expansion: $$n = \sum b_k \phi^k$$where $b_k b_{k+1}=0$ for all $k$ with $b_i \in \{0, 1 \}$. Now, we have $b_0 = 0$ then add $1$ and we are done. Else, $b_0=1$. Now, consider the largest non-negative integer $t$ such that: $b_{-t} = 1, b_{-t-1} = b_{-t-2} = 0$. Then: we replace $b_{-t} = 0$ and $b_{-t-1} = b_{-t-2} = 1$. We keep on repeating this step until $b_0=0$. Now we add $1$ and we are done.