Zeckendorf's Theorem -- How to Represent a Positive Integer with Fibonacci Numbers?

Zeckendorf's Theorem is about that every positive integer can be represented in the form of the sum of one or more Fibonacci numbers.

For example, 6 = 3 + 2 + 1, 10 = 8 + 2. We can further represent these positive integers in the binary form of Fibonacci numbers. Thus, 6 can be represented as "111" which means fibo(1) +  fibo(2) + fibo(3) -- the sum of the first, second and third Fibonacci numbers. Similarly, 10 can be represented as "10010" which means fibo(2) +  fibo(5)  --  the sum of the fsecond and fifth Fibonacci numbers.

How to find the Fibonacci numbers that sum to a particular positive integer? Basically you can use DP and leverage the binary form.

• 1 can be represented as "1", 2 as "10", 3 as "11", 4 as "101", 5 as "110". Thus, we can observe the binary form of a positive integer i is just the immediate next number of the binary form of a i-1. However, this "immediate next" is slightly different when an integer has a binary form of all "1". For example, 3 is "11". The  "immediate next" of "11" is not "100" but "101". This is due to the nature of Fibonacci numbers. We know "100" = "11" since fibo(n) = fibo(n-1) + fibo(n-2). So here we need to add one more "1" to "100".
• Based on the above analysis, we can get those Fibonacci numbers for a particular positive integer by using DP.

Actually not only positive integers, negative integers can also be represented in the sum of "broadly defined" Fibonacci numbers.