NT9

From Exampleproblems

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 f₁ = 1 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.