# NT9

Prove that any number $x\ {\boldsymbol {\epsilon }}\ {\mathbb {Z}}$ 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 $f_{1}=1$ be a fibonnaci number and construct $\forall k=k\cdot f_{1}$
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.