Question

對(duì)于每個(gè)正整數(shù)n，將n表示成2的非負(fù)整數(shù)次方的和，令f(n)為正整數(shù)n的不同表示法的個(gè)數(shù)．

如果兩個(gè)表示法的差別僅在于它們中各個(gè)數(shù)相加的次序不同，這兩個(gè)表示法就被視為是相同的．例如，f(4)＝4，因?yàn)?恰有下列四種表示法：4；2＋2；2＋1＋1；1＋1＋1＋1．

Answer 1

證明：對(duì)于任意一個(gè)大于1的奇數(shù)n＝2k＋1，n的任一表示中必含一個(gè)1．去掉這個(gè)1就得到2k的一個(gè)表示．反之，給2k的任一表示加上一個(gè)1就得到2k＋1的一個(gè)表示．這顯然是2k＋1和2k的表示之間的一個(gè)一一對(duì)應(yīng)．從而有如下遞歸式：

f(2k＋1)＝f(2k)                                (1)

對(duì)于任意正偶數(shù)n＝2k，其表示可以分為兩類：含有1的與不含1的．對(duì)于前者，去掉一個(gè)1就得到2k－1的一個(gè)表示；對(duì)于后者，將每一項(xiàng)除以2，就得到k的一個(gè)表示．這兩種變換都是可逆的，從而都是一一對(duì)應(yīng)．于是得到第二個(gè)遞歸式：

f(2k)＝f(2k－1)＋f(k)                       (2)

(1)、(2)式對(duì)于任意k≥1都成立．顯然f(1)＝1．定義f(0)＝1，則(1)式對(duì)于k＝0也成立．根據(jù)(1)、(2)式，函數(shù)f是不減的．

由(1)式，可以將(2)式中的f(2k－1)換成f(2k－2)，得到f(2k)－f(2k－2)＝f(k)，k＝1，2，3，…，給定任一正整數(shù)n≥1，將上式對(duì)于k＝1，2，…，n求和，得到

f(2n)＝f(0)＋f(1)＋…＋f(n)，n＝1，2，3，…(3)

下面先證明上界，在(3)式中，右端所有的項(xiàng)都不大于最后一項(xiàng)，對(duì)于n≥2，2＝f(2)≤f(n)．于是有

f(2n)＝2＋(f(2)＋…＋f(n))≤2＋(n－1)f(n)

≤f(n)＋(n－1)f(n)＝nf(n)

n＝2，3，4，…從而得到

f(2ⁿ)≤2^n－1?f(2^n－1)≤2^n－1?2^n－2?f(2^n－1)

≤2^n－1?2^n－2?2^n－3?f(2^n－3)≤…

≤2^{(n－1)＋(n－2)＋…＋1}?f(2)＝2^n(n－1)/2?2

為了證明下界，我們先證明對(duì)于具有相同奇偶性的正整數(shù)b≥a≥0，有如下不等式成立：

f(b＋1)－f(b)≥f(a＋1)－f(a)                           (4)

事實(shí)上，如果a、b同為偶數(shù)，則由(1)式知上式兩端均等于0．而當(dāng)a、b同為奇數(shù)時(shí)，由(2)式知f(b＋1)－f(b)＝f(b＋1)/2)，f(a＋1)－f(a)＝f((a＋1)/2)．由函數(shù)f是不減的即得不等式(4)成立．

任取正整數(shù)r≥k≥1，其中r為偶數(shù)，在(4)式中依次令a＝r－j，b＝r＋j，j＝0，1，…，k－1．然后將這些不等式加起來(lái)，得到

f(r＋k)－f(r)≥f(r＋1)－f(r－k＋1)

因?yàn)閞是偶數(shù)，所以f(r＋1)＝f(r)．從而

f(r＋k)＋f(r－k＋1)≥2f(r)，k＝1，…，r

對(duì)于k＝1，…，r，將上述不等式相加，即得

f(1)＋f(2)＋…＋f(2r)≥2rf(r)

根據(jù)(3)式，上式左端等于f(4r)－1．從而對(duì)于任意偶數(shù)r≥2，f(4r)＞2rf(r)＋1＞2rf(r)．取r＝2^m－2即得

f(2^m)≥2^m－1f(2^m－2)                                     (5)

要使r＝2^m－2為偶數(shù)，m須為大于2的整數(shù)，但是(5)式對(duì)于m＝2也成立．

因此對(duì)一切n≥2下界成立．