Solving Nonconsecutive Fibonacci Challenges

[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.

 

[Robokapp]

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.

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

1, 1, 2, 3, 5, 8, 13, 21, 34[/color], 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 can't 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 don't know if it's useful.

 

[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...

 

[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 ). 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.

 

[Robokapp]

My math teacher said that if you can put the sum in the form of an equation that doesn't 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!

 

[CRGreathouse]

My math teacher said that if you can put the sum in the form of an equation that doesn't 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!

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)$$