问题集6的解 到期：星期一下午9点，三月28日 间题1 Sammy是一个金脸服务提供商，能给以下项目商提侯货款： ●Sam可y上午给一个客户贷款m美元.这使符这个客户拥有Sam町ym美元的债 务 ●每个绕上，Samm首先牧取“服务费用”，使得客户的债务提高f美元，然后Smmy 改变利息，也就是用一个因子p乘以其债务，例如，如果Smmy的利率每天是5%， 椰么p是1.05. ()在第一天结束的时候，客户的债务是什么？ 解：在第一天结束的时候，客户欠Sam野(m+p■mp+印美元 )在第二天结束的时候，客户的债务是多少？ 解：m+p+p=mp+p+p ()写初一个d天后客户的债务的公式，且寻找一个等价闭公式. 解：在三天后的客户的债务是 (((m+fp+fip+f)p=mp'+fp'+fp+fp 一般化模式，在d天后，客户欠 d mp2+ f k=1 美元。对几何求和应用公式拾出： +-( 问题2：寻找一个等于以下和的闭型表达式。说明你的步耀。 a 92-7 119 i=0 解：把表达式分为两个几何级数，然后应用几何级数求和公式， Pf文件使用"pdfFactory Pro”试用版本创建w.fineprint.cn
问题集 6 的解 到期：星期一下午 9 点，三月 28 日 问题 1 Sammy 是一个金融服务提供商，他给以下项目商提供贷款。 l Sammy 上午给一个客户贷款 m 美元。这使得这个客户拥有 Sammy m 美元的债 务。 l 每个晚上，Sammy 首先收取“服务费用”，使得客户的债务提高 f 美元，然后 Sammy 改变利息，也就是用一个因子 p 乘以其债务。例如，如果 Sammy 的利率每天是 5%， 那么 p 是 1.05。 (a) 在第一天结束的时候，客户的债务是什么？ 解：在第一天结束的时候，客户欠 Sammy (m+f)p = mp + fp 美元 (b) 在第二天结束的时候，客户的债务是多少？ 解：((m+f)p + f)p = mp 2 + fp2 + fp (c)写初一个 d 天后客户的债务的公式，且寻找一个等价闭公式。 解：在三天后的客户的债务是 (((m+ f)p+ f)p+ f)p= mp 3 + fp3 + fp2 + fp. 一般化模式，在 d 天后，客户欠 美元。对几何求和应用公式给出： 问题 2： 寻找一个等于以下和的闭型表达式。说明你的步骤。 (a) 解：把表达式分为两个几何级数，然后应用几何级数求和公式。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
-()() 1-()+11-()+ 1-品 1- 号()+()+ 11.9)” )使用对数援约这个乘法为一个容易的和。 34+5=3ogg(Π=134+5 =3i45 =32n(n+1)+5nm (c) 解，这个外表可怕的求和是一只纸老虎：我们仅应用儿何领数求和公式，然后使用算术领数 求和即可。 2--” 1-(1-n】 =∑22 j=1 2n(n+)m+1) 3 问题3在一米的地毯商又一个虫子。虫子想要穿越到毯子的另一端，它每秒爬1m:然而， PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
(b) 使用对数规约这个乘法为一个容易的和。 (c) 解：这个外表可怕的求和是一只纸老虎；我们仅应用几何级数求和公式，然后使用算术级数 求和即可。 问题 3 在一米的地毯商又一个虫子。虫子想要穿越到毯子的另一端。它每秒爬 1 cm。然而， PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
在每秒结束的时候，一个不怀好意的一年级名为Mildred Anderson的学生把毯子拉长I米. 假设地的动作是瞬时的。且毯子均匀地被拉长。那么。在前面儿秒钟内，发生了什么？ ·虫子在的一秒中前送Icm,因此99cm在前面。 ·Mded拉种毯子1米，这个两倍其长度，因此现在有2cm在虫子的后面且19然em 在前面。 ·虫子在下一秒中前透另一个1cm,图下3cm在后面且197cm在前面. ·那么Mdd努力把毯子从2米拉到3米。因此，现在是3·(3/2)=4.5cm在 虫子的后面，且197·(3/2=295.5cm前面. ·虫子行走另一个在第三秒1Cm,依此类推。 (a)在秒1中，虫子穿越毯子的部分是多少？ 解：在i秒中，甚子的长度是100icn,且虫子穿越1cm.因比，虫子穿越的部分是1/10Oi. (6)在前面的n秒后，虫子穿越的毯子的部分总共是多少？ 解：虫子在第一秒中穿越毯子的1/100，在第二秒中为1/200，在第三秒中为1/300， 依此类推。因此，在前面的秒中。虫子穿越的部分是： =Hn./100 100k k=1 (这个公式是有效的，仅当虫子达到毯子的远端) 》估计虫子穿越整个毯子需要多少秒？ 解：虫子到达运端。当它穿越的部分到达1。当，逝去的秒数，的时候发生，有足够 大H/00≥1，现在H,大约是an:因此虫子到达当： Inn 100 21 lnn≥100 n≥e1oo≈103 seconds 问愿4：使用积分来发现以下无限求和相差大约0.1的上下界。说明你的工作。 S= 11.1 127 221 32十42+… PDF文件使用“pdfFactory Pro”试用版本创建，fineprint.cn
在每秒结束的时候，一个不怀好意的一年级名为 Mildred Anderson 的学生把毯子拉长 1 米。 假设她的动作是瞬时的，且毯子均匀地被拉长。那么，在前面几秒钟内，发生了什么？ l 虫子在的一秒中前进 1 cm，因此 99 cm 在前面。 l Mildred 拉伸毯子 1 米，这个两倍其长度。因此现在有 2 cm 在虫子的后面且 198 cm 在前面。 l 虫子在下一秒中前进另一个 1 cm，留下 3 cm 在后面且 197 cm 在前面。 l 那么 Mildred 努力把毯子从 2 米拉到 3 米。因此，现在是 3 ·(3/2) = 4.5 cm 在 虫子的后面，且 197·（3/2）= 295.5 cm 前面。 l 虫子行走另一个在第三秒 1 cm，依此类推。 (a)在秒 1 中，虫子穿越毯子的部分是多少？ 解：在 i 秒中，毯子的长度是 100i cm，且虫子穿越 1cm。因此，虫子穿越的部分是 1/100i。 (b)在前面的 n 秒后，虫子穿越的毯子的部分总共是多少？ 解：虫子在第一秒中穿越毯子的 1/100 ，在第二秒中为 1/200，在第三秒中为 1/300， 依此类推。因此，在前面的 n 秒中，虫子穿越的部分是： (这个公式是有效的，仅当虫子达到毯子的远端.) (c ) 估计虫子穿越整个毯子需要多少秒？ 解：虫子到达远端，当它穿越的部分到达 1。当 n，逝去的秒数，的时候发生，有足够 大 Hn/100 ≥ 1。 现在 Hn 大约是 ln n，因此虫子到达当： 问题 4： 使用积分来发现以下无限求和相差大约 0.1 的上下界。说明你的工作。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
为了达到准确度，明确求和面结各项，然后使用积分米界限所有剩余的项。 解：前面三个项的和是： 1 1149 8= 1+22+32=36 剩余项的上界是： 1 13 3 总的来说，我们有： 58 491 9.161 36≤36+4≤≤ 6+3=36 这些界限差是1/121天的调度结束于3个可能的2-天活动成者2个可能的1-天活动中的一个，因 此 S(n)=2S(n-1)+3S(n-2) for n 1. )通过求解递推寻找一个可能的办天调度的闭形表达式 解：这个线性齐次递推的特任多式是： PF文件使用"pdfFactory Pro”试用版本创建w.fineprint.cn
为了达到准确度，明确求和前面结各项，然后使用积分来界限所有剩余的项。 解：前面三个项的和是： 剩余项的上界是： 总的来说，我们有： 这些界限差是 1/12 1 天的调度结束于 3 个可能的 2-天活动或者 2 个可能的 1-天活动中的一个。因 此 ， (b) 通过求解递推寻找一个可能的 n-天调度的闭形表达式。 解：这个线性齐次递推的特征多项式是： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
x22x-3=(x+1)(x-3,因此解是形式Sn)=a-1P+b3”。n=0,我们得出结论+ b=1,且令n=1,我们得到-4+36=2，因此b=34,a=1/4,且解是： 3m+1+(-1) S(n)= 4 问题6寻找对T)的闭形表达式，这个以如下递推定义： T(0)=0 T(1)=1 T(n)=5T(n-1)-6T(n-2)+6 for all n≥2 解：特征方程是x2-5x+6=0,其根是x=2且x=5。因此，通解是： T(n)=A·2"+B.3" 对于一个转解，让我们首先猜精测T()-c c-5e=6e+6 =>=3 我们的精测是对的：T)一3是一个特解：把这个如到通解上给出一粒解： T()=A.2"+B.3"+3 替换n=0和n=1给出1 0=A+B+3 1=2A+3B+3 求解这个方程给出A=7且B■4。因此： T(n)=-7.2"+4.3”+3 问题：判定下面这项是睿每个函数的渐近行为： e(n),Θ(n2ogn),0(n2,0(1),Θ(2")，日(2mn") 证明是不需要的，但是需要简单说明你的答案。 n+Inn+(Inn)2 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
x 2 -2x – 3 = (x + 1) ( x -3)。因此解是形式 S(n) = a(-1)n + b3n。令 n = 0，我们得出结论 a + b = 1，且令 n = 1，我们得到 –a + 3b = 2，因此 b = 3/4， a = 1/4，且解是： 问题 6 寻找对 T(n)的闭形表达式，这个以如下递推定义： 解：特征方程是 x 2 – 5x + 6 = 0, 其根是 x = 2 且 x = 3。因此，通解是： 对于一个特解，让我们首先猜测 T(n) = c: c= 5c – 6c + 6 ＝> c=3 我们的猜测是对的；T(n) = 3 是一个特解：把这个加到通解上给出一般解： 替换 n = 0 和 n = 1 给出： 求解这个方程给出 A = -7 且 B = 4。因此： 问题 7：判定下面选项是否每个函数的渐近行为。 证明是不需要的，但是需要简单说明你的答案。 (a) PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
解：n>nn且n>n旷，对于所有足够大的n都成立。因此多于所有的是够大的 nn+Inn+(Inn)2<n+n+n Son+lnn+(nn)2=θ(n) n2+2n-3 (b) n2-7 解：现察到： n2+2m-3 lim n-00 n2-7 =1 这个意味着，对于所有的是够大的n。分数，例如，在0.9羽到101之创，因此8() (e) 74 22+1 =0 解：几何和是通过最大项来主导的，也流是2=2·4”这也藏是©(4，这个没有出 暖在提供的列表中。 (d) In(n21) 解：由Stirling的公式得到： n2~V2mn2 e 使用对数得出： n2 ln(n2)）ln(v2mn2 =ln(√2rm2)+ln 和第二项比较，第一项是小的，这个能重写为： FPDF文件使用“pdfFactory Pro”试用版本创建fineprint.cn
解：n > ln n 且 n > (ln n)2，对于所有足够大的 n 都成立。因此多于所有的足够大的 n: (b) 解：观察到： 这个意味着，对于所有的足够大的 n，分数，例如，在 0.99 到 1.01 之间，因此Θ(1)。 ( c) 解：几何和是通过最大项来主导的，也就是 22n+1 ＝ 2· 4n . 这也就是 Θ(4n )，这个没有出 现在提供的列表中。 (d) 解：由 Stirling 的公式得到： 使用对数得出： 和第二项比较，第一项是小的，这个能重写为： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
e(n2 In n) e )=n( e 三(-) 解：这个在基号中的表达式总是至少2且至多是1。因此，我们有界限： 三≤(-)s 既然第一个表达式和最后一个都是日(，因此，一个在中间。 问题8一个三角数字是一个有形式 k(k+1) n=1+2+3+..+k= 2 的整数，这里k是一个正整数， a)指述aai难题的有kk十1)2个盘子的4个立桂的解需要T次移动，这里： T1=1 T=2T-1+2*-1 解： 递白的移动所有但是k最大的盒子到另一个柱子上这个需要)移动 ·移动k个最大的盘子到另一个柱子上使用三柱子策略。这个需要21移动。 ·现在递日地移动所有的在k最大盘子上的其他盘子。这个需要Tk)移动。 因此，使用这个策略，总的香要移动一堆k+1)2盘子需要的岁骤是Tk)-2Tk1)+2” .1. b)寻找一个萝于T的闭形。 解：这是一个非齐次线性方程。让我们开始尝试发现一个特解：存在弥数项2)和一个 常数项，因此我们可能猜测形式a2+©： Pf文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
(e) 解：这个在括号中的表达式总是至少 1/2 且至多是 1。因此，我们有界限： 既然第一个表达式和最后一个都是Θ(n2 )，因此，一个在中间。 问题 8 一个三角数字是一个有形式 的整数，这里 k 是一个正整数。 (a) 描述 Hanoi 难题的有 k(k＋1)/2 个盘子的 4 个立柱的解需要 Tk次移动，这里： 解： l 递归的移动所有但是 k 最大的盘子到另一个柱子上。这个需要 T(k-1)移动。 l 移动 k 个最大的盘子到另一个柱子上使用三柱子策略。这个需要 2k -1 移动。 l 现在递归地移动所有的在 k 最大盘子上的其他盘子。这个需要 T(k-1)移动。 因此，使用这个策略，总的需要移动一堆 k(k+1)/2 盘子需要的步骤是 T(k) = 2T(k-1) + 2k -1。 (b) 寻找一个等于 Tk的闭形。 解：这是一个非齐次线性方程。让我们开始尝试发现一个特解：存在指数项(2k )和一个 常数项，因此我们可能猜测形式 a2k + c： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
a2*+c=2(a2-1+c)+2*-1 =(a+1)2*+2c-1 ÷0=2*+(c-1) 显然，常数相是一，但是指数部分更复杂一些。我门的方法说我们能尝试一个形式为 2+bk2+1的特解 a2*+bk2*+1=2(a2*-1+b(k-1)2-1+1)+2*-1 =(a-b+1)2*+bk2*-1 等价2项的系数给出a=a-b+1。这个蕴辆b=1。因此，心+k上+1是对所有。 的转解：只要我们有这个自由，我们可能选择以便这个解是和界限条件T一1相一致 的。且能写成： a2+1.2+1=1 →a=-1 T=(k-1)2*+1. 因此。递推的解是： )估计需要多少步移动求解4个桂子，n个盘子的n的函数的Ham塔何题？假设n 是一个三角数。（在格式这点上，正确使用渐近符号，） 解：我们有k=(V8m+1-1)=V2五+O(1),因此移动 Θ(Vm2v2m 的步耀需要 Pf文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
显然，常数相是 c=1，但是指数部分更复杂一些。我们的方法说我们能尝试一个形式为 a 2 k + bk2k +1 的特解： 等价 2 k项的系数给出 a = a – b + 1。这个蕴涵 b = 1。 因此，a2k + k 2k + 1 是对所有 a 的特解：只要我们有这个自由，我们可能选择 a 以便这个解是和界限条件 T1 = 1 相一致 的。且能写成： 因此，递推的解是： (c) 估计需要多少步移动求解 4 个柱子，n 个盘子的 n 的函数的 Hanoi 塔问题？假设 n 是一个三角数。（在格式这点上，正确使用渐近符号。） 解：我们有 ，因此移动 的步骤需要 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn