Update on 2019.10.9 增加了斐波那契生成函数
Part1:斐波那契数列的定义
斐波那契数列(Fibonacci sequence)是从所谓的兔子繁殖问题定义的.假设每只兔子过(2)个月就有繁殖能力,每个月产下一只兔子.如果兔子不死,那么在第(n)个月你有多少只兔子?
设第(n)个月有(F_n)只兔子,显然(F_1=F_2=1).根据打表找规律可得
[F_n=F_{n-1}+F_{n-2}(nge3).
]
该数列从第三项起m每一项都是前两项的和.这就是斐波那契数列.根据计算可得,斐波那契数列的前几项是
[F_1=1,F_2=1,F_3=2,F_4=3,F_5=5,F_6=8,F_7=13,F_8=21,F_9=34,F_{10}=55,F_{11}=89,F_{12}=144,dots
]
Part2:通项公式
根据定义,斐氏数列是一个线性递推数列.其特征方程为
[x^2=x+1
]
因此有(x_1=frac{1-sqrt 5}2,x_2=frac{1+sqrt 5}2)(这两个数就是我们后面要介绍的黄金分割率).设(F_n=C_1x_1^n+C_2x_2^n),
(ecause F_1=F_2=1)
( herefore C_1x_1+C_2x_2=C_1x_1^2+C_2x_2^2=1)
解得(C_1=frac1{sqrt5},C_2=-frac1{sqrt5}).
所以斐波那契数列的通项公式为
[F_n=frac1{sqrt5}left[left(frac{1+sqrt5}2
ight)^n-left(frac{1-sqrt5}2
ight)^n
ight]
]
多神奇啊!斐波那契数列竟可以被无理数表示出.
Part3:斐波那契数列的性质
(1.)邻项方差:
[F_{n-1}cdot F_{n+1}-F_n^2=(-1)^n
]
用数学归纳法易证.
(2.)通项求和:
[sum_{i=1}^n F_n=F_{n+2}-2
]
证明:因
[F_1=F_2,\
F_2=F_3-F_1,\
dots,\
F_n=F_{n+1}-F{n-1}
]
所以原式成立.
(3.)奇数项求和:
[sum_{i=1}^n F_{2i-1}=F_{2n}
]
证明:因
[F_1=F_2,\
F_3=F_4-F_2,\
dots,\
F_{2n-1}=F_{2n}-F_{2n-2}
]
所以原式成立.
(4.)偶数项求和:
[sum_{i=1}^n F_{2i}=F_{2n+1}-1
]
把通项求和公式和奇数项求和公式减一下就好了.
(5.)平方求和:
[sum_{i=1}^n F_{i}^2=F_{n+1}F_n
]
仿照上例证明展开即可.更直观地,
如图,易知正方形面积和=边长之积,也就是上述平方和公式.
(6.)两倍项关系
[frac{F_{2n}}{F_n}=F_{n-1}+F_{n+1}
]
展开既得.
(7.)倒数求和
[sum_{i=1}^nfrac1{F_{i-1}+F_{i+1}}=1-frac1{F_{n-1}F_n}\
sum_{i=1}^nfrac{F_i}{F_{i-1}F_{i+1}}=2-frac1{F_{n-1}}-frac1{F_n}
]
裂项即可.证明略.
(8.)三倍项关系
[F_{3n}=F_{n+1}^3+F_n^3-F_{n-1}^3
]
证明略.
(9.)公约数
[gcd(F_n,F_m)=F_{gcd(n,m)}
]
证明:欲证(gcd(F_n,F_m)=F_{gcd(n,m)}),只需证(gcd(F_{n+m},F_n)=gcd(F_m,F_n)).又
[egin{align}
gcd(F_{n+m},F_n)
&=gcd(F_{n+1}F_m+F_nF_{m-1},F_n)\
&=gcd(F_{n+1}F_m,F_n)\
&=gcd(F_{n+1},F_n)cdotgcd(F_m,F_n)\
&=gcd(F_m,F_n)=gcd(F_m,F_n)
end{align}
]
故原式成立.
作为该结论的直接推论,有(gcd(F_n,F_{n+1})=1).即斐氏数列的邻项互质.
(10.)带权和
[sum_{i=1}^n icdot F_i=ncdot F_{n+2}-F_{n+3}+2
]
证明:运用数学归纳法.当(n=1)时,命题成立.
设当(n=k)时,命题成立,令(S_i=sumlimits_{i=1}^nicdot F_i),则
[egin{align}
S_{k+1}&=S_k+F_{k+1}cdot(k+1)\
&=kcdot F_{k+2}-F_{k+3}+2+F_{k+1}cdot (k+1)\
&=kcdot F_{k+3}-F_{k+3}+2+F_{k+1}\
&=kcdot F_{k+3}-F_{k+2}+2\
end{align}
]
所以原命题成立.
Part4:黄金分割率
将一条线段分成两部分,使得其中一段的长度与全长之比,等于另一段与该线段长度之比,这,就是黄金分割率.
根据其定义,我们设(varphi=x)((varphi)通常表示黄金分割率),则
[x^2+x-1=0
]
解得
[x_1=frac{sqrt5-1}2,x_2=frac{-sqrt5-1}2( ext{舍})
]
因此,(varphi=frac{sqrt5-1}2approx 0.618).
下面来讨论(varphi)的性质.记(hat varphi=frac{sqrt5+1}2),称为(varphi)的共轭.
(1.varphi=frac1{hat{varphi}}).这是因为
[varphicdothat{varphi}=frac{sqrt5-1}2frac{sqrt5+1}2=1
]
(2.varphi+varphi^2=1).由定义既得.
(3.varphi+1=frac1{varphi}).由(2)可推得.
Part5:斐波那契数列与黄金分割率
我们尝试除斐氏数列的邻项.有
[frac{F_1}{F_2}=1,frac{F_2}{F_3}=0.5,frac{F_3}{F_4}approx0.667,frac{F_4}{F_5}=0.6,frac{F_5}{F_6}=0.625,dots
]
可以发现,相邻两项之比不断趋近于黄金分割率.更直观地,
[frac{F_{20}}{F_{21}}approx0.618033985017358;\
varphiapprox0.6180339887498949
]
直到第(10)位才出现不同.那么,是否有
[lim_{n oinfty}frac{F_n}{F_{n+1}}=varphi
]
呢?答案是肯定的.
因
[F_n=F_{n-1}+F_{n-2}
]
两边同除(F_{n+1})得
[frac{F_n}{F_{n+1}}+1=frac{F_{n+2}}{F_{n+1}}
]
设(limlimits_{n oinfty}frac{F_n}{F_{n+1}})存在(存在性是显然的)且等于(x),则
[lim_{n oinfty}frac{F_n}{F_{n+1}}=lim_{n oinfty}frac{F_{n+1}}{F_{n+2}}=x
]
所以
[x+1=frac1x
]
又(x>0),所以(x=varphi).
Part6:斐波那契数列的生成函数
我们要求其生成函数,即
[G(x)=F_0+F_1x+F_2x^2+dots+F_nx^n+dots=sum_{n=0}^{infty}F_nx^n
]
我们知道有
[F_n=frac1{sqrt5}left[left(frac{1+sqrt5}2
ight)^n-left(frac{1-sqrt5}2
ight)^n
ight]
]
故
[egin{align}
G(x)&=sum_{n=0}^{infty}F_nx^n=sum_{n=0}^{infty}F_n=frac1{sqrt5}left[left(frac{1+sqrt5}2
ight)^n-left(frac{1-sqrt5}2
ight)^n
ight]cdot x^n\
&=frac1{sqrt5}left[sum_{n=0}^nleft(frac{1+sqrt5}2cdot x
ight)^n+sum_{n=0}^{infty}left(frac{1-sqrt5}2cdot x
ight)
ight]\
&=frac1{sqrt5}left(frac1{frac{1+sqrt5}2x}+frac1{frac{1-sqrt5}2x}
ight)\
&=frac1{sqrt5}frac{sqrt5}{1-x-x^2}\
&=frac1{1-x-x^2}
end{align}
]
于是我们知道了斐波那契数列的生成函数为
[G(x)=frac1{1-x-x^2}
]
本文完