也许更好的阅读体验

前言

考试的时候考了到斐波那契的题，于是咱自己推了一些好玩的东西，后来又听dalao讲了些感觉挺有用的东西

通项公式

$f_0=0f_1=1f_2=1f_n=f_{n-1}+f_{n-2}$f0​=0   f1​=1    f2​=1 fn​=fn−1​+fn−2​
我们对它的系数动点手脚
$f_n=f_2{f}_{n-1}+f_1{f}_{n-2}$fn​=f2​fn−1​+f1​fn−2​
再将其迭代一下
$\begin{array}{cc}{\displaystyle f_n}& {\displaystyle =f_2(f_{n-2}+f_{n-3})+f_1{f}_{n-2}}\\ {\displaystyle }& {\displaystyle =(f_1+f_2)f_{n-2}+f_2{f}_{n-3}}\\ {\displaystyle }& {\displaystyle =f_3{f}_{n-2}+f_2{f}_{n-3}}\end{array}$fn​​=f2​(fn−2​+fn−3​)+f1​fn−2​=(f1​+f2​)fn−2​+f2​fn−3​=f3​fn−2​+f2​fn−3​​
如此迭代，我们发现，这个系数也是一个斐波那契数列
所以可以得到
$f_n=f_{n-k+1}{f}_k+f_{n-k}{f}_{k-1}$fn​=fn−k+1​fk​+fn−k​fk−1​

负项数

有时候总想，要是斐波那契有负数项就好了
虽然是负数项，我们仍然要使其满足
$f_n=f_{n-1}+f_{n-2}$fn​=fn−1​+fn−2​
考虑逆推
$f_{n-2}=f_n-f_{n-1}$fn−2​=fn​−fn−1​
则 $f_{-1}=f_1-f_0=1$f−1​=f1​−f0​=1
$f_{-2}=f_0-f_{-1}=-1$f−2​=f0​−f−1​=−1
可以看出，每次往负数推都是由一个正数减一个负数，或者一个负数减一个正数
那么其每一项的绝对值是不会改变的，并且奇数项都是正的，偶数项都是负的
则我们可以得到这样的递推式
$f_{-n}={(-1)}^{n+1}\cdot f_n(n\>0)$f−n​=(−1)n+1⋅fn​(n>0)

有趣的东西

• $gcd(f_{i+1},f_i)=1$gcd(fi+1​,fi​)=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$gcd(fi+1​,fi​)=gcd(fi+1​−fi​,fi​)=gcd(fi−1​,fi​)=gcd(fi​,fi−1​)=⋯=gcd(f1​,f2​)=1

• $f_i\mid f_j\iff i\mid j$fi​ ∣ fj​⇔i ∣ j
  当然， $f_1,f_2$f1​,f2​是特殊情况

• $gcd(f_{n+m},f_n)=gcd(f_n,f_m)$gcd(fn+m​,fn​)=gcd(fn​,fm​)

• $f_n^2+f_{n-1}^2=f_{2n-1}$fn2​+fn−12​=f2n−1​
  这个就是用上面的那个递推公式，令 $n=2k-1$n=2k−1得到的

• 然后咱在打表的情况下又发现个好玩的
  $f_{n-1}^4\equiv 1\left(mod\right)f_n$fn−14​≡1(mod)fn​
  这个是打表的，证明我不会，这是特意写的4次幂
  2次幂要分情况
  $f_{n-1}^2\equiv -1$fn−12​≡−1 $(f_n-1)$(fn​−1) $\left(mod\right)f_n$(mod)fn​(n为奇数)
  $f_{n-1}^2\equiv 1\left(mod\right)f_n$fn−12​≡1(mod)fn​(n为偶数)

• $(f_n-1{)}^2\equiv 1(mod)f_n$(fn​−1)2≡1(mod)fn​
  这个并不是只有斐波那契数列才满足
  对于所有自然数 $x$x都有 $x^2\equiv 1\left(mod\right)(x+1)$x2≡1(mod)(x+1)
  证明
  $x^2+x\equiv 0\left(mod\right)(x+1)x^2\equiv -x\left(mod\right)(x+1)x^2\equiv 1\left(mod\right)(x+1)$x2+x≡0(mod)(x+1)x2≡−x(mod)(x+1)x2≡1(mod)(x+1)

• $f_{k-1}^2+f_{k-1}{f}_k-f_k^2=(-1{)}^k$fk−12​​+fk−1​fk​​−fk2​​=(−1)k
  这个是dalao教的，蒟蒻不会证明

• 另外，在打表时发现这么一个规律，分了太多情况，这里就不一一赘述了
  想要具体知道的话可以去自己打表试试
  当n为奇数
  $x\in [1,n-1]$x∈[1,n−1]

  • $f_x\cdot f_{n-1}\equiv f_{n-x}\left(mod\right)f_n$fx​⋅fn−1​≡fn−x​(mod)fn​(x为奇数)
  • $\begin{array}{c}{\displaystyle f_x\cdot f_{n-1}\equiv f_n-\sum _{i=1且为奇数}^{n-x}{f}_i}\end{array}$fx​⋅fn−1​≡fn​−i=1且为奇数∑n−x​fi​​(x为偶数)

  当n为偶数时也有类似的公式
  并且好像将 $n-1$n−1变小都有类似的公式…

• $f_{n+2}=1+{\sum }_{i=1}^n{f}_i$fn+2​=1+∑i=1n​fi​
  没有为什么，打表

下面附上打的表

f[0]=0
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   f[13]=233   f[14]=377   f[15]=610 
f[16]=987   f[17]=1597  f[18]=2584  f[19]=4181  f[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

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