$$\newcommand\comb[2]{C_{#1}^{#2}}$$

斐波那契数列

令$F(1)=F(2)=1$，斐波那契数列的第$i$项为$F(i)=F(i-1)+F(i-2)$

前置知识

二次剩余

等比数列求和公式: $\large S_n=a_1\frac{1-q^n}{1-q}=\frac{a_1-a_nq}{1-q}\ (q\ne 1)$

通项公式

$$\large{F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]}$$

通项求解过程见参考资料。

狠人解法

由递推公式可知

$$\begin{pmatrix}F_n \\ F_{n+1}\end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 1 & 1\end{pmatrix}\begin{pmatrix}F_{n-1} \\ F_{n}\end{pmatrix}$$

对角化得

$$\begin{pmatrix} 0 & 1 \\ 1 & 1\end{pmatrix}=\left(\begin{array}{cc}-1+\sqrt{5} & -1-\sqrt{5} \\2 & 2\end{array}\right)\left(\begin{array}{cc}\frac{1+\sqrt{5}}{2} & 0 \\0 & \frac{1-\sqrt{5}}{2}\end{array}\right)\left(\begin{array}{cc}\frac{1}{2 \sqrt{5}} & \frac{1+\sqrt{5}}{4 \sqrt{5}} \\-\frac{1}{2 \sqrt{5}} & \frac{-1+\sqrt{5}}{4 \sqrt{5}}\end{array}\right)$$

因此

$$F_n=\begin{pmatrix} 1 & 0\end{pmatrix}\left(\begin{array}{cc}-1+\sqrt{5} & -1-\sqrt{5} \\2 & 2\end{array}\right)\left(\begin{array}{cc}(\frac{1+\sqrt{5}}{2})^n & 0 \\0 & (\frac{1-\sqrt{5}}{2})^n\end{array}\right)\left(\begin{array}{cc}\frac{1}{2 \sqrt{5}} & \frac{1+\sqrt{5}}{4 \sqrt{5}} \\-\frac{1}{2 \sqrt{5}} & \frac{-1+\sqrt{5}}{4 \sqrt{5}}\end{array}\right)\begin{pmatrix}0 \\ 1\end{pmatrix}$$

计算得

$$\begin{aligned}F_n&=\begin{pmatrix} -1+\sqrt{5} & -1-\sqrt{5}\end{pmatrix}\begin{pmatrix}(\frac{1+\sqrt{5}}{2})^n & 0 \\ 0 & (\frac{1-\sqrt{5}}{2})^n\end{pmatrix}\begin{pmatrix}\frac{1+\sqrt{5}}{4\sqrt{5}} \\\frac{\sqrt{5}-1}{4\sqrt{5}}\end{pmatrix}\\&=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}\end{aligned}$$

巧妙解法

核心：将相邻三项的递推关系转化为相邻两项的递推关系，进一步求出通项

记$a_i=F(i)$

构造$a_n+xa_{n-1}=y(a_{n-1}+xa_{n-2})$

由$a_n=a_{n-1}+a_{n-2}$可知$\left\{\begin{aligned} x&=\frac{\sqrt{5}-1}{2}\\ y&=\frac{\sqrt{5}+1}{2} \end{aligned}\right.$为方程的一组解

令$b_n=a_n+\frac{\sqrt{5} - 1}{2}a_{n-1}$，则$b_n=\frac{\sqrt{5}+1}{2}b_{n-1}$，$b_1=1$，$b_n=(\frac{\sqrt{5}+1}{2})^{n-1}$

至此，我们得到$a_n+\frac{\sqrt{5}-1}{2}a_{n-1}=(\frac{\sqrt{5}+1}{2})^{n-1}$，成功将相邻三项递推关系转化为相邻两项的递推关系。

继续拆分，设$a_n+xb_n=y(a_{n-1}+xb_{n-1})$

由上述过程可知，必有$y=-\frac{\sqrt{5}-1}{2}$，进而解得$x=-\frac{\sqrt{5}+1}{2\sqrt{5}}$

设$c_n=a_n-\frac{\sqrt{5}+1}{2\sqrt{5}}b_n$，有$c_n=\frac{1-\sqrt{5}}{2}c_{n-1}$，$c_1=\frac{\sqrt{5}-1}{2\sqrt{5}}$，$c_n=\frac{\sqrt{5}-1}{2\sqrt{5}}(\frac{1-\sqrt{5}}{2})^{n-1}$

由此，可得$a_n=c_n+\frac{\sqrt{5}+1}{2\sqrt{5}}b_n$

代入可得

$$a_n=\frac{1}{2\sqrt{5}}\left(-2(\frac{1-\sqrt{5}}{2})^{n}+2(\frac{1+\sqrt{5}}{2})^n\right)$$

---

PS：化简太复杂了，直接心态爆炸

Fibonacci数列的幂和

形如“给定$n,k$，求$S=(F_1^k+F_2^k+\cdots F_n^k)\mod {(10^9+7)}$”的问题

例题 HDU 6755

题意：$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}$

给定个数字$N,C,K$，求

$$F_{0}+F_{C}+F_{2C}+\cdots + F_{NC}$$

