From Example Problems
Jump to: navigation, search

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

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

The algorithm shows good evidence that this is possible.
I was not able to prove the problem for distinct fibonacci.