Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
College Number Theory
High School Fibonacci Sequence/Golden Ratio
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/