（即是求$\sum\limits_{i=0}^N{(\large F_{iC})^K}$）

$(1\le N,C\le 10^{18},1\le K \le 10^5)$

答案对$1000000009$求余

解析

易知$x^2\equiv 5\mod {(10^9 + 9)}$的一个解为$383008016$（下文省略mod 符号）

记$t=\frac{1}{\sqrt 5}\equiv 276601605$

已知

$$F_i=\frac{1}{\sqrt 5}({(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n})$$

令$a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}$

可以求得$a\equiv 691504013,b\equiv 308495997$

由于$C$的存在，我们令$a=a^C,b=b^C$

那么

$$\begin{aligned}(F_i)^k&=t^k(a^n-b^n)^k\\&=t^k\sum_{i=0}^k\left[(-1)^i\comb{k}{i}(a^n)^{k-i}(b^n)^{i}\right]\end{aligned}$$

那么有

$$\begin{aligned}\sum_{n=1}^{N}(F_n)^k &= \sum_{n=1}^Nt^k\sum_{i=0}^k(-1)^i\comb{k}{i}(a^n)^{k-i}(b^n)^{i}\\&=t^k \sum_{i=0}^k (-1)^i\comb{i}{k} \sum_{n=1}^N (a^{k-i}b^i)^n\end{aligned}$$

令$u_i=a^{k-i}b^i$，使用等比数列求和公式（注意公比为1时，不可用求和公式）

$$\sum_{n=1}^{N}(F_n)^k = \left\{\begin{aligned}&\sum_{i=0}^k (-1)^i\comb{i}{k}\frac{u_i(u_i^N-1)}{u_i-1} \quad (u_i\ne 1) \\&\sum_{i=0}^k (-1)^i\comb{i}{k}N\quad (u_i=1)\end{aligned}\right.$$

小细节：

• 求组合数需要预处理出$[1, 10^5]$的阶乘及对应的逆元
• 由于$1000000009$是质数，可以使用欧拉降幂降低复杂度（否则超时）

关键代码：

const int maxn = 1e5 + 1001;
const ll sqrt_5 = 383008016, inv_sqrt_5 = 276601605;
const ll mod = 1e9 + 9;
const ll x = 691504013, y = 308495997;

ll fact[maxn], inv_fact[maxn];

ll qpow(ll a, ll t){
    ll res = 1;
    while(t){
        if(t & 1) res = a * res % mod;
        t >>= 1, a = a * a % mod;
    }
    return res;
}

ll comb(int n, int k){
    if(k == 0 || k == n) return 1;
    return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
}

void init(){
    fact[0] = inv_fact[0] = 1;
    for(int i=1; i<maxn; i++) fact[i] = fact[i - 1] * i % mod;
    inv_fact[maxn - 1] = qpow(fact[maxn - 1], mod - 2);
    for(int i=maxn-2; i>0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
}

void solve(){
    ll n, c, k, a, b;
    cin >> n >> c >> k;
    a = qpow(x, c), b = qpow(y, c);

    ll cur = 1, factor = qpow(a, mod - 2) * b % mod;
    for(int i=1; i<=k; i++) cur = cur * a % mod; 
    
    ll ans = 0, sum;
    for(int i=0; i<=k; i++){
        if(cur == 1) sum = n % mod;
        if(cur != 1) 
            sum = cur * ((qpow(cur, n % (mod - 1)) - 1 + mod) % mod) % mod * qpow((cur - 1 + mod) % mod, mod - 2) % mod;
        ans = (ans + (comb(k, i) * sum % mod) * (i & 1?-1:1) + mod) % mod;
        cur = cur * factor % mod;
    }
    ans = ans * qpow(inv_sqrt_5, k) % mod;
    cout << ans << '\n';
}

附

拓展问题1：

若$F(i)=5F(i-1)+6F(i-2)$，$F(0)=2,F(1)=1$，求$F(n)$的通项公式.

解法

易知

$$\begin{pmatrix}F_i \\F_{i+1}\\\end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 5 & 6\end{pmatrix}\begin{pmatrix}F_{i-1} \\F_{i}\\\end{pmatrix}$$

得特征方程$\lambda^2-6\lambda-5=0$，解得$\lambda_1=2,\lambda_2=3$

令$F(n)=C_1(-2)^n+C_2(-3)^n$，可知$F(0)=C_1+C_2=2,F(1)=2C_1+3C_2=1$

解得$C_1=5,C_2=-3$

因此$F(n)=5(2)^n-3(3)^n$

---

注意：此方法仅限特征无重根且均为实数根时可用。

参考

• 斐波那契数列的通项公式推导-任所怀 (opens new window)
• 斐波那契数列通项公式是怎样推导出来的？ - Lancewu的回答 - 知乎 https://www.zhihu.com/question/25217301/answer/580609745
• 斐波那契数列通项公式是怎样推导出来的？ - 面无表情的仔仔的回答 - 知乎 https://www.zhihu.com/question/25217301/answer/158291644
• 差分方程的求解 https://wenku.baidu.com/view/c9fdb47f6ad97f192279168884868762cbaebb08.html