数论概论读书笔记 39.斐波那契与线性递归序列

斐波那契与线性递归序列

比内公式 斐波那契序列$F_n$用递归公式描述如下: $$ F_1=F_2=1,\quad F_n=F_{n-1}+F_{n-2}\quad ,n=3,4,5,... $$ 则斐波那契序列的第$n$项可用公式 $$ F_n=\frac{1}{\sqrt{5}}\left{ \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right} $$ 给出。

斐波那契序列模m

对$m=2,3,4,5,6...$进行尝试,会发现在每一种情形下斐波那契数列最后都开始循环。

即,当计算斐波那契序列模$m$时,最后总会发现两个连续的1出现,然后序列开始循环。

即,存在整数$N\ge 1$使得,$F_{n+N}\equiv F_n \ (mod \ m)$ 对所有的$n=1,2,...$

最小的这样的整数$N$叫做斐波那契序列模$m$的周期,记为$N(m)$。

img





评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)