混凝土数学习题笔记(last update-2014-4-6)

具体数学看了几遍了……但是习题一直没怎么做……感觉这本书习题总是比讲的内容难好多……(虽然讲得也很难
写一下习题题解……供备忘。(以及练习LaTex)
有的题目比较有趣……说不定会抄一下题目描述,供那些没有具体数学的参考……
4.6更新:凑这个坑好难填……能不能在省选彻底滚粗前填好呢……

第一章 递归问题

……暂时放一边……

第二章 和式

1……没人不会做这个吧

2没人不会做这个吧,显然就是x的绝对值

3没人不会做这个吧,第一个是a0+a1+a2+a3+a4+a5,第二个是a0+2a1+2a4(注意k是负数的情况)

[4-9]……没人不会做这个吧

10……这玩意显然就是两种情况推一遍嘛……

笔记……分部求和是用于求和的利器……虽然最近还没在中国的oi题中看到要用这玩意的题目……但是感觉还是很炫酷的。

11.证明分部求和的一般法则……

....证明是很好证的,只是这公式为某些不习惯符号的人提供了方便。

12.证明只要c是一个整数,函数就是所有整数的排列。
证明只要证两点就可以了……
1.不存在不同的整数i,j使得p(i)=p(j)
2.整数x,整数k使p(k)=x。
第1点的证明:
……反证大法好!
假设存在不同整数i,j使p(i)=p(j),那么就有
那么就有
我们注意到,如果i与j同奇偶的话,那么所以推出,与假设矛盾。
然后如果i与j不同奇偶的话,显然|i-j|是一个奇数,
然后只有-2或2两种取值,那么是一个偶数。
所以
所以如果i,j不同奇偶,那么方程p(i)=p(j)无解。
综上不存在不同的整数i,j使得p(i)=p(j)
第2点的证明:
解方程
那么如果x-c是一个偶数,显然k=x-c就是方程的一个解
否则显然x+c是一个奇数,那么k=x+c就是方程的一个解
(写到这里发现这样窝好像也顺便把第一点证明出来了……果然脑洞太大了)

13.利用repertoire method求的封闭形式。
显然这题也没有用成套方法的必要……但是既然题目要求了……
事实上成套方法那一部分我没有好好看过……写这题的时候补习了一下。

下面是笔记。

repertoire method是一种对求解递归式有惊人效果的方法……(事实上我觉得这玩意没啥用)。
大意就是寻找一组已知其解的通用参数,然后弄出可以求解的特殊情形,然后合并得出一般情形。
举个例子……
我们要找的封闭形式
我们考虑一个数列
一般的说,它的解可以写成形式
然后A(n),B(n),C(n)这些代数式都是确定的。
我们考虑的情况,也即的情况。
我们就发现A(n)=1
然后考虑的情况,也即的情况。
我们就发现B(n)=n
然后考虑的情况,也即的情况。
所以,解得
所以我们就解出了A(n),B(n),C(n)
回到原问题……
那么就有
所以
然后大家大概就能明白这玩意是啥了……个人感觉挺扯淡的,所以一直略读跳过。

回到问题……求的封闭形式。
考虑

那么它的通解是
考虑若干个特殊情况……比如最基本的之类的……就能求出若干系数代数式了。
最后B(n)也就是答案求出来是

14将重新改写成多重和式的形式的形式来对它进行运算。
利用分部求和,我们很容易知道
下面考虑用导出这个结果。。。

15用类似方法5得到的封闭形式。
方法5大概意思就是说……将变换为然后求封闭形式。
然后设立方和是S,平方和是R,那么
接下来就是推一推的事情了。
懒得码公式了。

16……没人不会做这个吧

17……没人不会做这个吧

18.……没人不会做这个吧

19.,利用求和因子求解这个递归式。
(这个小学生都能做到的)
我们左右同乘以
那么就得到
所以是一个等比数列……
接下来随便搞搞就可以了。

第二章暂时更新到这里好了……
4月6日继续填
20.利用来推导出的值
做法挺显然的。令那么
21.利用扰动法计算
...不会有人不会做这题吧。
22.证明拉格朗日恒等式:

然后搞出一个对于这个和式弄出个更一般的恒等式:

做法很显然……
因为第二问更一般化一些,解决了第二问,拉格朗日恒等式就证明出来了。
考虑怎么化简第二问的和式。

那么我们将S加倍……
得到

所以就化简掉了……得到了公式:

同时拉格朗日恒等式也得证了。

23.用两种方法计算和式
我比较懒……就只写分部求和这一种方法了……
显然这就是
然后我们知道

那么直接套分部求和公式……

24.计算
继续分部求和搞。

然后套公式得到

25.找类似的性质……比如结合律之类的。

26.化简
先把P平方然后再开根号就能得到

27.计算,并用它推导
显然
然后我们发现
那么
根据差分的基本知识……
我们就能知道

28.指出书中一个证明1=-1的推导错误之处。
书上的错误很逗逼……就是下界没把握好所以挂了。就不抄题目+写题解了。

29.计算和式
...这个初中生都会做的。

然后注意到那个可以让相邻两个求和项互相抵消一部分……
最后就能得出
30.15有四种方式表示成连续的正整数之和:15=7+8=4+5+6=1+2+3+4+5(包含15自身一种方式),求1050有几种方案。
显然就是问有多少公差为1的首项为正整数的有限等差数列中有多少个的总和为1050.
显然确定了首项和末项,这个等差数列就确定了。
我们定义n为首项,m为末项
那么我们就是求解方程的满足的整数解的个数。
我们令x=n+m,y=m-n+1,那么显然x,y奇偶性不同,进一步观察发现只有存在一对奇偶性不同的正整数对(x,y)满足xy=2100,那么就得到了一个解。
所以我们任务转变为了统计有多少对数满足它们奇偶性不同且乘积为2100,稍微思考一下就转变成了统计2100/4=525的约数个数。
答案是12.
31.黎曼zeta函数,显然这是一个无限和式。
证明
并确定的值
就是符号稍微吓人一点。。。推导依旧很简单。

同样的方法可以确定
第二章接下来的几道题目都没什么兴趣做…

第三章 整值函数

暂时放一边。

第四掌 数论

1.暴力手算枚举。
2.因为所以

第五章 二项式系数

主席推荐我先来刷这章习题……(不过我一直觉得这章的超几何变换之类的很鬼畜……感觉习题一定也很可怕)
1.11^4是多少,为什么容易口算?
显然是14641,理由略。

2.当n是正整数时,k取多少最大?
显然是时。
相邻两项作商即可证明。

3.证明六边形性质

暴力展开可以做。不知道有没有更优美的做法。

4.通过反转上指标来计算

又到了笔记时间……第五章的公式比较多……需要记忆的东西比较多……

下面说明什么叫反转上指标:
有这样的恒等式:
在k是整数的时候恒成立。
对于这道题……

5.假设p是一个素数,那么试证明对于0<k<p,我们有,这对二项式系数意味着什么?

因为p是一个素数,k<p,(p-k)<p
所以k!不含p这个质因子,(p-k)!不含p这个质因子,而显然p!含有p这个质因子。
那么显然含有p这个质因子,所以对于0<k<p,我们有
那么再结合
我们可以知道在模p意义下……是1,p-1,1,p-1,...交替出现的。

6.第五章第二节的问题6给出的错误推导错在哪里,试修正之(其实就是让你自己推一遍233)。
(问题6:给出的封闭形式)
先简化两个二项式的乘积……
然后去掉k+1这个分母……
...然后利用对称性去掉第一个二项式系数下指标的k……再套二项式系数相乘的公式就可以了。。。

也就是
然后书里面的推导就是这里出了错误……
书里的推导是
事实上只有在k是[0,n]之间的正整数之间的时候……才能断言
而书里面的推导中的和式可能会引入k=-1的情况……所以就跪了。
修正之后得到封闭形式是

7.考虑公式,在k<0的时候是否成立。
成立的……用类似证明的情况时的方法就可以证明出来了,当然也可以结合下降幂的一些公式直接推导,这样更简洁。

8.计算,当n 非常大的时候,这个和式的近似值是什么?
……这是刷混凝土数学以来第一道能让我搞半小时以上的题目……这题的级别还只是一道“热身题”……
首先先不想近似值……我们看这个和式的封闭形式能不能搞出来。

笔记:高阶差分以及牛顿级数等

我当时看书的时候略读了导致这题yy不出……
首先一个函数u(x)的(一阶)差分就是
那么函数u(x)的二阶差分就就是一阶差分的差分:
对于u(x)的n阶差分……有公式:
还是比较显然的。
对于d次多项式
那么它在d次差分之后,会变为一个常数。
它在d次以上差分后,会变成0。
这个非常显然,考虑我们怎么得到这个多项式在差分d次之后变成的常数。
我们引入牛顿级数的概念:

就是用二项式系数的倍数的和来表示一个多项式,显然这样子是一定可行的。
然后我们注意到就是d次差分之后得到的常数,而显然

接下来回到这题……
我们化简求和式……发现
那么就有函数
这个和式就是
显然f(x)是一个多项式,它的最高次项是
所以n次差分之后得到的常数就是
所以我们得到了封闭形式……

所以我们根据斯特林近似之类的东西搞一下……
就能发现这玩意在n趋向无限大的时候是

8.关于广义指数级数的……暂时跳过

9.关于超几何函数的……暂时跳过

10.关于超几何级数的……暂时跳过

11.关于超几何级数的……暂时跳过

12.关于超几何级数的……暂时跳过

13.用反转上指标以及范德蒙特卷积的方法证明恒等式

笔记:范德蒙特卷积

就是公式

对于这题接下来趴在地上想一想就能用数学归纳法推了,只要用加法公式就够了。
然后怎么用范德蒙特卷积……

注意
然后约去
就可以直接套范德蒙特卷积了。

第六章 特殊的数

暂时放一边

第七章 生成函数

暂时放一边

第八章 离散概率

暂时放一边

Comments

comments powered by Disqus