《赏析运用斐波那契数列归纳证明的问题》由会员分享，可在线阅读，更多相关《赏析运用斐波那契数列归纳证明的问题（3页珍藏版）》请在金锄头文库上搜索。
1、学生习作收稿日期:2007-12-13赏析运用斐波那契数列归纳证明的问题武 炳 杰(上海市复旦大学附属中学高三(8)班,200433)斐波那契数列是由一个古老的兔子生兔 子问题所引发的,然而,其意义却不仅满足于 求解通项公式,许多问题甚至在题中丝毫不 出现递推关系,它的求解却蕴涵了斐波那契 数列的思想,这些问题包含了看似普通的数论甚至组合的问题. 本文以几道竞赛试题为例,与读者赏析.题1 求所有的整数对(k,m) ,mk0 ,(m,k) =1 ,使得定义为x0=k m,xn+ 1=2xn- 1 1-xn,xn1 ;1 ,xn= 1的数列一定包含数字1. 分析:定义斐波那契数列Fn :F0=F1
2、=1,Fn+2=Fn+1+Fn(n=0,1,).通过对小量数据的枚举,不难发现答案 为(k,m) = (F2l,F2l+1) (lN) .首先,由xn+ 1=2xn- 1 1-xnxn=xn+ 1+1 xn+ 1+2.下面运用数学归纳法. 若含有数字1 ,则存在一些j,有xj= 1=F0 F1.假设xp+ 1=F2i F2i+1,则xp=F2i F2i+1+1F2i F2i+1+2=F2i+2 F2i+3.从而,必有x0=F2l F2l+1.因此,(k,m) = (F2l,F2l+1) (lN) .这里应该注意到斐波那契数列相邻两项互质的事实(反证法易证) .另一方面,容易验证对于所有的lN,
3、x0=F2l F2l+1都能使数列包含数字1.选择此题的原因在于说明,即使是递归 数列的试题,若以斐波那契数列为背景,也未 必一眼就能看出来. 题2 证明:有无穷多对正整数a、b,满足:a| (b2+ 1) ,b| (a2+1) . 对于此题的讨论可参考文1. 列举题2是为了说明斐波那契数列也可 成为数论问题中的背景.分析:从最小的正整数开始枚举,12+1=2 , 22+1=5 ,52+1=213 ,132+ 1=534 , 发现(1 ,2) , (2 ,5) , (5 ,13) ,均满足题意,可以看出所求数为斐波那契数列的相 邻的奇数项.只需用归纳法证明:F2n-1F2n+3=F2 2n+1
4、+ 1.式 的证明见文2. 题3 Fn为满足以下递推关系的全部函数:从1 ,2 ,n到1 ,2 ,n ,且(1)f(k)k+ 1(k=1 ,2 ,n) ;(2)f(k)k(k= 2 ,3 ,n) .求从Fn中随意取出一个函数f,使得f(1)1的概率. (1998 ,韩国数学竞赛)此题是斐波那契数列在计数问题中的运61中 等 数 学用.通过对n为较小数的枚举,不难发现其结果应为Fn- 1 Fn,其中,Fi表示斐波那契数列的第i项. 下面用数学归纳法证明:Fn有Fn个元素,且其中有Fn- 1个满足f(1) =2 (而f(1)1) . 显然,当n=1时,结论成立.下面令n2 ,运用构造一一对应的方法
5、 来计数. 如果fFn,f(1) =2 ,则可以确定一个函数gFn- 1.若f(k+ 1) =1 ,则g(k) =1 ,而其他的x,f(x+1 )1 ,于是,g(x) =f(x+1 ) -1 . 相反地,对于任一个函数gFn- 1,都唯一地对应一个fFn,使得f(1) =2 .所以,f的个数是Fn- 1的元素总个数.由归纳假设知有Fn- 1个.另一方面,可以通过令g(k) =f(k+ 1) -1 , 知使得f(1) =1 ,fFn的集合元素与满足g(1) =2 ,gFn- 1的集合元素一一对应.那么,由归纳假设知,满足f(1) =1 ,fFn的个数有Fn- 2个.故Fn的元素总个数为Fn- 1
6、+Fn- 2=Fn,其中,使得f(1)1的概率为Fn- 1 Fn.由归纳法知,原命题得证. 题4 (1)是否存在10个整数克重的砝码(不同砝码可能有相同重量) ,用天平可以 量出从1 g到88g重的任何物体,甚至少了 任何一个砝码也能做到这一点?(2)是否存在12个整数克重的砝码(不同砝码可能有相同重量) ,用天平可以量出从1 g到59g重的任何物体,甚至少了任何两 个砝码也能做到这一点? 本题是1993年环球城市数学竞赛的一 道题,笔者略有改动.与其他的砝码问题有所不同,本题的立意很新颖.利用斐波那契数列 来归纳求解,完全体现出了数学之美.取n个砝码,记第i个砝码的重量为Fi(1in) .首
7、先用归纳法证明:对于重w(1wFn+ 2- 1)的物体,可以用n个砝码量出其重量.当n= 1时,F3=F2+F1=2.于是,F3- 1=1 ,w=1 ,显然可以量出.设对n成立,考虑n+ 1个砝码.由归纳假设,用F1,F2,Fn可量出大于或等于1、 小于或等于Fn+ 2- 1的物体,则可以多放入一个重为Fn+ 1的砝码.而Fn+2Fn+ 1+1(n1) ,从而,可以称量的范围扩大到Fn+ 1+Fn+ 2- 1=Fn+ 3- 1.上述结论成立.现在去掉一个砝码Fi,利用归纳法证明:由重量为F1,F2,Fi- 1,Fi+ 1,Fn的砝码可以称量重量为w(1wFn+1- 1)的物体.当n= 2时,F
8、n+1- 1=F3- 1=F1+F2- 1=1 ,而F1=F2= 1 ,随意去掉一个仍可称量.设当n2时成立,现考虑n+1个砝码.若去掉的是砝码Fn+ 1,由前面归纳知用F1,F2,Fn可称量重为w(1wFn+2- 1)的物体.若去掉的是砝码Fi(i1 ,2 ,n) .由归纳假设知F1,F2,Fi- 1,Fi+ 1,Fn可量出重量为w(1wFn+ 1- 1)的物体.现在考虑重量为w(1wFn+2- 1)的物体,其中,1wFn+1- 1的部分可通过那n-1个砝码称量.只需考虑Fn+1wFn+2- 1的部分.先将砝码Fn+ 1放上,转化为用n- 1712008年第11期个砝码称量重为w(1wFn+
9、2- 1-Fn+1=Fn- 11)个矩形,每个矩形的边与单位正方形的边平行.任意一条与单位正方形的边平行,且过正方形内部的点的直线也过某个矩形内部的点.证明:存在一个矩形,其内部及边界上的点都不是单位正方形边界上的点.3.求所有的正整数n,使得集合S=1 ,2 ,n中的数被染成红色或蓝色,并满足下列条件:集合SSS恰包含2007个有序三元数组(x,y,z) ,使得(1)x、y、z同色;(2)x+y+z可以被n整除.4.设A0= (a1,a2,an)是实数数列.对于每个非负整数k,由数列Ak= (x1,x2,xn)来构造一个新的数列Ak+ 1满足下列条件:(1)选择1 ,2 ,n的一个分割IJ,满足IJ=,IJ= 1 ,2 ,n ,表达式iIxi-jJxj取得最小值(允许I或J是空集,这种情况的和为0) ,如果有多于一个这样的分割,任意选其中的一个;(2)设数列Ak+1= (y1,y2,yn) ,其中,81中 等 数 学
