13
- 章节名:13
1.7题其实并不难,注意到
($$ 2^{100} = \left( 2^{4} \right)^{25} \equiv 1^{25} \left( \mod 5 \right) $$)即可. 那么这个是怎么注意到的呢?其实除非有很高的数字感觉,其实一下是感觉不到的.... 核心在于同余式具有一个性质:
($$ a \equiv b \left( \mod m \right) \Rightarrow a^{k} \equiv b^{k} \left( \mod m \right) $$)利用这个式子就可以把2^100的求模转化成一个较小容易计算的数的求模。反复几次就可以得到结果。 1.8的(a)其实是是建立在F0 = 1, F1 = 1, F2=2...的基础上的.....所以在证明的时候会觉得这个式子不对。 而在现在数学通用的表达是F0 = 0, F1 = 1, F2 = 1...F0称为第零项。 相应的,要证明的式子应该改成
($$ \sum_{i=1}^{N-2} F_{i} = F_{N} - 1 $$)证明这个式子最简单实用数学归纳法(事实上,solution manual给出的就是MI)。但是用MI会晤从小的这个式子的来历,这个时候就需要用另外一种方式去证明。 证明也比较简单,只需要逆向迭代即可: ($ F_{N} = F_{N-1} + F_{N-2} $) ($F_{N} = F_{N-2} + F_{N-2} + F_{N-3}$) ($F_{N} = F_{N-2} + F_{N-3} + F_{N-3}+F_{N-4}$) ($\cdots$) ($F_{N} = F_{N-2} + F_{N-3} + F_{N-4}+\cdots + F_{2}+F_{2}+F_{1}$) 很容易看出,右边其实是多了F2。而在书上的定义中,F2=2,所以减去2;而我们定义的F2=1,所以减去1。 第三小题的解法应该是烂大街了,几乎任何一本有点名气的离散数学/组合数学一类的书都会有。甚至还可以利用初等代数和高等代数的方法求解。 最一般的解法无法是借助generating function,从Fn - Fn-1 - Fn-2 = 0导出 q^n - q^n-1 - q^n-2 = 0,然后得出特征方程 X^2 - x - 1 =0,得出两个一般解,在利用F1和F0联立求解出常系数C1 C2。
说明 · · · · · ·
表示其中内容是对原文的摘抄