I like the "talk" section of wikipedia, Talk:Generalizations_of_Fibonacci_numbers. I am quoting from their writeup.
According to Binet's formula,
$$F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}$$
Since $\psi = -\frac{1}{\varphi}$, this formula can also be written as
$$F_n = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt 5}$$
Now if you factor the $-1$ out of the $-\varphi$, you get
$$F_n = \frac{\varphi^n-(-1)^{-n}\varphi^{-n}}{\sqrt 5}$$
...
And from Euler's identity, $-1 = e^{i\pi}$, so
$$F_n = \frac{\varphi^n-e^{i\pi n}\varphi^{-n}}{\sqrt 5}$$
Ok, now continuing on my own.... And from Euler's formula, $e^{i\pi n} = \cos (\pi n) + i \sin (\pi n)$, so Binet's solution can be equivalently expressed as $F_1$, to distinguish it from its complex conjugate.
$$F_1(z) = \frac{\varphi^z-(\cos (\pi z) + i \sin (\pi z))\varphi^{-z}}{\sqrt 5}$$
There is an alternative definition, with $-1 = e^{-i\pi}$, which leads to the complex conjugate solution, which I will label $F_2$.
$$F_2(z) = \frac{\varphi^z-(\cos (\pi z) - i \sin (\pi z))\varphi^{-z}}{\sqrt 5}$$
Due to the fact that linear combinations of solutions to the Fibonacci recurrence relation are also solutions, we can average $F_1$ and $F_2$ together, and get the real valued solution, $F_{\text{real}}(z)$, where at the real axis, the imaginary term cancels with its conjugate.
$$F_\text{real}(z) = \frac{F_1(z)+F_2(z)}{2} = \frac{\varphi^z-\cos (\pi z) \varphi^{-z}}{\sqrt 5}$$
I think both solutions are equally valid, and perhaps sometimes it seems more natural to have a real valued solution, and this derivation shows where the "cos" term in that solution comes from. As I noted in earlier comments, there is also some interesting behavior for the "ratio" function for these various solutions, $r(z)=\frac{F(z+1)}{F(z)}$, which I may post later, which connects the complex solution to the formal Schroeder function solution for the ratio function.
The procedure you describe, applied to $n$, finishes with the remainder of $n$ when divided by $9$. As the remainder behaves well with respect to the sum (
$r_9(r_9(a)+r_9(b))=r_9(a+b)$) you can work always with remainders. It is easy to see that two consecutive terms determine the whole sequence and there are a finite number of possible pairs, so that the sequence has to become periodic.
This can be explained easily using modular arithmetic and, in particular, your problem is a well-known one. See this article.
Best Answer
Recall that Fibonacci numbers are defined by $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$ for $n\ge1$.
For a multiset of positive integers $M$, let $\ell(M)$ be the number of integers in $M$, $s(M)$ be the sum of integers in $M$ and $p(M)$ be the sum of the squares of integers in $M$. Note that $p(M)\le s(M)^2$. Call a multiset of Fibonacci numbers $M$ a $k$-set if the $s(M)=k$. Let $g(k)$ be the multiset of Fibonacci numbers found by the greedy algorithm on $k\ge1$ that chooses the largest possible Fibonacci number at each stage.
The question is how we can prove the following claim.
Claim: Let $M$ be a $k$-set. Then $\ell(M)\ge\ell(g(k))$.
A rigorous proof
The basic ideas have been stated in the question.
Repeat the following operations on $M$ as long as one of the operations is possible.
We can verify that $\ell(M)$ is reduced by $1$, $s(M)$ is not changed and $p(M)$ is increased by $2\ge2$ by this operation.
We can verify that $\ell(M)$ is not changed, $s(M)$ is not changed while $p(M)$ is increased by $2{F_{n-1}}^2\ge2$ by this operation.
We can verify that $\ell(M)$ is reduced by $1$, $s(M)$ is not changed while $p(M)$ is increased by $2F_nF_{n+1}\ge2$ by this operation.
In summary, each operation will not increase $\ell(M)$, will not change $s(M)$ and will increase $p(M)$ by at least $2$.
Since $s(M)$ never changes, it is always equal to $k$. Since the numbers added by each operation are Fibonacci numbers, $M$ is always a $k$-set.
Since $p(M)$ is bounded by the constant $s(M)^2=k^2$, there cannot be more than $k^2/2$ operations. So the operations on $M$ will end.
At the end of all operations, $M$ is a $k$-set with neither equal numbers nor adjacent Fibonacci numbers, which is none other than the multiset of Fibonacci numbers in the Zeckendorf representation of $k$, which is known to be $g(k)$. Since $\ell(M)$ is not increased by each operation, we have proved the claim.
Zeckendorf representation can be found by the greedy algorithm
In order to make this answer a bit more self-contained, here are the main ideas for a proof of the known fact that the numbers in the Zeckendorf representation of $k$ are the numbers in $g(k)$.
Suppose $k=\sum _{{i=1}}^{j}F_{{c_{i}}}\ge3$, where $c_i\ge2$, with $c_{i + 1} > c_i + 1$. Given $k$, the greedy algorithm will choose $F_{c_j}$ first since $F_{c_j+1}$ $=F_{c_j}+F_{c_j-2}+ F_{c_j-4}+$ $\cdots+$ $F_{c_j\%2+2}+1$ $\ge k+1$ $>k$ and $F_{c_j}\le k$.
Given $k\ge3$, suppose the greedy algorithm will choose $F_t$ for some $t\ge3$. Since the greedy algorithm will not choose $F_{t+1}$, we know $k<F_{t+1}$. Hence $k-F_t<F_{t-1}$.
Some remarks
You can, in fact. For example, $16=8+8$. The greedy algorithm will find $16=13+3$. Both sum use two Fibonacci numbers. In other words, although the numbers found by the greedy algorithm given $k$, in which there are no duplicate numbers will always be as few as possible, there could be other $k$-sets with duplicate numbers that have the same cardinality.
On the other hand, there cannot not be three equal Fibonacci numbers in an optimal sum. $F_n+F_n+F_n=F_{n+2}+F_{n-2}$ for $n\ge3$.