Write a Number as a Fibonacci Sum
GolfScript, 54 characters
~1.{3$)<}{.@+}/<[[]]{{+}+1$%+}@/\{~)+{+}*!}+,{'+'*n.}/
Test it online or have a look at the examples:
> 54
2+5+13+34
> 55
1+2+5+13+34
3+5+13+34
8+13+34
21+34
55
Ruby, 118 114 (array output) or 138 134 (correct output)
i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
p (1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}
Sample run:
c:\a\ruby>fibadd
100
[[3, 8, 89], [1, 2, 8, 89], [3, 8, 34, 55], [1, 2, 3, 5, 89], [1, 2, 8, 34, 55], [3, 8, 13, 21, 55], [1, 2, 3, 5, 34, 55], [1, 2, 8, 13, 21, 55], [1, 2, 3, 5, 13, 21, 55]]
Change gets to $*[0] if you want command line arguments (>fibadd 100), +1 character though.
With the correct output:
i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
$><<(1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}.map{|o|o*?+}*'
'
Sample runs:
c:\a\ruby>fibadd
100
3+8+89
1+2+8+89
3+8+34+55
1+2+3+5+89
1+2+8+34+55
3+8+13+21+55
1+2+3+5+34+55
1+2+8+13+21+55
1+2+3+5+13+21+55
c:\a\ruby>fibadd
1000
13+987
5+8+987
13+377+610
2+3+8+987
5+8+377+610
13+144+233+610
2+3+8+377+610
5+8+144+233+610
13+55+89+233+610
2+3+8+144+233+610
5+8+55+89+233+610
13+21+34+89+233+610
2+3+8+55+89+233+610
5+8+21+34+89+233+610
2+3+8+21+34+89+233+610
c:\a\ruby>obfcaps
12804
2+5+21+233+1597+10946
2+5+8+13+233+1597+10946
2+5+21+89+144+1597+10946
2+5+21+233+610+987+10946
2+5+21+233+1597+4181+6765
2+5+8+13+89+144+1597+10946
2+5+8+13+233+610+987+10946
2+5+8+13+233+1597+4181+6765
2+5+21+34+55+144+1597+10946
2+5+21+89+144+610+987+10946
2+5+21+89+144+1597+4181+6765
2+5+21+233+610+987+4181+6765
2+5+8+13+34+55+144+1597+10946
2+5+8+13+89+144+610+987+10946
2+5+8+13+89+144+1597+4181+6765
2+5+8+13+233+610+987+4181+6765
2+5+21+34+55+144+610+987+10946
2+5+21+34+55+144+1597+4181+6765
2+5+21+89+144+233+377+987+10946
2+5+21+89+144+610+987+4181+6765
2+5+21+233+610+987+1597+2584+6765
2+5+8+13+34+55+144+610+987+10946
2+5+8+13+34+55+144+1597+4181+6765
2+5+8+13+89+144+233+377+987+10946
2+5+8+13+89+144+610+987+4181+6765
2+5+8+13+233+610+987+1597+2584+6765
2+5+21+34+55+144+233+377+987+10946
2+5+21+34+55+144+610+987+4181+6765
2+5+21+89+144+233+377+987+4181+6765
2+5+21+89+144+610+987+1597+2584+6765
2+5+8+13+34+55+144+233+377+987+10946
2+5+8+13+34+55+144+610+987+4181+6765
2+5+8+13+89+144+233+377+987+4181+6765
2+5+8+13+89+144+610+987+1597+2584+6765
2+5+21+34+55+144+233+377+987+4181+6765
2+5+21+34+55+144+610+987+1597+2584+6765
2+5+21+89+144+233+377+987+1597+2584+6765
2+5+8+13+34+55+144+233+377+987+4181+6765
2+5+8+13+34+55+144+610+987+1597+2584+6765
2+5+8+13+89+144+233+377+987+1597+2584+6765
2+5+21+34+55+144+233+377+987+1597+2584+6765
2+5+8+13+34+55+144+233+377+987+1597+2584+6765
That last one (12804) only took about 3 seconds!
Mathematica, 89 85 chars
Shortened to 85 chars thanks to David Carraher.
i=Input[];#~Row~"+"&/@Select[If[#>i,Subsets@{##},#0[#+#2,##]]&[2,1],Tr@#==i&]//Column
Mathematica has a built-in function Fibonacci, but I don't want to use it.