8) How to prove that every positive integer can be written as the sum of one or

Question

8) How to prove that every positive integer can be written as the sum of one or more distinct non-consecutive Fibonacci numbers?

9) How to prove that the sum of any set of distinct non-consecutive Fibonacci numbers whose largest member is Fk is strictly less than Fk+1?

10) How to prove that no positive integer can be written in two different ways as the sum of distinct non-consecutive Fibonacci numbers?

11) How to show that the set of positive integers can be partitioned into Fibonacci sets (i.e. there's a collection of Fibonacci sets so that every positive integer is in precisely one of them) by referencing questions 8 and 10?

Explanation / Answer

8) Every positive integer can be written as the sum of one or more distinct non-consecutive Fibonacci numbers this was explained by the Zeckendorf's theorem.

Zeckendorf's Theorem :

The proof for the Zeckendorf's theorem is given by the induction method.

For n= 1,2,3 the numbers itself are the fibonacci numbers. For n = 4 we get 4 = 3+1 where both 3 and 1 are fibonacci numbers.

Suppose for each n k has a Zeckendorf representation.

If k + 1 is a Fibonacci number then we could prove the statement, else there exists j such that Fj < k + 1 < Fj+1.

Now consider a = k + 1 Fj. Since a k, a has a Zeckendorf representation (by the induction hypothesis).

We know that, Fj + a < Fj+1 and since Fj+1 = Fj + Fj1 (by definition of Fibonacci numbers), a < Fj1, so the Zeckendorf representation of a does not contain Fj1.

As a result, k + 1 can be represented as the sum of Fj and the Zeckendorf representation of 'a'.

10) If you clearly observe the 8) proof one can conclude that we can get a unique way of representing a positive integer as the sum of the distinct non- consecutive Fibonacci numbers.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.