Is this conjecture on Fibonacci sums correct?

Question

I have the following conjecture, need to know a proof just in case mine is wrong, or the conjecture itself is wrong.

The sum of $k$ distinct Fibonacci numbers can be written in at most $k$ ways as the sum of another $k$ distinct numbers from the sequence

Proof: Take, say 4, Fibonacci numbers with distinct values: $$144+34+3+2$$ We can see that we must maintain the distinctness and number of the Fibonacci numbers. So when we split the numbers; $$[89+55]+[13+21]+3+2$$

It is immediately apparent that if some numbers are split into smaller Fibonacci numbers, others must be merged to keep only 4 numbers. Thus, 3+2 becomes 5, and either 144 or 34 kept as-is. Thus, $$144+34+3+2=89+55+34+5=144+21+13+5$$

I know it's a rudimentary proof, and $k$ ways of writing the same sum is probably a wrong upper bound, but at least it works for now.

Please do let me know what's wrong. Thanks.

Answer 1

We show that the conjectured upper bound of $k$ is a fair distance from the truth.

Let $W$ be a set of $3n$ distinct Fibonacci numbers, of which $n$ are lonely (no other Fibonacci number in $W$ is near them) and the remaining $2n$ are lonely couples. A lonely couple is a set of two consecutive Fibonacci numbers, with no other element of $W$ near them. Let $N$ be the sum of the Fibonacci numbers in $W$.

Then we can get another representation of $N$ as a sum of $3n$ Fibonacci numbers by selecting any $k$ lonely numbers, and representing each of them as a sum of two consecutive Fibonacci numbers, and selecting any $k$ lonely couples, and expressing each of their sums as a single Fibonacci number.

The $k$ lonely numbers can be chosen from the $n$ lonely numbers in $W$ in $\binom{n}{k}$ ways. For each choice, the $k$ lonely couples can be chosen in $\binom{n}{k}$ ways. It follows that $N$ has at least $$\sum_{k=0}^n \binom{n}{k}\binom{n}{k}$$ representations as a sum of distinct Fibonacci numbers. It is well-known that the above sum is equal to $\binom{2n}{n}$. For large $n$, this is much larger than the $3n$ that the conjecture would suggest. Indeed by using the Stirling formula, one can show that $\binom{2n}{n}$ is asymptotically equal to $\sqrt{\frac{2}{\pi}}\frac{2^{2n}}{\sqrt{2n+1}}$.

Answer 2

As a general rule, you'll want to use Zeckendorf's theorem to find these representations; it says that any number has a unique representation as the sum of nonconsecutive Fibonacci numbers. As André has noted, your conjecture is false in general, but it is possible to find a straightforward bound on the number of possible sums.

Let's say you want to write $k$ as the sum of $n$ Fibonacci numbers, and the Zeckendorf's theorem sum contains $m<n$ terms. From any $n$-term sum you like, you'll be able to get the Zeckendorf sum by repeatedly combining terms until no remaining terms are consecutive. This implies that you can get any $n$-term sum by starting with the Zeckendorf sum and splitting up terms in it until you get $n$ of them.

Say you start with a single term $F_a$. The only way to split that is as $F_a=F_{a-1}+F_{a-2}$; the only way to split that is as $F_{a-1}+F_{a-3}+F_{a-4}$; and so on -- that is, any sum that began as a single Fibonacci number has at most one representation as the sum of $n$ distinct Fibonacci numbers for any $n$ (since at each point the indices differ by at most two, the only additional split that's possible comes from breaking up the smallest number in the sum).

So, if you start with a Zeckendorf sum that has $m$ terms, your only possible decision is how many times to split up each of those terms; once you know that, you'll have a unique sum. (It may be that your terms will "collide" and you won't get a sum of distinct Fibonacci numbers, but you'll certainly get every possible sum from some such specification, so this leads to an overcount.) To get an $n$-term sum, you need to split a total of $n-m$ times. By a stars-and-bars argument, there are at most ${n-1 \choose m-1}$ ways of doing this. So a repaired version of your conjecture would state:

If the Zeckendorf sum for $k$ contains $m$ terms, there are at most ${n-1 \choose m-1}$ ways of writing $k$ as the sum of $n$ distinct Fibonacci numbers.