数学竞赛中的斐波那契数列问题.pdf

4 中书效 - 一 一 . 目 . . 目. . . . . . . . 曰. . . . . . 一 . 粥 二 卜 一 一 一 ,曰职 , . . , , 吕 . 一 , . . . 口护. . . . . . . . 数学竞赛中的斐波那契数列间题 刘 步舌 杰 (心 j 、义间 专 公 学 系) 数学竞赛从某种意义上可 以看成 是 欲学 研究的缩影与雏形 . 数学中的重要理 论以 及 数学研究中的某些 热点必 然 要渗 透于 其中 . 斐波那契数列就是一 个典型例 子 . 尹下 文将介 绍一些以斐波 那契数 列问题 为背景 l i : J国外众 学竞赛题 。 例1 . (第1 4届 全俄数学竟赛)设 = 厂孟 十厂2 厂 。一 厂孟 1+ 一 一 止 1 其中,和 n 是互质的白然 数 , 而等式左边含 有 19 88条分数线 , 试计算 m Z + 。2:一: 2 的值 . 解设上述含有k条分数线 的繁分数的 值为 。: 、/nk 夕 , : 二) 嫩k +1 九k+z (刀: ;, 1 1十世些 、)= 1 , 咒k 刀z、+7zk, 吕 l m k+ := 注意到 7乙k Zlk ,尤 、 十l= m : 1 ”z盆+n。 一 生= 气一, 阴 1 儿1 1 = 1 , 222= 1 将它与斐波那契数列 : f , = 1, f Z= 1 , 厂 k, = f :+ f 、 +: (k)i)比较可知 , 水 k 于是 , = f k , n k= f k十 :. m Z + m n 一n Z = f全 。 + f ;。,3 f l。,。二 f; 。 = 犷全 。 + f l。 3 (f l 。: , + 厂 ,。 。7 ) 一 (ft。: : +Zf , 。 厂 1。7 + f全 。8。) = 一 (f g。7 “ 一 f l。 。7 f ,。 ,。一 厂护 。3。) 二 f ,。 8 。+ f ,。厂工。 87 一 厂; 。8 二 1 匕+ 1 . 2 一2 2= 一 1 . 例2 . (1 9 刘 , _盛国 议学 奥 林匹克 ) 详 rl 为 斐故 那 契数列 , 试证明有 唯一组正整数 幻乙 , :, 使得O a 。, O今 2时 , f 。 一,: a 乙 ” = 厂 u 一 1 十 f n一2 一72。b “ = 厂 。一 , 一 ( ?:一 1)a乙 ”一+ (,: 一1) a 乙 “一 + 厂 。一 : 一 n一2)a 乙 ”一“ + (,z 一2)a 乙 ”一 “ 一,z a 乙 1 二 a b “一 “(22 一1)b+ (, z 一 2) 一zZ b “ 三 O(m o d 了 7:) 。 山此 矢 日 , (, z一 1)乙+(, :一 2) 一,2 乙 “ 二 O(m o d zn) . (2) 用 4 乘(2 ) 式并利用 (1)式有 4(儿一1)乙+4(陀一2)一4 n b Z = 2(n一1)(Zb一1)一 n (4b “一 1) + sn 一10 二5(?: 一2)二 0(n l od ,z). 因为 ,:一 2 是 任意正整数 , 所 以只 有 ,n = 5适 台 . 再由(1) , Zb一1三O (m o d s) , 注 意到O乙 5, 可得乙 = 3 . 又 由 1 一a b = 1 一3a三 O (m o d匀和O a 0 . 由于( , “一,。: 一m Z)2 = (z: 一zn) “ +m (探 一, 刀)一,n Z 之 = m “ 一优 (祝 一,:)一 (,: 一,n ) 2 “ 夕 如果(阴 , : )是 满足 上 述条件, 一组解 , 并且 (m , , )今(i , t), 那 么( , z一;,;,。:) 也是i译行足 上述条件的一组解 , 等等 . 山于 满足 上 述 条 件的解有限 , 因此进行有限步后一定 可得 到 解( 1 , 1 ) ; 反过来 由解( 1 , 价 一可逐 步得 到满 足上述 条件的全 部解 (其 具体操作过程 为由(m 一 : , 胡)得 出( 。:, ) . 不难着出 , 这些 二, : 组成斐波那契数(每 胡邻 两个是 一 例4 . (第2嘶创MO附加 题) 幂旧多项式尸(x )满 足P(k ) = f k , 一 个9 90次 k = 9 92 , 9叼 , , 1082 , 共 中f 、为斐 波那契数列 . i正明 : P(198勺= f l g3。一 1 二 证明 山N e留to n 一刃r e g o r 刀插值多 项 式 , 得 P(x ) 二 x 一 992 ) “ 。92 ( 其中 , 泛 f 。 : 为数列f 。 。:, f 。 。 3, 中对标号为99 2的项的连续 向前j 注意到盯 ,二 厂 ,+ , 一 厂 ;= 八 - Zfi= 厂, +, 一 f ,= 厂 ,一 厂 ,一工 护, = 厂 i一 , . 山此 , (带)式为 : , f l 。 : 阶差分 . = f ,一 :, , _ /、 一 胃 / 厂、, 一 台、 万一 992 )f 。 。 :一j。 构造一 个991次幂多项式Q , 并满 足 : 对 992(无镇1983, 有Q(k) = k - 同理 , Q(x) = 丫一 992 ) 。 2一 ” 、,/ 这样 , Q(x) = P(x) + ( 组解) : 1 , 2 , 3 , 3 J, 1597 55夕89 , 1 , 144 , 2 3 3 , 5 , 6 , 1 3 , 2 1, 3 3 7 , 610 , . 987 , 令 x = 1 9 33 , 并利用Q(198 3)二 f 工。:, 得 f 工。 3= P(198 3)+1 , 即 P(1 9 33) = f ,。:3 一 1 。 例5 . (第2 2届IMO备选题) 设f 。 为 斐 波 那契效列 . (a) 求出所有的实数对( : , b) , 使得对 于每个 : , 盯 。 十 乙了 。一 , 为数列f 。中的一项。 (的 求出所 有 的正实数对( , v ) , 使 得对每 个 : , 衬盆 + 汀择 1 为数列 f 。 中的 一项 。 , 一 、石 , 一 中;数 - 南翻冲. 冲或蜘钾户一一一一一 一 一 号 - - 一一一一 ,一 一 . 一一 一 , 刃辞jr目设实数 。, 乙使得对于一切自卜 爹价a f + 盯 。、, 是斐波那契数列 中 的 一 几顶 夕 那么对于 :二 1,2,3 , 我们可设 a 十 b = f 。,a十Zb“ 厂扩 , Za+3乙二f了 . 其币m , 耐 , 麒是某三个 自 然数 , 自 上而三式中消去a , b可 得厂 m+ 了 .“ = f厂 . 在斐波那契数列中 , 相邻两项 之和等 于 共 紧接的后一项 夕 即对于任何 自然数k 夕 有厂 k + f 、 ,= f 、十2. 于是可能有以下四种情汉 : 卜21 二 1 a厅 r JI 、 ,污, 才!于 。= 易泪 1 夕 乙= 0 . ,12, 、 不是解 . , 取 允= 4 3卜 以 , l!1 爷 了 a= 尹 。l一 : 一卜厂 乃二 一 f 。 一 十 好 5 = 3 : +sb 3(厂 。一: 十f 。 ) 一三厂 。 一: 衬如 = 浪 二 1 , 抓, 二 3 , (2) 切l , = 刁; /爪, = 1, 。 ! 爪 , 厂 j 几 气从汀 = 引; 二 牙 。一 Zf 上 一: 二 沂 二 一: + 尹 l+ 1. 但在 1 1:) 3 时 , f , 十 厂 。 + : 不是斐波 那 契数列中 t为项 , 故知这对 a, b下是解 . 综上所述 , 其全部解为 : /11 .1 、J 了 ,占 了、 (3) 优十1 , m +2; a二 O , I ) “ 1; a二 1 , a= 矛 m 一2 , b 二 0;b = fm 一: . (m) 3) 一一 一一 , l l 州水 产. 下 、 仇, 二川一 1 , 优刀 二幼+ 1 - (b ) 可按类似(a ) 的方法解决 . J I r 、 、 、 Z 刀 仔 矛胜、 I枕情况(1) 可得 + 右 = z, a+zb = 1, Za干3沙=3, 且】 a= 3 , b =一 1 . 但 3f 。 一 f 。+ 1= 厂 。 十 f 。 一 :, 除非 n= 3 , 否则 , 3 f 。 一 f 。, , 不是斐波到锲数列中的项 , 故 a写 3 , b =一1不是解 . 由情况(3 ) 可得 a 十 乃二厂 。,a +Zb 二 f 。、 l, 解得 a 二 fl n 一:, 乙二尹一 , (水3 ) . 在 优=1时夕 有 a= 1 夕 b = 0 . 在。 = 2时 , 有 a= 0 , 乙二1 - 特别地 , fm 斑n一1 易证 , 这些结果都是解 . 用数学 归纳法可证 = f ;f。+ 。_ 二 沂 : f 二+ 一“ : + f : f m + 。一 : 一卜厂 3f。十。 一3 = f 。一: 厂 。 + f 。一: 厂 二+ , 二a f 。 + 乙f 。+ 工。 由情况 (4) 得 a+ 乙= f 二, a+2 乙=厂 m一, . (二) 2) 解得 。 = f 2 + f m , b =一 f l一 :. (,了 ,)3、 练习题 1 . 试证 : are e tgl仁 are c t已2 + ale e t gs+ ar ee tg13+ aree tg 34+ 式中这些整数是斐波 那契数列 中相间出现的 那 些数 . 它们 还满足递推式 :v 。十1 二 3 : 。 一V n一飞. 2 . 用 来确定录初的梅森数的数列: 。 : 3 , 7 , 47 , 2 207 , 4 8708 一1 7 , , 通常定义 为 a 叶 , = a 盆 一2 . 证明 : 它也可 以定义为 。 、二 f :、午, /f :.