Minimum number of fibonacci numbers sum to k proof

Question

The minimum number of fibonacci numbers needed to sum up to k can be computed with a greedy algorithm that simply loops through the fibonacci numbers from greatest (less than k) to lowest, and takes the number when it can. Subtract from k, and repeat. I am interested in proving why this is correct.

This codeforces thread has some insights: https://codeforces.com/blog/entry/60305,

I understand these specific points:

1. It's never optimal to take two adjacent fibonacci numbers since you can just use the next fibonacci number instead.
2. If you were to sum up all the non-adjacent fibonacci numbers less than fib(n) for some n, it'd still be less than fib(n).
3. Instead of repeating a fibonacci number twice, you can decompose it

However, I don't understand how everything connects together to prove why the greedy algorithm is optimal. Could someone lay out the full proof? One other essential point that I don't understand is why you couldn't, in theory, use some fibonacci number multiple times. elsantodel90's last comment addresses this, but I think I don't understand the "big picture" enough to see why it addresses it.

Answer 1

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.

• If there are two $1$'s in $M$, replace them with a $2$.
  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.
• If there are two $F_n$'s in $M$ for some $n\ge3$, replace them with $F_{n+1}$ and $F_{n-2}$.
  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.
• If there are $F_n$ and $F_{n+1}$ in $M$ for some $n\ge1$, replace them with $F_{n+2}$.
  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

Why you couldn't, in theory, use some Fibonacci number multiple times?

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$.