斐波那契相关斐波那契相关

也许更好的阅读体验
前言考试的时候考了到斐波那契的题，于是咱自己推了一些好玩的东西，后来又听dalao讲了些感觉挺有用的东西
通项公式 \(f_0=0\ \ \ f_1=1\ \ \ \ f_2=1\ \\ f_n=f_{n-1}+f_{n-2}\)
我们对它的系数动点手脚
\(f_n=f_2 f_{n-1}+f_1 f_{n-2}\)
再将其迭代一下
\(\begin{aligned}f_{n} &= f_{2}\left( f_{n-2}+f_{n-3}\right) +f_{1}f_{n-2}\\ &=\left( f_{1}+f_{2}\right) f_{n-2}+f_{2}f_{n-3}\\ &=f_{3}f_{n-2}+f_{2}f_{n-3}\end{aligned}\)
如此迭代，我们发现，这个系数也是一个斐波那契数列
所以可以得到
\(f_{n}=f_{n-k+1}f_{k}+f_{n-k}f_{k-1}\)
负项数有时候总想，要是斐波那契有负数项就好了
虽然是负数项，我们仍然要使其满足
\(f_n=f_{n-1}+f_{n-2}\)
考虑逆推
\(f_{n-2}=f_n-f_{n-1}\)
则\(f_{-1}=f_1-f_0=1\)
\(f_{-2}=f_0-f_{-1}=-1\)
可以看出，每次往负数推都是由一个正数减一个负数，或者一个负数减一个正数
那么其每一项的绝对值是不会改变的，并且奇数项都是正的，偶数项都是负的
则我们可以得到这样的递推式
\(f_{-n}=\left( -1\right) ^{n+1}\cdot f_n(n>0)\)
有趣的东西

\(gcd(f_{i+1},f_{i})=1\)
证明
利用更相减损法
\(gcd(f_{i+1},f_{i})=gcd(f_{i+1}-f_i,f_i)=gcd(f_{i-1},f_i)=gcd(f_i,f_{i-1})=\cdots=gcd(f_1,f_2)=1\)
\(f_i\ |\ f_j \Leftrightarrow i\ |\ j\)
当然，\(f_1,f_2\)是特殊情况
\(gcd(f_{n+m},f_n)=gcd(f_n,f_m)\)
\(f^{2}_{n}+f^{2}_{n-1}=f_{2n-1}\)
这个就是用上面的那个递推公式，令\(n=2k-1\)得到的
然后咱在打表的情况下又发现个好玩的
\(f_{n-1}^4≡1(mod)f_n\)
这个是打表的，证明我不会，这是特意写的4次幂
2次幂要分情况
\(f_{n-1}^2≡-1\)\((f_n-1)\)\((mod)f_n\)(n为奇数)
\(f_{n-1}^2≡1(mod)f_n\)(n为偶数)
\((f_n-1)^2≡1(mod)f_n\)
这个并不是只有斐波那契数列才满足
对于所有自然数\(x\)都有\(x^2≡1(mod)(x+1)\)
证明
\(x^2+x≡0(mod)(x+1) \\ x^2≡-x(mod)(x+1) \\ x^2≡1(mod)(x+1)\)
\(f_{k?1}^2?+f_{k?1}f_k??f_k^2?=(?1)^k\)
这个是dalao教的，蒟蒻不会证明
另外，在打表时发现这么一个规律，分了太多情况，这里就不一一赘述了
想要具体知道的话可以去自己打表试试
当n为奇数
\(x\in[1,n-1]\)
- \(f_x\cdot f_{n-1}≡f_{n-x}(mod)f_n\)(x为奇数)
- \(\begin{aligned}f_x\cdot f_{n-1}≡f_n-\sum_{i=1且为奇数}^{n-x}f_i\end{aligned}\)(x为偶数)
当n为偶数时也有类似的公式
并且好像将\(n-1\)变小都有类似的公式....
\(f_{n+2}=1+\sum_{i=1}^{n}f_i\)

没有为什么，打表
下面附上打的表

