斐波那契数列的一些引理和相关题目 本blog还没有写完,后面将持续更新qwq
斐波那契数列,是一个经典的递推数列。在实际生活中有很多应用。
我们一般都知道它的递推公式:
F[1]=1,F[2]=1,...,F[n]=F[n-1]+Fn-2
或者说通项公式......(这个我是不会,而且一半也用不到)
下面补充一些引理,做题的时候可能会用到。
(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}))
(=......)
(=gcd(2,1))
(=1)
得证
(F_{m+n}=F_{m-1}*F_n+F_{m}*F_{n+1})
证明:
(F_{m+n})
(=F_{m+n-1}+F_{m+n-2})
(=2*F_{m+n-2}+F_{m+n-3})
(=3*F_{m+n-3}+2*F_{m+n-4})
(=5*F_{m+n-4}+3*F_{m+n-5})
(=......)
(=F_{a-1}*F_{m+n-a}+F_{a}*F_{m+n-a+1})
设 (k1=a-1,k2=m+n-a+1)
因为
(k1+k2=a-1+m+n-a+1=m+n)
所以
(F_{k1+k2}=F_{k1}*F_{k2-1}+F_{k1+1}*F_{k2})
得证
(gcd(F_i,F_j)=F_{gcd(i,j)})
(sum_{i=1}^nF_i=F_{n+2}-1)
证明:
(sum_{i=1}^nF_i)
(=F_2+F_1+F_2+....+F_n-1)
(=F_3+F_2+...+F_n-1)
(=...)
(=F_{n+2}-1)
(sum_{i=1}^n i imes F_i=n imes F_{n+2}-F_{n+3}+2)
证明:
(sum_{i=1}^n i imes F_i)
(=n imes sum_{i=1}^nF_i-(n-1) imes F_1-(n-2) imes F_2-...-1 imes F_{n-1})
(=n imes sum_{i=1}^nF_i-(sum_{i=1}^{n-1}F_i+sum_{i=1}^{n-2}F_i+...+sum_{i=1}^2F_i+F_1))
(=n imes sum_{i=1}^nF_i-(F_{n+1}-1+F_{n}-1+...+F_4-1+F_1))
(=n imes sum_{i=1}^nF_i-(F_{n+1}+F_{n}+...+F_4+F_3+F_2+F_1-3-(n-2)))
(=n imes sum_{i=1}^nF_i-F_{n+3}+1+n+1)
(=n imes F_{n+2}-F_{n+3}+2)
斐波那契数列经常用在一些结论题里,或者和矩阵快速幂搭配使用。
下面贴上几道相关题目:
萨塔尼亚的期末考试
斐波那契公约数
斐波那契数列
斐波那契
粉樱花之恋