算法引论 笔记4
30 Jul 2013 by LelouchHe
说明
本篇是第二章的习题解答(好多题目..好难..)
2.1
| $n = 1, x ^ n - y ^ n = x - y | x - y$,归纳基础成立 |
-
假设$k < n$时成立,即$x ^ k - y ^ k x - y$ - 当$k = n$时, \(x ^ n - y ^ n = x (x ^ {n - 1} - y ^ {n - 1}) + y (x ^ {n - 1} - y ^ {n - 1}) + x y (x ^ {n - 2} - y ^ {n - 2})\) 因为等式右边均可以被$x - y$整除(规矩归纳假设),所以左边亦可被证书
- 命题成立
ps:
一开始我陷入的误区是没有让归纳假设发挥最大作用.第2步我一开始是这样的变换:
\[x ^ n - y ^ n = x (x ^ {n - 1} - y ^ {n - 1}) + y ^ {n - 1} (x - y) = (x - y)(m x + y ^ {n - 1})\]其中利用归纳假设,设$x ^ {n - 1} - y ^ {n - 1} = m (x - y), m \in Z+$.这样等式右边就是一个可以整除x-y的数,从而证明假设.
这个结论应该是错的,因为题目上说x/y为任意数.有可能x-y为整,但x/y却不是,这样等式右边就不一定是整数了,显然就无法整除.出现这样问题的原因在于1,畏惧变换,只肯变一步就不动了,就想得结论;2,没有将题目的约束想仔细;3,结论分析的模棱两可,当时证明时我就说不清为啥右边是整除,结果确实也不是
连自己都没法说服的证明,肯定不是好证明
2.2
猜测$S _ n = \frac{n (n + 1)}{2} c _ 1 + n c _ 2$
$n = 1, S _ 1 = c _ 1 + c _ 2$,归纳基础成立
- 假设$k < n$成立,即$S _ k = \sum _ {i = 1} ^ {k} a _ i = \frac{k (k + 1)}{2} c _ 1 + k c _ 2$
- 当$k = n$时, \(S _ n = \sum _ {i = 1} ^ {n} a _ i = \sum _ {i = 1} ^ {n - 1} a _ i + a _ n = [\frac{(n - 1) n}{2} c _ 1 + (n - 1) c _ 2] + (n c _ 1 + c _ 2) = \frac{n (n + 1)}{2} c _ 1 + n c _ 2\) 假设成立
- 命题成立
ps:
本题其实可以很简单的分别相加两个部分,就能看出答案是多少.这样复杂的操作主要是为了练习归纳法
2.3
试着对式子进行一些变形
\[S _ n = \sum _ {i = 1} ^ {n} i (i + 1) = \sum _ {i = 1} ^ {n} i ^ 2 + \sum _ {i = 1} ^ {n} i\]等式右边的两个式子中,第二个和式是简单的,第一个和式不知道具体结果,需要继续求解(好吧,其实也知道..)
假设$T _ n = \sum _ {i = 1} ^ {n} i ^ 2 = a n ^ 3 + b n ^ 2 + c n + d$(二次方求和设为三次方式,是很合理的),然后尝试1/2/3/4的具体值来求解(4个),得到$T _ n = \frac{n (n + 1) (2 n + 1)}{6}$
假设对于1/2/3/4显然成立(就是从这里得到的式子),归纳基础成立
- 假设$k \le n$成立,即$T _ k = \frac{k (k + 1) (2 k + 1)}{6}$
- 当$k = n + 1$时, \(T _ {n + 1} = \sum _ {i = 1} ^ {n + 1} = T _ n + (n + 1) ^ 2 = \frac{(n + 1) (n + 2) (2 n + 3)}{6}\) 满足假设条件
- 命题成立
2.4
这是等比数列,$S _ n = \sum _ {i = 1} ^ {n} 1 / {2 ^ i} = 1 - 1 / {2 ^ n}$
$n = 1$时,归纳基础成立
- 假设$k \le n$时成立,即$S _ k = 1 - 1 / {2 ^ k}$
- 当$k = n + 1$时,有 \(S _ {n + 1} = \sum _ {i = 1} ^ {n + 1} 1 / {2 ^ i} = S _ n + \frac{1}{2 ^ {n + 1}} = 1 - \frac{1}{2 ^ {n + 1}}\) 满足假设条件
- 命题成立
2.5
这个问题在2.4已经证明
2.6
假设$S _ n = \sum _ {i = 1} ^ {n} (-1) ^ {n - 1} n ^ 2 = (-1) ^ {n - 1} \frac{n (n + 1)}{2}$
$n = 1, n = 2$时假设成立,归纳基础成立
- 假设$k \le n$时成立
- 当$k = n + 1$时,有 \(S _ {n + 1} = S _ n + (-1) ^ n (n + 1) ^ 2 = (-1) ^ n \frac{(n + 1) (n + 2)}{2}\) 满足假设条件
- 命题成立
ps:
变形的时候,需要持续不断的关注已知(纯已知和n归纳假设)和未知(n+1归纳假设)
一开始的时候,试图从n的奇偶性入手解决.当然,这肯定是一个方法,但更好的方式是先入手了解问题,然后在需要的时候再引入分类讨论.类似本题,入手了解后,就完全不需要分类了
2.7
这个问题比较怪,并不像之前看到的那些纯数学问题了.相反,以类似构造的方式,来解决,而不是证明问题,往往是合理的步骤
先将问题形式化下(要不然怎么能贴在博客上啊).设$(n + 1, 2 n)$表示从前$2 n$个正整数任取$n + 1$满足条件的取法的集合
$n = 1$时成立,即$(2, 2)$不为空
- 假设$k < n$时成立,即$(k + 1, 2 k)$不为空
- 当$k = n$时,问题的求解就是$(n + 1, 2 n)$不为空即可.凭空构造解法肯定是比较难的(大家可以试试,不考虑前后联系生做数据,反正我是弄了很久也没弄出来),而且也不是归纳法的应用.归纳法着眼于怎么归纳到1中的假设.自然的想法是去掉一个数字,谁呢?很自然的,应该想到1,1是特殊的数,只要$1 \in (n + 1, 2 n)$,那么命题是必然成立的.所以我们需要讨论的是$1 \notin (n + 1, 2 n)$.删除了1之后,就剩下2n-1个数字,我们的问题变成了$(n + 1, 2 n - 1)$,和n-1归纳假设相差1,那么我们还需要删除1个数字.自然的,想到的肯定是非常特殊的2了,因为只要有2和另外一个偶数,那么命题就肯定成立.在剩下的2n-1个数中,有n个偶数和n-1个奇数,如果$2 \in (n + 1, 2 n - 1)$,那么剩下的n个数字中,必然会有一个偶数(因为只有n-1个奇数了),所以如果取出了2,命题就会成立.这样,我们只用处理没有2的情况了.现在问题成了$(n + 1, 2 n - 2)$,比较n-1归纳假设$(n, 2 n - 2)$,很容易发现,如果取n个数字的方法有了,则必然有取n+1的方法(再任取一个数字即可),所以此处可以利用归纳假设证明
- 证明过程中,我们总共删除了2个数字,因此原先n=1就不完全是归纳假设了,还需要包括n=2的情况(这个自然也是成立的)
- 命题成立
ps:
从这个问题可以看到如果利用归纳假设来推导结论.有些时候不一定能直观的看到归纳的步骤,此时要做的不是灰心,而是一步一步的慢慢推导,向着归纳假设的方向努力,然后适时的调整结论和步骤.一次不行就多次归纳.
另一个问题是归纳基础的覆盖范围必须是全面的,比如此例中,只有n=1的情况,就无法推导证明n=2k的结论了,所以必须把n=2加上.虽然此处是trival的,但对于某些问题,归纳基础也是证明的关键一步
2.8
n = 1时成立,归纳基础成立
- 假设$k \le n$时成立,即$2 ^ {k - 1}(a ^ k + b ^ k) \ge (a + b) ^ k$
- 当k=n+1时,尝试证明$2 ^ n (a ^ {n + 1} + b ^ {n + 1}) \ge (a + b) ^ {n + 1}$.我们从等式的右边入手,看看如何能得到左边 \((a + b) ^ {n + 1} = (a + b) (a + b) ^ n \le (a + b) 2 ^ {n - 1} (a ^ n + b ^ n) = 2 ^ n (a ^ {n + 1} + b ^ {n + 1}) - 2 ^ {n - 1}(a ^ n - b ^ n)(a - b) \le 2 ^ n (a ^ {n + 1} + b ^ {n + 1})\) 观察最后一步待证式,只要能证明$2 ^ {n - 1}(a ^ n - b ^ n)(a - b) \ge 0$,就可以证明假设,而这个是很显然成立的,所以归纳假设成立
- 命题成立
ps:
这个问题的误区就大了.看到题目,本能的想到平均数问题了,于是就开始利用逆向归纳来证明.先是证明了2的幂次方都成立,然后再反推,结果是怎么都推不出来(我估计是可以的).而且一开始的预处理也不同,由于想着平均数问题,我就果断的把$2 ^ n$除到等式右边(恩,很像那道原题了吧),然后从等式左边强攻
其实,这里可以说明一个道理,解决问题的方向.这个题目等式左右都有n,而且还没有办法化简变成上面那些题的样子(即只有一边存在变量,另一边是值).此时,就要思考方向了:是从左边还是右边?就普遍而言,能进行变换的一边是首选的方向.能变换,而不是最简单,应该是一个关键性质,比如本题,左边比右边复杂,而且左边没法变,除非用次方和公式(?有么?),而右边则是和的次方比较好动手.就算左边更简单,也要首先尝试右边,因为解决问题是要变换归纳的,动的性质,远远比静的性质要好.
2.9
这个问题其实可以不利用归纳来解.
设各个位数字和$S _ n = \sum _ {i = 1} ^ {n} c _ i$, 该数为$N _ n = \sum _ {i = 1} ^ {n} 10 ^ i c _ i$.二式相减,$N _ n - S _ n = \sum _ {i = 1} ^ {n} (10 ^ i - 1) c _ i$,所得结果必然是9的倍数,自然也是3的倍数.所以只要一个数能被3整除,另一个也必然可以.命题成立.
如果要用归纳法,那么本题的证明还是需要一定技巧的.这类问题我总结为”你明明知道,但就是无法证明”
(这个问题还需要再想想)
2.10
这个问题也可以直接求解,二项式的和,$S _ n = 2 ^ n$
n=1时成立,归纳基础成立
- 假设k<n时成立
- 当k=n时,观察相邻两行的差距,很自然可得$S _ n = 2 (S _ {n - 1} - 1) + 2 = 2 S _ {n - 1}$,前面是n-1行相加提供n行的中间数字,后面的2是首尾的1.假设成立
- 命题成立
ps:
差值是利用归纳假设的一种方式
2.11
第一步肯定是随手画画(我们好久没用这个词了..),观察一下每行的和,一个自然的猜测是$S _ n = 3 ^ n$
n=1/2/3/4时肯定成立(这是猜测的来源),归纳基础成立
- 假设k<n时成立
- 当k=n时,观察相邻两行的差值,自然可得$S _ n = 3 (S _ {n - 1} - 1) + 1 + 2 = 3 S _ {n - 1}$,前面两项还是两行见相加的差值,后一项是首尾的1.假设成立
- 命题成立
2.12
n=2时,假设成立.归纳基础成立
- 假设k<n时成立,即$S _ {n - 1} = 1 / n + 1 / (n + 1) + \cdots + 1 / (2 n - 2) > 13 / 24$
- 当k=n时,$S _ n = 1 / (n + 1) + \cdots + 1 / (2 n - 2) + 1 / (2 n - 1) + 1 / (2 n)$,观察二者的差值,只有n-1的首项和n的后两项,而且可以证明$1 / n < 1 / (2 n -1) + 1 / {2 n}$,所以有$S _ n > S _ {n - 1} > 13 / 24$,假设成立
- 命题成立
ps:
当遇到问题瓶颈的时候,将归纳假设和待证项分别列出,往往可以得到解决问题的线索.
记住,归纳的关键不在于凭空解决问题(当然,这是我们的目标!!),而在于将待证的问题推导到归纳假设上来,将未知转换为已知.
事先可以发现问题的本质固然非常不错,发现不了的时候,就在归纳的时候慢慢寻找
2.13
这个问题非常的巧妙,解题过程值得思考
一开始解题时,还是按照旧思路,n-1=>n的归纳方法,但是在判断奇偶的时候出了瓶颈.单一的n非常难判断奇偶性,此时就需要分别讨论,再各自的奇偶性内,还要讨论奇偶性.这条道路估计也行得通,但我分析了一段时间(好几十分钟!!!),觉得就不想走下去了
然后就换了思路,既然n奇偶性很难,那相邻两个的奇偶性不就简单了么?一开始我并不知道怎么使用,就开始尝试n-2,n-1=>n,结果待证问题中出现$n (n - 1)$这样奇偶性确定的式子,立马觉得走对路了
n=1/2时成立.归纳基础成立
- 假设k<n时成立,即$S _ k = \sum _ {i = 1} ^ {t} \frac{1}{i} = \frac{k _ t}{m _ t}, k _ t = 2 a - 1, m _ t = 2 b, a, b \in Z ^ + $
- 当k=n时,有 \(S _ n = S _ {n - 2} + \frac{1}{n - 1} + \frac{1}{n} = \frac{k n (n - 1) + m (2 n - 1)}{m n (n - 1)}\) $n (n - 1)$为奇,$k n (n - 1)$为奇;$2 n - 1$为奇,$m (2 n - 1)$为偶;二者相加为奇;$m n (n - 1)$为偶.由此假设成立
- 命题成立
ps:
这个问题部分展示了归纳的奇妙之处,我们并不是第一眼就知道要强归纳的,而是在归纳的过程中,发现需要强化归纳假设才能给予证明,然后才加强归纳假设
解题是一个脚印一个脚印的前行,而不是一蹴而就的解决