Sum of Distinct Fibonacci NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/