Sum of Distinct Fibonacci Numbers (Some Proofs)

Sep. 9, 2021, 15:23:02

A couple of days ago, my friends and I worked together on an algorithm problem we found online. I proposed a potential solution but I didn't come up with a proper proof for it. Intuition says the theory is correct, but an actual proof for it requires multiple steps as dictated here.

The question is - "Given 2 positive integers, n and k, check whether k can be represented as a sum of n distinct fibonacci numbers".

My Solution

There are 3 steps to my solution:
1. Find the minimum number of distinct Fibonacci numbers k can be written into.
2. Find the maximum number of such Fibonacci numbers.
3. Check whether k is in that range.

Step 1

To find the minimum set of Fib numbers, I proposed the theory that "the smallest set of distinct Fibonacci numbers that sum to k must contain p, which is the largest Fib number that is smaller than k".

Lemma 1: Every positive integers can be written as a sum of distinct Fib numbers.

There is already a theorem that indirectly proves this statement - the Zeckendorf's theorem, but it's better to prove it ourselves as the proof is simple to write and serves as a good refresher on "Proof by Induction" which we will use later for the statement above.

Base Case:
1 and 2 can be written as a sum of distinct Fib numbers (ie. they are Fib numbers themselves).
Induction Hypothesis:
Assume the statement is true for ALL positive number k with 2<k, let's prove the statement is also true for k+1. Let's also define a convenient function F(k) which gives the set of distinct Fib numbers k can be written as a sum of.
Induction Case:

We know if k+1 is a Fib number already, the statement is trivially correct. Therefore, we only need to look at the case when k+1 is not a Fib number.

Let p,q be two Fib number that are immediately to the left of k+1 with q < p < k+1 (ie. if k+1=9, then q=5 and p=8). Since k+1-p must be less than q, otherwise the immediate left Fib number of k+1 is p+q, and q<p, we know k+1-p < p.

Then by our induction hypothesis, we know k+1-p can be written as a sum of distinct Fib numbers smaller than p (ie. not including p). Therefore, we can prove k+1 can be written as a sum of distinct Fib numbers, namely {p} ⋃ F(k+1-p).

Lemma 2: The sum of the first distinct n Fib numbers is f_n+2 - 2.

This fact is easily proven by writing out each Fib number as the difference between 2 of its immediate larger Fib numbers. So, f_n = f_n+2-f_n+1, f_n-1 = f_n+1-f_n, ... f₁ = f₃-f₂. The middle terms cancel out when we add them together to get f_n = f_n+2-2.

Proof: The smallest set of distinct Fib numbers that sums to k must contain the largest Fib number that is smaller than k

Let's define a convenient function M(k) which gives the smallest set of distinct Fib numbers that sums to k. Similarly the statement can be proven by induction.

Base Case:
1 ∈ M(1), 2 ∈ M(2).
Induction Hypothesis:
Assume the statement is true for ALL 1..k-1. Let's prove it's also true for k.
Induction Case:

Let's define f_n to be the largest Fib number that is smaller than or equal to k, and f_n-1 to be the largest Fib number that is smaller than f_n-1. Let's also assume the statement is wrong and f_n is not in the smallest set (ie. f_n ∉ M(k)).

Because we know from Lemma 2 that the sum of the first x Fib numbers is smaller than f_x+2, then the smallest set must contain f_n-1 (ie. f_n-1 ∈ M(k)). Otherwise, the largest value we can achieve by taking everything smaller than, and including f_n-2 is f_n-1 < f_n ≤ k.

So we can split M(k) into 2 parts, M(k) = {f_n-1} ⋃ M(k-f_n-1). The work now is to find the minimum set of distinct Fib numbers that sum to k-f_n-1.

From our definition of f_n and f_n-1, and the definition of Fib numbers, we know f_n ≤ k < f_n-1+f_n and thus f_n-2 = f_n-f_n-1 ≤ k-f_n-1 < f_n.

By the induction hypothesis, we know the minimum set of distinct Fib numbers for k-f_n must contain f_n-2. Since both f_n-1 and f_n-2 are present in M(k), M(k) is not the smallest set.

Therefore, the smallest set must contain f_n.

Now with the proof in place, we can device a greedy algorithm that repeatedly takes the largest Fib number possible until we get a sum equal to k.

Step 2

Once we know the smallest set, we can try expanding it by breaking the numbers in this set into smaller numbers to obtain the maximum set.

An orderly way of achieving this is to start with the smallest number in the set and break it into numbers as small as possible. However, if breaking the current number results in duplicate Fib numbers being used, we would stop.

Lemma 3: All sets of distinct Fib numbers that sum to k can be transformed into the minimum set M(k) by combining neighboring Fib numbers.

Let's prove by contradiction. Assume we have a set of distinct Fib numbers S(k) that sums to k and it doesn't include f_n, the largest Fib number smaller or equal to k, both directly and indirectly (ie. elements of the set cannot be combined to get f_n).

From Lemma 2 we know f_n-1 must be in S(k) or we would never get to a sum of k. As f_n-1 is fixed, we now must pick the remaining Fib numbers that is smaller than f_n-1 and which together sum to k-f_n-1 ≥ f_n-2. By Lemma 2 again, we know we can only take f_n-2 or f_n-3. Otherwise, we would never get to the expected sum (ie. k-f_n-1).

However, by the definition of S(k), we must not include f_n-2 in the set or we indirectly include f_n (ie. f_n = f_n-1+f_n-2). This leaves only f_n-3 as the valid next number to pick. The remaining sum is k-f_n-1-f_n-3 ≥ f_n-4.

The only valid next choices from this stage on are f_n-5, f_n-7, f_n-9... And the remaining sum keeps decreasing but never reaches 0: f_n-4, f_n-6, f_n-8....

In the end, there are only 2 possibilities: the last Fib number included is either 1 or 2. No matter which case it is, if we sum the Fib numbers we have already chosen, we will always get a remaining value of 1, which we must get by adding another 1.

However, adding a 1 to the set will make the set indirectly contain f_n (ie. combine terms all the way back to f_n), which contradicts with the definition of S(k). Therefore, all valid sets of distinct Fib numbers that sum to k must directly or indirectly contain f_n.

It's easy to see that if we apply this fact repeatedly on k (ie. like how we computed M(k) in step 1), we would get a set that is either M(k) or can be transformed into M(k) by combining terms.

Now that we know all valid sets that have a sum of k can be transformed into the minimum set M(k). Then it suffices to show that the maximum set obtained by transforming the minimum set is indeed the global maximum set.

But how do we transform M(k) to obtain the maximum set? The idea is simple, to break the Fib numbers in M(k) as many times as possible. However, I haven't come up with a solid proof for my algorithm, so the best I can do is to offer an intuitive explanation.

It is worth noting that there is only one way to break a single Fib number - breaking f_x into f_x-1 and f_x-2, and then breaking f_x-2 into f_x-3 and f_x-4, etc. Any other breaking sequence would yield duplicates (ie. can be easily proved).

To break multiple numbers, we must follow certain rules to not introduce duplicates. During the process of breaking down a larger Fib number, and when the sequence of numbers being broken into, overlaps with a smaller Fib number, the breaking stops. Otherwise, we will certainly introduce duplicates. For example, let's assume M(k) = {3,21}. After breaking 21 once into {13,8}, the next breaking will generate another 3 which is redundant.

Therefore, we must break a Fib number as many times as permitted if the final sequence doesn't overlap with other Fib numbers.

Step 3

We check whether n is in the range.

Code

Useful Links/References:

Zeckendorf's theorem - Wikipedia