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
Math Forum Home || Math Library || Quick Reference || Math Forum Search