# NT9

From Example Problems

Prove that any number can be represented by the sum of Fibonacci numbers.

The problem is known as Zeckendorf's theorem and a proof can be found here.

## please revise the statement of the problem.

If it is stated as so we can easily consider be a fibonnaci
number and construct

Perhaps the problem asks for **distinct** fibonacci numbers which added up
equal any integer ?

If so we can have the following perl program

$p[0]=0; $p[1]=1; $k=<>; $i=1; #building fibonnaci less than k while($k>$p[$i]) { $i++; $p[$i] = $p[$i-1]+$p[$i-2]; }; $i--; #decomposing k into distinctfibbonaci less than it while($k>0) { $k-=$p[$i]; print "$p[$i]".($k>0?'+':''); while($k<$p[$i]) { $i--; } }

The algorithm shows good evidence that this is possible.

I was not able to prove the problem for distinct fibonacci.