定义f(n)的值为将n拆分成若干个2的幂的和，且其中每个数字出现的次数不会超过两次的方案数。规定f(0)=1。
    例如，有5种合法的方案可以拆分数字10：1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 和 2+8。因此，f(10)=5。
    请用一句最简单的话来描述集合{ f(n)/f(n-1) }。证明你的结论。

    注意：答案远比一个递归公式来得精辟，来得巧妙。如果你发现了我们的结论，你会一眼认定它为正确答案。

    答案：数列{ f(n)/f(n-1) }以最简形式包含了所有的正有理数。

    如果n是奇数（等于2m+1），那么数字1（即2^0）必须出现且只能出现一次。现在的问题就是，2m的拆分方案中有多少个方案不含数字1呢？稍作思考你会立即发现，它就等于f(m)，因为m的所有拆分方案的所有数都乘以2后正好与不含1的2m拆分方案一一对应。因此，f(2m+1) = f(m)
    如果n是偶数（等于2m），那么数字1要么没有出现，要么恰好出现两次。对于前一种情况，我们有f(m)种可能的方案；第二种情况则有f(m-1)种方案。因此，f(2m) = f(m) + f(m-1)
    另外，显然f(k)都是正数。于是，f(2k-1) = f(k-1) < f(k-1)+f(k) = f(2k)
    这样，我们可以得到以下三个结论：

    结论1：gcd( f(n),f(n-1) ) = 1
    证明：对n进行数学归纳。显然gcd( f(1),f(0) ) = gcd(1,1) = 1
    假设对于所有小于n的数结论都成立。根据n的奇偶性，下面两式中必有一个成立：
    gcd( f(n),f(n-1) ) = gcd( f(2m+1),f(2m) ) = gcd( f(m), f(m)+f(m-1) ) = gcd( f(m),f(m-1) ) = 1
    gcd( f(n),f(n-1) ) = gcd( f(2m),f(2m-1) ) = gcd( f(m)+f(m-1), f(m-1) ) = gcd( f(m),f(m-1) ) = 1

    结论2：如果f(n+1)/f(n) = f(n'+1)/f(n')，那么n=n'
    证明：还是数学归纳法。当max(n,n')=0时结论显然成立，因为此时n=n'=0。
    假如对于所有小于n的数结论都成立。由于f(2k-1)<f(2k)，那么要想f(n)/f(n-1) = f(n')/f(n'-1)，n与n'的奇偶性必须相同，于是可以推出f(m)/f(m-1) = f(m')/f(m'-1)，根据归纳我们有m=m'，这就告诉我们n=n'。

    结论3：对于任何一个有理数r，总存在一个正整数n使得r=f(n)/f(n-1)。
    证明：把r写成两个互素的数p和q的比。我们对max(p,q)施归纳。
    显然，当p=q=1时结论成立，此时n=1。
    不妨设p<q，那么定义r'为p/(q-p)。根据归纳假设，总存在一个数m满足r'=f(m)/f(m-1)。于是r=f(2m+1)/f(2m)。当p>q时同理可证明。

做人要厚道
转贴请注明出处