IBM Ponder This #112 · August 2007

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.
For example, f(10)=5 since there are five different ways to express 10: 1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8.
Describe, in a single sentence, the multiset {f(n)/f(n-1)} for positive integer n.
Show your proof to this sentence.

As usual, we ask that you only submit your original work.

UPDATE, 8/2/07: The solution is more elegant than just a recursion formula. You'll recognize it once you find it.

Solution

Best opened after a real attempt

To be added.