# Fibonacci sums

1. Sep 11, 2006

### zhx_haq

i need help with finding out how to solve the following:

Express the following natural numbers as a sum of distinct, nonconsecutive Fibonacci numbers: 52, 143, 13, 88.

:yuck:

2. Sep 12, 2006

### Robokapp

i'd write out a little of the sequence obviously.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

so if we pick 34...we have a leftover of 18. 18 can be made by adding 5 and 13.

13 is easy...just 5 and 8...

143...we cant use 144 so we pick randomly 89 for being largest.
143-89=54... so we form a 54 out of 34, 13, 5 and 2.
so 143 = 89+34+13+5+2
And 88 is just 88=55+21+8+3+1

but that's not mathematics that's actually doing it. So I dont know if it's useful.

3. Sep 12, 2006

### mtanti

Had the fibonacci sequence been a series of super increasing numbers (the next number in the list is greater than the sum of all numbers behind it) than this question would have made more sense as all you do is subtract the target number by the largest number in the series which is less than the target number... But appearantly you have to do it by brute force...

4. Sep 12, 2006

### CRGreathouse

I'd use a greedy algorithm. Take the largest number that fits, and continue down the line, backing up when needed. For 143:
89 <= 143 < 144, so choose 89. 143 - 89 = 54.
Since you chose 89 the next one must be at most 34 (skipping 55), so choose that. 54 - 34 = 20.
Likewise, you must choose at most 13 (skipping 21), so choose that. 20 - 13 = 7.
You must choose at most 5 (skipping 8), so choose that. 7 - 5 = 2.
Since 2 is a Fibonacci number not next to 5, choosing that solves this problem.

I did some programming with a similar problem recently (calculating a b-file for Sloane's http://www.research.att.com/~njas/sequences/A013583 [Broken]). It's actually not a hard problem; I was able to find all the ways to make Fibonacci numbers sum to each integer < 100,000 in something like 2 seconds.

Last edited by a moderator: May 2, 2017
5. Sep 13, 2006

### Robokapp

My math teacher said that if you can put the sum in the form of an equation that doesnt take the previews term to find the next...like a function...you'd get rich and you'd never have to work again. So good luck!

6. Sep 13, 2006

### CRGreathouse

Which sum, the Fibonacci numbers? That's not hard.

$$F_n=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}$$

Finding an explicit formula for the number of ways to sum to a particular number using Fibonacci numbers is harder, but Sloane's list has this:
$$\frac1n\sum^n_{k=1}\left(a(n-k)\sum_{f\mid k} (-1)^{k/f+1}\cdot f\right)$$

Last edited: Sep 13, 2006