学生习作
收稿日期:2007-12-13
赏析运用斐波那契数列归纳证明的问题
武炳杰
(上海市复旦大学附属中学高三(8)班,200433)
斐波那契数列是由一个古老的兔子生兔
子问题所引发的,然而,其意义却不仅满足于
求解通项公式,许多问题甚至在题中丝毫不
出现递推关系,它的求解却蕴涵了斐波那契
数列的思想,这些问题包含了看似普通的数
论甚至组合的问题.
本文以几道竞赛试题为例,与读者赏析.
题1求所有的整数对(k,m),m>k≥
0,(m,k)=1,使得定义为
x0=km,xn+1=
2xn-1
1-xn,xn≠1;
1,xn=1
的数列一定包含数字1.
分析:定义斐波那契数列{Fn}:
F0=F1=1,Fn+2=Fn+1+Fn(n=0,1,…).
通过对小量数据的枚举,不难发现答案
为(k,m)=(F2l,F2l+1)(l∈N).
首先,由xn+1=2xn-11-x
n
]xn=xn+1+1x
n+1+2
.
下面运用数学归纳法.
若含有数字1,则存在一些j,有
xj=1=F0F
1
.
假设xp+1=F2iF
2i+1
,则
xp=
F2i
F2i+1+1
F2i
F2i+1+2
=F2i+2F
2i+3
.
从而,必有x0=F2lF
2l+1
.
因此,(k,m)=(F2l,F2l+1)(l∈N).
这里应该注意到斐波那契数列相邻两项
互质的事实(反证法易证).
另一方面,容易验证对于所有的l∈N,
x0=F2lF
2l+1
都能使数列包含数字1.
选择此题的原因在于说明,即使是递归
数列的试题,若以斐波那契数列为背景,也未
必一眼就能看出来.
题2证明:有无穷多对正整数a、b,满足:
a|(b2+1),b|(a2+1).
对于此题的讨论可参考文[1].
列举题2是为了说明斐波那契数列也可
成为数论问题中的背景.
分析:从最小的正整数开始枚举,
12+1=2,22+1=5,
52+1=2×13,132+1=5×34,
……
发现(1,2),(2,5),(5,13),……均满足
题意,可以看出所求数为斐波那契数列的相
邻的奇数项.只需用归纳法证明:
F2n-1F2n+3=F22n+1+1.①
式①的证明见文[2].
题3Fn为满足以下递推关系的全部函
数:从{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-1F
n
,其中,Fi表示斐波那契数列
的第i项.
下面用数学归纳法证明:
Fn有Fn个元素,且其中有Fn-1个满足
f(1)=2(而f(1)≠1).
显然,当n=1时,结论成立.
下面令n≥2,运用构造一一对应的方法
来计数.
如果f∈Fn,f(1)=2,则可以确定一个
函数g∈Fn-1.
若f(k+1)=1,则g(k)=1,而其他的
x,f(x+1)≠1,于是,g(x)=f(x+1)-1.
相反地,对于任一个函数g∈Fn-1,都唯
一地对应一个f∈Fn,使得f(1)=2.
所以,f的个数是Fn-1的元素总个数.
由归纳假设知有Fn-1个.
另一方面,可以通过令
g(k)=f(k+1)-1,
知使得f(1)=1,f∈Fn的集合元素与满足
g(1)=2,g∈Fn-1的集合元素一一对应.那
么,由归纳假设知,满足f(1)=1,f∈Fn的个
数有Fn-2个.
故Fn的元素总个数为Fn-1+Fn-2=Fn,
其中,使得f(1)≠1的概率为Fn-1F
n
.
由归纳法知,原命题得证.
题4(1)是否存在10个整数克重的砝
码(不同砝码可能有相同重量),用天平可以
量出从1g到88g重的任何物体,甚至少了
任何一个砝码也能做到这一点?
(2)是否存在12个整数克重的砝码(不
同砝码可能有相同重量),用天平可以量出从
1g到59g重的任何物体,甚至少了任何两
个砝码也能做到这一点?
本题是1993年环球城市数学竞赛的一
道题,笔者略有改动.与其他的砝码问题有所
不同,本题的立意很新颖.利用斐波那契数列
来归纳求解,完全体现出了数学之美.
取n个砝码,记第i个砝码的重量为Fi
(1≤i≤n).
首先用归纳法证明:
对于重w(1≤w≤Fn+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+2≥
Fn+1+1(n≥1),从而,可以称量的范围扩大
到Fn+1+Fn+2-1=Fn+3-1.
上述结论成立.
现在去掉一个砝码Fi,利用归纳法证
明:由重量为F1,F2,…,Fi-1,Fi+1,…,Fn
的砝码可以称量重量为w(1≤w≤Fn+1-1)
的物体.
当n=2时,
Fn+1-1=F3-1=F1+F2-1=1,
而F1=F2=1,随意去掉一个仍可称量.
设当n≥2时成立,现考虑n+1个砝
码.
若去掉的是砝码Fn+1,由前面归纳知用
F1,F2,…,Fn可称量重为w(1≤w≤Fn+2-1)
的物体.
若去掉的是砝码Fi(i∈{1,2,…,n}).
由归纳假设知F1,F2,…,Fi-1,Fi+1,…,Fn
可量出重量为w(1≤w≤Fn+1-1)的物体.现
在考虑重量为w(1≤w≤Fn+2-1)的物体,
其中,1≤w≤Fn+1-1的部分可通过那n-1
个砝码称量.只需考虑Fn+1≤w≤Fn+2-1
的部分.先将砝码Fn+1放上,转化为用n-1
712008年第11期
个砝码称量重为w(1≤w≤Fn+2-1-Fn+1
=Fn-1
假设得证.
综上,由归纳法知结论成立.
取n=10,F1=F2=1,F3=2,
F4=3,F5=5,F6=8,F7=13,
F8=21,F9=34,F10=55.
其中任意去掉一个,仍可以称量重为w
(1≤w≤F11-1=89-1=88)的物体.
对于(2),可以构造广义斐波那契数列:
g(n)=g(n-1)+g(n-3)(n≥4),
g(1)=g(2)=g(3)=1.
用与(1)类似的方法,可以说明对于这样
的n个砝码,任意去掉两个,仍能称出重为
w(1≤w≤g(n+1)-1)的物体,而g(13)=
60.
所以,重量范围为1≤w≤59的物体是
可以找到满足题意的12个砝码来称量出的.
这几道题的解答过程几乎都是先枚举尝
试,发现规律为斐波那契数列后,再进行归纳
证明,这反映了“探索———猜想———证明”的
解题步骤.
参考文献:
[1]武炳杰.从无穷递降法到递推数列[J].中等数学,
2008(5).
[2]吴振奎.斐波那契数列[M].沈阳:辽宁教育出版社,
1987.
竞赛之窗
第48届IMO预选题(四)
李建泉译
(天津师范大学数学教育科学与数学奥林匹克研究所,300387)
组合部分
1.已知n是大于1的整数.求满足下列
条件的所有数列a1,a2,…,an2+n.
(1)ai∈{0,1},对于所有满足1≤i≤
n2+n的i成立;
(2)ai+1+ai+2+…+ai+n
对于所有满足0≤i≤n2-n的i成立.
2.将一个单位正方形分割成n(n>1)个
矩形,每个矩形的边与单位正方形的边平行.
任意一条与单位正方形的边平行,且过正方
形内部的点的直线也过某个矩形内部的点.
证明:存在一个矩形,其内部及边界上的点都
不是单位正方形边界上的点.
3.求所有的正整数n,使得集合S=
{1,2,…,n}中的数被染成红色或蓝色,并满
足下列条件:集合S×S×S恰包含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}的一个分割I∪J,
满足I∩J=`,I∪J={1,2,…,n},表达式
∑i∈Ixi-∑j∈Jxj取得最小值(允许I或J是
空集,这种情况的和为0),如果有多于一个
这样的分割,任意选其中的一个;
(2)设数列Ak+1=(y1,y2,…,yn),其中,
81中等数学
|
|
