一生小兔问题引起的
十三世纪初，意大利比萨的一位叫伦纳德，绰号为斐波那契(Fibonacci，1170～1250)*的数学家，在一本题为《算盘书》**的数学著作中，提出下面一个有趣的问题：兔子出生以后两个月就能生小免，若每次不多不少恰好生一对（一雌一雄），假如养了初生的小兔一对，试问一年以后共可有多少对兔子（如果生下的小兔都不死的话）？我们来推算下．如图11：第一个月：只有一对小兔；第二个月：小免子没有长成不会生殖，仍然只有一一对兔子；第三个月：这对兔子生了一对小兔，这时共Fibonacci是filiusBonacci的简写，意思是“波那契之子”*这儿的“算盘”是指用来计算的沙盘，不是我国的算盘。《算盘书》（LiberAbaci，1202)是一本研究算术（及代数）的书籍，abacus直译为“算盘”，它源自希腊文aBa.这是对后几个世纪欧洲数学发展起着重要作用的书籍，也是向欧洲人传播印度一一阿拉伯字码的最早论著
月份兔子数（对）121324355注：○表示未成熟小兔子，表示成熟免子图1-1有两对兔子；第四个月：老兔子又生了一对小兔，而上月出生的小兔还未成熟，这时共有三对兔子，第五个月：这时已有两对兔子可以生殖（原来的老兔和第三个月出生的小兔），于是生了两对小兔，这时共有五对免子，如此推算下去，我们不难得出下面的结果（这里列成一张表）：月份数四五兔子数(对）13/21/34552311从表中可知：一年后（第十三个月时）共有兔子233对
用这种办法来推算，似乎有些“笨”，而且越往后越使人觉得复杂。有无简单办法推算？我们把上表中下面一列数用（u）表示（有时也用（F）表示，下标n表示月份数，兔子数可视为月份数的函数），则它们被称为斐波那契数列，记[un):1,1,2,3,5,8,13,21,34,..且un称为斐波那契数。1634年数学家奇拉特发现（那已是斐氏死后近四百年的事了）：斐波那契数列之间有如下递推关系：unti=un+un-1其实这个式子并不难理解，试想：第n+1个月时的兔子可分为两类：一类是第n个月时的兔子，另一类是当月新出生的小兔，而这些小兔数恰好是第n一1个月时兔子数（它们到第n+1个月时均可生殖）。由于这一发现，生小兔问题引起了人们的极大兴趣，首先计算这列数方便多了：人们不仅可以轻而易举地算出一年以后的兔子数，甚至可以算出两年，三年、以后的兔子数（这要用原来办法推算恐怕是繁琐至极），再者由于人们继续对这个数列探讨，又发现了它的许多奇特的性质
比如它们项数间的更一般关系是：Um+n = Un-i Um + Unum+i (m.nEN)我们可以用数学归纳法证明如下（对m归纳)：1) m=1时,unt1=un-1 + ux=un-iui+unuzs即命题真（注意到=z=1)类似地我们可以证明㎡=2时命题也真，即un+=Un-iuz+Unus.2）设m≤k时真，今考虑m=k+1的情形:由归纳假设有Un+k=1=Un-iuk-1+unuk及un+k=un-iuk+unuc+1，两式两边相加有：n+k-++ux+n=Un-(ur++ux)+un(uk+ukti)注意到：Un+k+1=un+k-1+Un+k及uk-1+uk=Uk+1,Uk+Ukr=ux+2,故un+k+=un-iuk++unuk+2即m=k+1时亦真，从而对任何自然m命题成立（这里用的是第二归纳法）。1680年，卡西尼发现了下面关于斐氏数列项间重要的关系式：un+iun-1-un (-1)n它可以直接用数学归纳法去证明，但更为巧妙的证明方法，可由矩阵恒等式1In=(un+)un(*)unun-10
的简单证明得到：1）n=2时，用矩阵乘法规则：(1 ) =(1)(1)=(11)=(μu)2）设n=k时结论真，即(1 )" (ut u)+今考虑n=k+1的情形，(1)*-(1)(1)-( )(1)-2.. +*1: :.1(u++UkU+)=(uk+z uk+1uk+uk-ruk(uktiuk此即说n=k+1时命题亦真，从而对任何自然数（*）式成立。对（*）两边取行列式再展开化简后即为：un+iun-1-- un = (-1)n从这个关系式中我们还可以发现，un与un+互质，即(un,un+1）=1（这里(a,b)表示 a、b的最大公因子）因为从式中可见：un与un+1的任何公因子，都是(一1)"的一个因子。上面关系式的推广形式是：un-hum+k-unum(-1)"um-n-kuk
它的证明将要用到后面我们将提到的一个公式。至于它的讨论，我们在以后给出。注利用等式（*）我们还可以证明前面的结论：Um+n=um Un+1 +um-1un这只须注意到：-)-(1)" (1)um+n(um+n-1 Umtn.()-(. t)unun-由矩阵乘法后再比较两边矩阵中左上角第一元素即可。2十八世纪初，棣美佛在其所著《分析集锦》+MiscellaneaAnalytica）中，给出斐波那契数列的通项表达式（又称为“封闭形式”，但它不唯一):[(1+)"-(1-)un=它又称为比内公式，这是以最初证明它的数学家比内命名的，它又是一个十分耐人寻味的等式：式左是正整数，而式右则是由无理数来表达的。公式的重要性我们不说即明，因为斐氏数列的许多重要性质的证明都是通过它来完成的，我们先来用数学归纳法证明这个等式，稍后我们还将给出它的另外一种证明。1）n=1时，直接验算即可。8
2）设n<k时结论真，今考虑到n=k+1的情形：注意到+=+-及[(I)-())IUk +Uk-125[(1+y)""-(y)")(1+)(+1)2)**(1-下+1)V5[(I+y)"(1+)(1)(1))[(yE)"-(1-y)"从而命题对n=k+1时真，因而对任何自然数公式都成立。1753年，希姆松发现斐氏数列中前后两项u，和unt之比un/unta是连分数17
的第n 个渐近分数。这一点我们后文还要叙及。1884年，法国数学家拉姆利用斐波那契数列证明：应用辊转相除（欧几里得除法）法的步数（即辗转相除的次数）不大于较小的那个数的位数的五倍。这是斐波那契数列的第一次有价值的应用（证明请见后文），1876年，数学家鲁卡斯发现：方程 --1=0的两个根=12T,=1-巨的任何次方暴的线性组合都满足关2系式：un+= un + un-1同时他还发现并证明了下述结论：一个数整除um和un的充要条件是这个数是ua的因子，这里 d=(m,n)。特别地，(um,Un)=U(mn).证我们已经证明了关系式，umtn=umunt+um-iun由之我们可有：um和un的任何公因子也是um+#的因子，且um+n和un的任何公因子:.10