具体数学第一章

具体数学都买了好久了，买的第一本英文版的书，可以一直没有看下去，看了N次还是第一章。现在刚好有同学一起看这本书，就打算从头开始好好的看一遍，然后把每一章的Homeword Exercises都做了，顺便再博客里面写下来，这次希望有人一起看的情况下，把这本书好好的看完一次。

第一章作者用几个例子来讲述递归式，第一个是汉诺塔，第二个是N条直线可以把平面最多分成多少个区域，第三个是Josephus Problem.这里面在汉诺塔的时候，通过T[n]<=2T[n-1]+1 & T[n]>=2T[n-1]+1从而得到T[n]=2T[n-1]+1.其中第一个是足够性，即T[n]在最多2T[n-1]+1步中一定可以做完(首先你把上面的N-1个移到第2个柱子上，然后把第N个移到第3个柱子上，最后再把第2个柱子上的移到第3个柱子上)，T[n]>=2*T[n-1]+1则是必须性，(在你移动第N个的时候，那么上面的N-1个一定在第2个柱子上，这里至少需要T[n]次,然后移动第N个需要1次，另外把第2个柱子上的移动到第3个柱子上至少需要T[n-1]次)。

第二个问题，就讲了一下一个扩展，就是每条直线变成了两条共起点射线，然后问最多分成多少个区域，这个问题，可以先延长是的变成2*n条直线，最后再减去多出的部分就行了

第三个问题，主要讲述了repertoire method,对于书上的一开始没看懂，对于没看懂的同学可以借鉴下这里

Concrete Mathematics Repertoire Method和repertoire。我的想法就是这个方法就是确定α,β,γ和A[n],B[n],C[n]无关，当然这个你可以证明出来是无关的，不过关键是你在毫不知情的时候想到这个。知道这些无关之后，那么你就可以另f[n]=某些特定的值，那样的话，α,β,γ会得到特定的值(α,β,γ组和f[n]是对应的)，然后你就可以得到A[n],B[n],C[n]的。最后就得到一个通式了。接下来可能还会把做的习题以文章的形式写出来。

表示好久都没看书了，看这书看的好慢啊！！！