IBM Ponder This August 2007

[pzhon]

I thought this month's IBM Ponder This challenge was interesting.

<ul type="square">
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 sequence {f(n)/f(n-1)} for positive integer n.
Show your proof to this sentence.[/list]
I believe in this problem, {n} means floor(n), the greatest integer less than or equal to n.

Here are the first few values of f(n), obtained by multiplying a(x)a(x^2)a(x^4)... where a(x) = (1+x+x^2):

0: 1
1: 1
2: 2
3: 1
4: 3
5: 2
6: 3
7: 1
8: 4
9: 3
10: 5
11: 2
12: 5
13: 3
14: 4
15: 1
16: 5
17: 4
18: 7
19: 3
20: 8
21: 5
22: 7
23: 2
24: 7
25: 5