f[0]=0 f[1]=1f[2]=1f[3]=2f[4]=3f[5]=5 f[6]=8f[7]=13f[8]=21f[9]=34f[10]=55 f[11]=89f[12]=144f[13]=233f[14]=377f[15]=610 f[16]=987f[17]=1597f[18]=2584f[19]=4181f[20]=6765 f[21]=10946 f[22]=17711 f[23]=28657 f[24]=46368 f[25]=75025 //n为奇数 f[2 ]*f[2 ] mod f[3 ]=1 f[1 ]*f[2 ] mod f[3 ]=1 f[4 ]*f[4 ] mod f[5 ]=4 f[3 ]*f[4 ] mod f[5 ]=1 f[2 ]*f[4 ] mod f[5 ]=3 f[1 ]*f[4 ] mod f[5 ]=3 f[6 ]*f[6 ] mod f[7 ]=12 f[5 ]*f[6 ] mod f[7 ]=1 f[4 ]*f[6 ] mod f[7 ]=11 f[3 ]*f[6 ] mod f[7 ]=3 f[2 ]*f[6 ] mod f[7 ]=8 f[1 ]*f[6 ] mod f[7 ]=8 f[8 ]*f[8 ] mod f[9 ]=33 f[7 ]*f[8 ] mod f[9 ]=1 f[6 ]*f[8 ] mod f[9 ]=32 f[5 ]*f[8 ] mod f[9 ]=3 f[4 ]*f[8 ] mod f[9 ]=29 f[3 ]*f[8 ] mod f[9 ]=8 f[2 ]*f[8 ] mod f[9 ]=21 f[1 ]*f[8 ] mod f[9 ]=21 f[10]*f[10] mod f[11]=88 f[9 ]*f[10] mod f[11]=1 f[8 ]*f[10] mod f[11]=87 f[7 ]*f[10] mod f[11]=3 f[6 ]*f[10] mod f[11]=84 f[5 ]*f[10] mod f[11]=8 f[4 ]*f[10] mod f[11]=76 f[3 ]*f[10] mod f[11]=21 f[2 ]*f[10] mod f[11]=55 f[1 ]*f[10] mod f[11]=55 f[12]*f[12] mod f[13]=232 f[11]*f[12] mod f[13]=1 f[10]*f[12] mod f[13]=231 f[9 ]*f[12] mod f[13]=3 f[8 ]*f[12] mod f[13]=228 f[7 ]*f[12] mod f[13]=8 f[6 ]*f[12] mod f[13]=220 f[5 ]*f[12] mod f[13]=21 f[4 ]*f[12] mod f[13]=199 f[3 ]*f[12] mod f[13]=55 f[2 ]*f[12] mod f[13]=144 f[1 ]*f[12] mod f[13]=144 f[14]*f[14] mod f[15]=609 f[13]*f[14] mod f[15]=1 f[12]*f[14] mod f[15]=608 f[11]*f[14] mod f[15]=3 f[10]*f[14] mod f[15]=605 f[9 ]*f[14] mod f[15]=8 f[8 ]*f[14] mod f[15]=597 f[7 ]*f[14] mod f[15]=21 f[6 ]*f[14] mod f[15]=576 f[5 ]*f[14] mod f[15]=55 f[4 ]*f[14] mod f[15]=521 f[3 ]*f[14] mod f[15]=144 f[2 ]*f[14] mod f[15]=377 f[1 ]*f[14] mod f[15]=377 f[16]*f[16] mod f[17]=1596 f[15]*f[16] mod f[17]=1 f[14]*f[16] mod f[17]=1595 f[13]*f[16] mod f[17]=3 f[12]*f[16] mod f[17]=1592 f[11]*f[16] mod f[17]=8 f[10]*f[16] mod f[17]=1584 f[9 ]*f[16] mod f[17]=21 f[8 ]*f[16] mod f[17]=1563 f[7 ]*f[16] mod f[17]=55 f[6 ]*f[16] mod f[17]=1508 f[5 ]*f[16] mod f[17]=144 f[4 ]*f[16] mod f[17]=1364 f[3 ]*f[16] mod f[17]=377 f[2 ]*f[16] mod f[17]=987 f[1 ]*f[16] mod f[17]=987 f[18]*f[18] mod f[19]=4180 f[17]*f[18] mod f[19]=1 f[16]*f[18] mod f[19]=4179 f[15]*f[18] mod f[19]=3 f[14]*f[18] mod f[19]=4176 f[13]*f[18] mod f[19]=8 f[12]*f[18] mod f[19]=4168 f[11]*f[18] mod f[19]=21 f[10]*f[18] mod f[19]=4147 f[9 ]*f[18] mod f[19]=55 f[8 ]*f[18] mod f[19]=4092 f[7 ]*f[18] mod f[19]=144 f[6 ]*f[18] mod f[19]=3948 f[5 ]*f[18] mod f[19]=377 f[4 ]*f[18] mod f[19]=3571 f[3 ]*f[18] mod f[19]=987 f[2 ]*f[18] mod f[19]=2584 f[1 ]*f[18] mod f[19]=2584//偶数情况 f[1 ]*f[0 ] mod f[2 ]=0 f[3 ]*f[2 ] mod f[4 ]=2 f[2 ]*f[2 ] mod f[4 ]=1 f[1 ]*f[2 ] mod f[4 ]=1 f[5 ]*f[4 ] mod f[6 ]=7 f[4 ]*f[4 ] mod f[6 ]=1 f[3 ]*f[4 ] mod f[6 ]=6 f[2 ]*f[4 ] mod f[6 ]=3 f[1 ]*f[4 ] mod f[6 ]=3 f[7 ]*f[6 ] mod f[8 ]=20 f[6 ]*f[6 ] mod f[8 ]=1 f[5 ]*f[6 ] mod f[8 ]=19 f[4 ]*f[6 ] mod f[8 ]=3 f[3 ]*f[6 ] mod f[8 ]=16 f[2 ]*f[6 ] mod f[8 ]=8 f[1 ]*f[6 ] mod f[8 ]=8 f[9 ]*f[8 ] mod f[10]=54 f[8 ]*f[8 ] mod f[10]=1 f[7 ]*f[8 ] mod f[10]=53 f[6 ]*f[8 ] mod f[10]=3 f[5 ]*f[8 ] mod f[10]=50 f[4 ]*f[8 ] mod f[10]=8 f[3 ]*f[8 ] mod f[10]=42 f[2 ]*f[8 ] mod f[10]=21 f[1 ]*f[8 ] mod f[10]=21 f[11]*f[10] mod f[12]=143 f[10]*f[10] mod f[12]=1 f[9 ]*f[10] mod f[12]=142 f[8 ]*f[10] mod f[12]=3 f[7 ]*f[10] mod f[12]=139 f[6 ]*f[10] mod f[12]=8 f[5 ]*f[10] mod f[12]=131 f[4 ]*f[10] mod f[12]=21 f[3 ]*f[10] mod f[12]=110 f[2 ]*f[10] mod f[12]=55 f[1 ]*f[10] mod f[12]=55 f[13]*f[12] mod f[14]=376 f[12]*f[12] mod f[14]=1 f[11]*f[12] mod f[14]=375 f[10]*f[12] mod f[14]=3 f[9 ]*f[12] mod f[14]=372 f[8 ]*f[12] mod f[14]=8 f[7 ]*f[12] mod f[14]=364 f[6 ]*f[12] mod f[14]=21 f[5 ]*f[12] mod f[14]=343 f[4 ]*f[12] mod f[14]=55 f[3 ]*f[12] mod f[14]=288 f[2 ]*f[12] mod f[14]=144 f[1 ]*f[12] mod f[14]=144 f[15]*f[14] mod f[16]=986 f[14]*f[14] mod f[16]=1 f[13]*f[14] mod f[16]=985 f[12]*f[14] mod f[16]=3 f[11]*f[14] mod f[16]=982 f[10]*f[14] mod f[16]=8 f[9 ]*f[14] mod f[16]=974 f[8 ]*f[14] mod f[16]=21 f[7 ]*f[14] mod f[16]=953 f[6 ]*f[14] mod f[16]=55 f[5 ]*f[14] mod f[16]=898 f[4 ]*f[14] mod f[16]=144 f[3 ]*f[14] mod f[16]=754 f[2 ]*f[14] mod f[16]=377 f[1 ]*f[14] mod f[16]=377 f[17]*f[16] mod f[18]=2583 f[16]*f[16] mod f[18]=1 f[15]*f[16] mod f[18]=2582 f[14]*f[16] mod f[18]=3 f[13]*f[16] mod f[18]=2579 f[12]*f[16] mod f[18]=8 f[11]*f[16] mod f[18]=2571 f[10]*f[16] mod f[18]=21 f[9 ]*f[16] mod f[18]=2550 f[8 ]*f[16] mod f[18]=55 f[7 ]*f[16] mod f[18]=2495 f[6 ]*f[16] mod f[18]=144 f[5 ]*f[16] mod f[18]=2351 f[4 ]*f[16] mod f[18]=377 f[3 ]*f[16] mod f[18]=1974 f[2 ]*f[16] mod f[18]=987 f[1 ]*f[16] mod f[18]=987 f[19]*f[18] mod f[20]=6764 f[18]*f[18] mod f[20]=1 f[17]*f[18] mod f[20]=6763 f[16]*f[18] mod f[20]=3 f[15]*f[18] mod f[20]=6760 f[14]*f[18] mod f[20]=8 f[13]*f[18] mod f[20]=6752 f[12]*f[18] mod f[20]=21 f[11]*f[18] mod f[20]=6731 f[10]*f[18] mod f[20]=55 f[9 ]*f[18] mod f[20]=6676 f[8 ]*f[18] mod f[20]=144 f[7 ]*f[18] mod f[20]=6532 f[6 ]*f[18] mod f[20]=377 f[5 ]*f[18] mod f[20]=6155 f[4 ]*f[18] mod f[20]=987 f[3 ]*f[18] mod f[20]=5168 f[2 ]*f[18] mod f[20]=2584 f[1 ]*f[18] mod f[20]=2584