Let $a(n)$ be A214973, number of terms in greedy representation of $n$ using Fibonacci and Lucas numbers.
Let $b(n)$ be A329320, sequence which arises from attempts to simplify computing of A329319. Here
$$b(n)=b\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+1-f(n+1), b(0)=0$$
where $f(n)$ is A035263, trajectory of $1$ under the morphism $0$ -> $11$, $1$ -> $10$; parity of $2$-adic valuation of $2n$.
Let $c(n)$ be A048679, compressed fibbinary numbers (A003714), with rewrite $0$->$0$, $01$->$1$ applied to their binary expansion.
Then sequencedb.net conjecture that
$$a(n)=b(c(n))$$
Is there a way to prove it?
Best Answer
Sure. Start with the Zeckendorf representation of $n$, $$ n = \sum_{ i} F_{j_i} $$ where $F_j$ are the Fibonacci numbers and $j_i \geq j_{i-1} + 2$.
Then the fibbinary number associated to $n$ is $\sum_i 2^{j_i}$ and $c(n)$ is obtained from this by removing a zero in front of each $1$, i.e. $$c(n) = \sum_i 2^{ j - (i-1)}$$
Now the $b(m)$ function is written in a confusing way. It's defined using the function 1-AO35263, where A035263(n) counts the number of trailing zeroes of $2n$, modulo $2$, so 1- A036263(n) simply counts the number of trailing zeroes of the binary expansion of $n$, modulo $2$. So $b(m)$ is the sum over $k$ of the number of trailing zeroes of $\lfloor \frac{m}{2^k} \rfloor+1$, mod 2. In other words, $b(m)$ is the sum over $k$ of the number of trailing ones of the binary expansion $ \lfloor \frac{m}{2^k} \rfloor$, mod $2$. If we break the binary expansion of $m$ into blocks of consecutive ones separated by zeroes, we see that each block of length $\ell$ produces one quotient with $\ell$ trailing ones, one with $\ell-1$ trailing ones, etc. down to one with $1$ trailing ones, for a total contribution of $\lceil \frac{\ell}{2} \rceil$.
So $b(m)$ is the sum over blocks of consecutive ones in the binary expansion of $m$ of half the number of ones in the block, rounded up.
Now we make the following observation. For $n = \sum_{i=1}^k F_{j_i}$ in Zeckendorf representation, if $ i_{k-1} = i_k-2$ then the largest Fibonacci-Lucas number $\leq n$ is $F_{i_k} + F_{i_k-2} = L_{i_k-1}$ and otherwise the largest Fibonacci-Lucas number $\leq n$ is $F_{i_k}$.
This can be checked quickly by properties of Fibonacci and Lucas numbers. We have $F_n \leq L_{n-1} \leq F_{n+1}$ so it suffices to prove in the first case that $F_{i_k+1} $ is too large and in the second case that $L_{i_k-1}$ is too large. In the first case, this claim follows from the Lemma used in the proof of the Zeckendorf decomposition and in the second case $L_{i_k-1} = F_{i_k} + F_{i_k-2}$ is too large by the same lemma after subtracting $F_{i_k}$ from both sides.
Using this and the definition of greedy algorithm, we can see that if $i_{k-1} = i_{k}-2$ then $a(n) = a(n- F_{i_k} - F_{i_k-2}) + 1$ and if $i_{k-1}< i_k-2$ then $a(n) = a(n-F_{i_k})-1$.
We can now prove $a(n) = b(c(n))$ by induction. In the first case, passing from $n$ to $n- F_{i_k} - F_{i_{k}-2}$ removes a leading $11$ from $c(n)$, and thus subtracts $1$ from $b(c(n))$ since it reduces the length of a block of ones by two, while in the second case, passing from $n$ to $n-F_{i_k}$ removes a leading $1$ followed by one or more $0$s from $c(n)$, and thus subtracts $1$ from $b(c(n))$ since it removes a block of ones of length one.
Since we passed to a lower number and shifted both $a(n)$ and $b(c(n))$ by the same amount, the two sequences are equal as long as they are equal in the base case $n=0$, which is automatic: $a(0) =0 = b(0 ) =b(c(0))$