具体数学第一章习题

对于《具体数学》的所有问题，欢迎邮件联系讨论 Email:qcx978132955#gmail.com

上一篇已经写了第一章大致的内容，这里写一下第一章的Homework Exercises的习题简单分析，有些是参考了后面的习题解答。

8.可以自己推出Q[0],Q[1],Q[2],Q[3],Q[4],Q[5],Q[6],然后就可以看到循环了。

9. a)直接把x[n]=(x[1]+…x[n-1])/(n-1)代入两边，然后化简之后就可以得到P[n-1]了

b)x[1]…x[n]<=((x[1]+…x[n])/n*(x[n+1]+…x[2n])/n)^2n
<=((x[1]+…+x[2n])/2n)^2n ====>这里用到了P[2]

c)不是很懂，一开始以为不能用a)的那个式子，后来找了好多加看了习题解貌似是承认a)中的那个式子的，对于a)中的那个其实是成立的，只不过a)中给出来，让我们更好证明一些(对于a中的证明，我们需要考虑的是x[1]*…x[n-1]<=((x[1]+…+x[n-1]/(n-1))^(n-1) 首先我们知道P[n]是对x[n]为任意数成立的，那么我们就可以设x[n]=(x[1]+…+x[n-1])/(n-1)，然后就证明了)然后P[2]->P[4], P[4]->P[3],P[3]P[2]->P[5],依次类推，就可以知道所有的P[n]都成立。

10.照着前面汉诺塔的模式推导就OK了

11.a)假设最后所需的是T[n]，那么T[n]=T[n-1]+2+T[n-1]{首先把上面2n-2个放到第2个柱子上，然后把最下面两个放到第3个柱子上，因为不用考虑顺序，所以这样放就行了，最后把第2个柱子上的2n-2个移到第3个柱子上就行了}，最后得到T[n]=2^(n+1)+2
b)假设最后所需要的是S[n],首先我们从a)中可以知道如下一个结论，也就是在a)的规则中，最后只有最下面两个是互换顺寻的，上面的n-1对中，相同大小的Hanoi是没有换位置的(移了2次，第一次之后换了位置，然后第二次又换回来了).那么我们就可以的得到S[n]=T[n-1]+2+T[n-1]+2+Sn-1。

12可以由11.a)扩展得到 如果所有的m[k]>0,那么A(m[1],…m[n])=A(m[1],…,m[n-1])+m[n],另外如果最后顺序不能颠倒的话用B(m[1],…m[n])表示，那么最后B(m[1],…m[n])的表达式为
{ A(m[1],….m[n]) if m[n]=1
B(m[1],…m[n]) = { 2m[n]-1 if n=1
{ 2A(m[1],…m[n-1])+2*m[n]+B(m[1],…m[n-1]) if n>1 & m[n]>1

13.照着书上给的那个射线的样子分析就行了，这里在ZZ[n-1]的情况下，然后考虑加入第n条ZZ线，可以知道只有让第n条ZZ线的3条”线”和前面的n-1条ZZ线都相交这样得到的区域最多，然后第n条ZZ线自己可以多出几个区域(因为是ZZ型的，注意拐角两边的区域是同一个区域，不要多算了)，这样就得到一个通式ZZ[n]=ZZ[n-1]+9*n-8

14.这个最后得到1维是C(n,0)+C(n,1) 2维是C(n,0)+C(n,1)+C(n,2) 3维是C(n,0)+C(n,1)+C(n,2)+C(n,3)

15.可以照着书上第15页那个展开式来写，这样的话只要考虑最后I[n]中n必须大于1，I(1)没有意义。另外可以按照书上Josephus Problem最开始的解法那样，写出递推式,然后可以解出来或者写出1-16(上限大一点好看规律，当然这也可以退出来)。然后可以得到最后的I(32^n+l)=2l+1 其中m>=0 & 0<=l<3*2^m && I(2) = 2

16.由repertoire method我们可以假设g[n]=αA[n]+β[0]B[n]+β[1]C[n]+γD[n].但是我一直只能找到两个式子，g[n]=1和g[n]=2这两个式子会得到 A[n]-2B[n]-2C[n]=1 & A[n]+C[n]-D[n]=n，但是当我去解g[n]=n^2或者g[n]=1/n等其他的时候总是得到一些矛盾的东西，后来看了书后的解答，可以没有看出其中的奥秘，然后在网上各种搜题解，看到这里和这里,才发现自己对那个repertoire method还是没有完全了解，照着上面给的两个链接我们可以得到最后的结果。

继续加油，好好努力，天天向上。