Sum of Distinct Fibonacci Numbers

Date: 05/06/2001 at 22:10:05
From: Sam
Subject: Fibonacci numbers

How do you show that every positive integer is a sum of distinct terms 
of the Fibonacci sequence?

Date: 05/07/2001 at 09:48:27
From: Doctor Floor
Subject: Re: Fibonacci numbers

Hi Sam, thanks for writing.

We can even prove a slightly better theorem: that each number can be 
written as the sum of a number of nonconsecutive Fibonacci numbers. We 
prove it by (strong) mathematical induction.

1. The statement is clearly true for n = 1, 2, and 3 since 1 = F_1, 
   2 = F_3, and 3 = F_4, which we may consider as single term sums.

2. Suppose that the statement is true for all n <= m (this is the 
   induction hypothesis for strong induction, while n = m is used for 
   standard induction). We will prove that the statement is true for 
   n = m+1.

   If m+1 = F_t for some t, then it is trivially correct. In other 
   cases we find the t such that F_t < m+1 < F_{t+1}.

   Let q = m+1-F_t; then we can write q as sum of nonconsecutive 
   Fibonacci numbers according to the induction hypothesis. We also 
   note that this sum does not contain F_{t-1} because:

        q = m+1-F_t < F_{t+1} - F_t = F_{t-1}

   So if we add F_t to the sum of nonconsecutive Fibonacci numbers for 
   q, we have such a sum for m+1 as well. And the statement is true 
   for n = m+1.

If you need more help, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/