赏析运用斐波那契数列归纳证明的问题

奥数

1 6

中等数学

些

赏析运用斐波那契数列归纳证明的问题武炳杰(上海市复旦大学附属中学高三(),043 8班 2 03 )

斐波那契数列是由一个古老的兔子生兔子问题所引发的，然而，其意义却不仅满足于求解通项公式，多问题甚至在题中丝毫不许出现递推关系，的求解却蕴涵了斐波那契它数列的思想，这些问题包含了看似普通的数论甚至组合的问题 .

因此，k m):, )f (,=( fF… (∈N) .

这里应该注意到斐波那契数列相邻两项互质的事实(反证法易证) . 另一方面，易验证对于所有的 Z容∈N,F

。= i

L都能使数列包含数字 1 .

』’ 1+l 2

本文以几道竞赛试题为例，与读者赏析 .题 1求所有的整数对 (,, k m) m>k ≥

选择此题的原因在于说明，即使是递归数列的试题，以斐波那契数列为背景，若也未必一眼就能看出来 . 题 2证明：有无穷多对正整数 o b满足：、,0I b+1, 0+1 . )b (。 ) ( I

0 ( ),,m,=1使得定义为

{ l ; 蠢L 1,=1

对于此题的讨论可参考文[] 1.列举题 2为了说明斐波那契数列也可是

的数列一定包含数字 1 .

分析：定义斐波那契数列{} :r=F=1+=F++ ( 01… ) o l, 2 ol n=,, .

成为数论问题中的背景 .分析：小的正整数开始枚举，从最l+1, =2 2+1, 2=55+ 1:2× 1 1+ 1:5×3 3. 3 4.

通过对小量数据的枚举，不难发现答案为 ( m) F F… )(∈N),=(, 2 Z . 首先， 下面运用数学归纳法 . 若含有数字 1则存在一些，,有l.

=

.

发现 (, ) (,) (,3, 12,2 5, 5 1 )……均满足

题意，可以看出所求数为斐波那契数列的相邻的奇数项 .只需用归纳法证明：F2一

Fb‘

1

F 3 2+=

++1 1 .

①

式①的证明见文[] 2. 题3 为满足以下递推关系的全部函,则

假设“~一’’

数：{,, }{,, }且从 12…,到 12…,,()( ) 1f k≤k+1 k:12…, ) (,, n; ()( ) ( 2 f k

≠k k=2 3…, ),, n .

‰

一 F2‘Ⅲ,一

2+ l

求从中随意取出一个函数 .使得厂，厂1≠1 ()的概率 .

从，有。≠ .而必= 收稿日期：O7—1 2O 2—1 3

(98韩国数学竞赛) 19, 此题是斐波那契数列在计数问题中的运

奥数

20第 1期 08年 1

1 7

用.通过对 n为较小数的枚举，难发现其不F

不同，题的立意很新颖 .本利用斐波那契数列来归纳求解，全体现出了数学之美 .完

结果应为』。H

,中， i示斐波那契数列其 F表

取 n个砝码，记第 i个砝码的重量为(≤ 1≤凡 . )

的第项 . 下面用数学归纳法证明：

首先用归纳法证明：

有个元素，且其中有一个满足。厂 1=2而厂1≠1 . () ( () ).

对于重 (≤W + 1的物体， 1≤一 )可以用 n个砝码量出其重量 . 当 t=1, 3 2 l ./时 F=F+F=2,于是， =1=1显然可以量出 . F一1, ,

显然， n=1,论成立 .当时结 下面令 n,≥2运用构造一一对应的方法来计数 . 如果/ , 1=2则可以确定一个∈ f( ),

设对 n成立，考虑+1个砝码 . 由归纳假设， F。F,,可量出大用，:…

函数 g 一. E。

若 .+1=1则 g k=1而其他的厂 ( ), (),,

于或等于 1小于或等于+一1、:的物体，则可以多放入一个重为+的砝码 .。而+≥:+

f+1≠1于是， ) ( ( ), g(=+1一1 ) .

相反地，对于任一个函数 g 一，∈ 都唯一

+1 (≥1, )从而，以称量的范围扩大可上述结论成立 . 现在去掉一个砝码 F,用归纳法证 利

地对应一个 f , C使得 f 1= . () 2所以，/的个数是F的元素总个数 . 由归纳假设知有一个 . 另一方面，以通过令可g( ) ( k=厂 k+1一1 ),

至+ +一l +—1 0+ 2= 3 .

明：由重量为 l F,, il F,:,, 2… F—,…‘ ‘

的砝码可以称量重量为 (≤ 1≤+一1 , ) 的物体 .当=2时，+ 1— 1= F3— 1= F

l+ F2— 1= 1,

知使得/ 1=1fE的集合元素与满足 (), g 1=,∈一的集合元素一一对应 . () 2 g 那么，由归纳假设知，满足 f 1=1fE的个 (), 数有 F一个 .

而 F=F=1随意去掉一个仍可称量 . l 2,设当 n≥ 2时成立，考虑 n+1个砝现码.

故的元素总个数为一+一=, .: F

其中，使得， 1≠l ()的概率为J n

.

若去掉的是砝码+, 由前面归纳知用F,,,可称量重为 w(≤≤+ )。… 1 一1的物体 . 若去掉的是砝码 (∈{,,,} . i l2… )由归纳假设知 F,:…,一，+一， F, ,

由归纳法知，原命题得证 . 题 4 () 1是否存在 l O个整数克重的砝码 (同砝码可能有相同重量 )用天平可以不，

量出从 1到 8重的任何物体，至少了 g 8g甚任何一个砝码也能做到这一点？ () 2是否存在 1整数克重的砝码 ( 2个不

可量出重量为 (≤1≤F+一1的物体 . 1/ n ) )现

同砝码可能有相同重量 )用天平可以量出从， 1到 5重的任何物体， g 9g甚至少了任何两个砝码也能做到这一点？

在考虑重量为 (≤≤+一1的物体， 1 : )其中，≤W≤+一1 1 的部分可通过那 1 1,一1个砝码称量 .只需考虑+≤≤ F+—l。 nz 的部分 .将砝码+放上，化为用凡一1先，转

本题是 1 3 9年环球城市数学竞赛的一 9道题，者略有改动 .笔与其他的砝码问题有所

奥数

1 8

中等数学

{赛窗l r之 ”—竞— 1—..、 .,, .、 . . .. .

一

第 48届

I M0预选题 ( )四李建泉译{,,,中的数被染成红色或蓝色，满 12… n}并

(天津师范大学数学教育科学与数学奥林匹克研究所，037 30 8 )

组合部分1已知凡是大于 l .的整数 .求满足下列条件的所有数列口，…, . 0,口() {,}对于所有满足 1 1 a∈ 0 1,≤≤

足下列条件：集合 S×S×S恰包含 2 0个 7 0有序三元数组( Y,,,)使得() Y。同色； 1、、(

) 2+Y+z可以被 n整除 .

/+n的成立；, I ( ) l 2 2 a++a++…+a+ < nI+n+1+ r￡上+n++… 2+ ai 2 + n,

4设 A=(。a, n ) .。 a,:…,是实数数列 . 对于每个非负整数 k由数列 A=(,, 戈，…

,

)构造一个新的数列 A满足下列来…

对于所有满足 0≤n一n的成立 .≤

条件：

2将一个单位正方形分割成 n n ) . (>1个矩形，每个矩形的边与单位正方形的边平行 .

() 1选择{,, n的一个分割八j, l2…,} I,满足， , UJ={,,,,, nJ:, 12… 1表达式 7}

任意一条与单位正方形的边平行，过正方且形内部的点的直线也过某个矩形内部的点 . 证明：存在一个矩形，其内部及边界上的点都不是单位正方形边界上的点 . 3求所有的正整数 l使得集合 S= . l,,个砝码称量重为 W(≤W≤+ 1一1一+ 。= 一

l一 l得小允或J ∑∑取最值(许，是i/ E j C -J

空集，种情况的和为 0,果有多于一个这 )如这样的分割，意选其中的一个；任

() 2设数列 A=(。Y,,, Y,:… Y )其中， 的n个砝码，任意去掉两个，仍能称出重为w1 (≤W≤g n+1一1的物体， g 1) ( ) )而 (3=6 0.

1+<一1的物体，样可以由归纳 )这

假设得证 .综上，由归纳法知结论成立 .取 n=1, I 2, 3, 0 F=F=1 F=2F4=3, F5=5, F6=8, F7= 1 3, F8=2 F9=3 Fl 1, 4, o=5 5.

所以，量范围为 1 ≤5重≤ 9的物体是可以找到满足题意的 1 2个砝码来称量出的 .

这几道题的解答过程几乎都是先枚举尝试，发现规律为斐波那契数列后 …… 此处隐藏：2401字，全部文档内容请下载后查看。喜欢就下载吧 ……