数列

变量

• $a_n \ (n \in \mathbf{N}^*)$：数列的第 $n$ 项；
• $S_n$：前 $n$ 项和（前缀和）；
• $d$：等差数列的公差；
• $q \ (q \neq 0)$：等比数列的公比。

$a_1$ 和 $p$ 或 $q$ 是基本量。一般地，$a_n = \begin{cases} S_1 &(n = 1) \\ S_{n} - S_{n - 1} &(n \geq 2) \end{cases}$。

自然数幂求和公式

$$\begin{aligned} \sum_{i = 1}^{n} i &= \frac{n(n + 1)}{2} \\ \sum_{i = 1}^{n} i^2 &= \frac{n(n + 1)(2n + 1)}{6} \\ \sum_{i = 1}^{n} i^3 &= \left[\frac{n(n + 1)}{2}\right]^2 \end{aligned}$$

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

等差、等比数列

设 $m \geq 1$。

等差数列的性质

设 $\{a_n\}$ 是等差数列，公差为 $d$，$S_{\text{偶}}$ 为偶数项之和，$S_{\text{奇}}$ 为奇数项之和。

1. 若 $p + q = r + s \ (p, q, r, s \in \mathbf{N}^*)$，则 $a_p + a_q = a_r + a_s$。

   扩展：若 $\sum_{i = 1}^{n}p_i = \sum_{i = 1}^{n}q_i$，则 $\sum_{i = 1}^{n}a_{p_i} = \sum_{i = 1}^{n}a_{q_i}$。

2. $\dfrac{S_n}{n} = \dfrac{na_1 + \frac{nd(n - 1)}{2}}{n} = a_1 + \dfrac{n - 1}{2}d$，故 $\left\{\dfrac{S_n}{n}\right\}$ 是首项为 $a_1$，公差为 $\dfrac{d}{2}$ 的等差数列。

3. 奇数项和与偶数项和

   • 若项数为 $2n$，则 $S_{2n} = n(a_n + a_{n + 1})$，其中 $a_n,\ a_{n + 1}$ 为中间两项。

     $S_{\text{偶}} - S_{\text{奇}} = nd$，$\dfrac{S_{\text{偶}}}{S_{\text{奇}}} = \dfrac{a_{n + 1}}{a_n}$。

   • 若项数为 $2n - 1$，则 $S_{2n - 1} = (2n - 1)a_n$，其中 $a_n$ 为中间项。

     $S_{\text{奇}} = \dfrac{n(a_1 + a_{2n - 1})}{2} = na_n$，$S_{\text{偶}} = \dfrac{(n - 1)(a_2 + a_{2n - 2})}{2} = (n - 1)a_n$。

     $S_{\text{奇}} - S_{\text{偶}} = a_n$，$\dfrac{S_{\text{奇}}}{S_{\text{偶}}} = \dfrac{n}{n - 1}$。

4. 等差数列依次每 $k$ 项之和仍成等差数列，即 $S_k,\ S_{2k} - S_k,\ S_{3k} - S_{2k},\ \cdots,\ S_{nk} - S_{(n - 1)k}$ 成等差数列，公差 $k^2d$。

5. 设等差数列 $\{b_n\}$，$\{a_n\},\ \{b_n\}$ 的前缀和分别为 $S_n,\ T_n$，则 $\dfrac{a_n}{b_n} = \dfrac{S_{2n - 1}}{T_{2n - 1}}$。

6. $S_m = p,\ S_n = q \ (m \neq n) \Rightarrow S_{m + n} = \dfrac{(S_n - S_m)(n + m)}{n - m} = \dfrac{(q - p)(n + m)}{n - m}$。

   特别地，若 $S_m = n,\ S_n = m$，则 $S_{m + n} = -(n + m)$；若 $S_m = S_n$，则 $S_{m + n} = 0$。

等比数列的性质

设 $\{a_n\}$ 是等比数列，公比为 $q$，$S_{\text{偶}}$ 为偶数项之和，$S_{\text{奇}}$ 为奇数项之和。

1. 若 $p + q = r + s \ (p, q, r, s \in \mathbf{N}^*)$，则 $a_p \cdot a_q = a_r \cdot a_s$。

   扩展：若 $\sum_{i = 1}^{n}p_i = \sum_{i = 1}^{n}q_i$，则 $\prod_{i = 1}^{n}a_{p_i} = \prod_{i = 1}^{n}a_{q_i}$。

2. 若 $m, n, p$ 成等差数列，则 $a_m,\ a_n,\ a_p$ 成等比数列。

3. 等比性质：设 $\{m_n\}$ 是等差数列，$k$ 是一个常数，则有

   $$\frac{a_{m_1 + k} + a_{m_2 + k} + \cdots + a_{m_n + k}}{a_{m_1} + a_{m_2} + \cdots + a_{m_n}} = q^k$$

4. 有穷等比数列中，与首末两项等距离的两项之积都相等。即

   $$a_1 \cdot a_n = a_2 \cdot a_{n - 1} = \cdots = a_m \cdot a_{n - m + 1}$$

5. 前缀和的性质

   • $S_{m + n}$ 满足

     $$S_{m + n} = S_m + q^m S_n = S_n + q^n S_m$$

     证明：$S_{m + n} = S_m + \sum_{i = m + 1}^{m + n}a_i = S_m + \sum_{i = 1}^{n}a_i q^m = S_m + S_n q^m$。

   • 等比数列依次每 $k$ 项之和仍成等比数列，但是 $\color{red} q \neq -1$，即 $S_k,\ S_{2k} - S_k,\ S_{3k} - S_{2k},\ \cdots,\ S_{nk} - S_{(n - 1)k}$ 成等比数列，公比 $q^k$。

6. 奇数项和与偶数项和

   • 若项数为 $2n$，则

     $$\dfrac{S_{\text{偶}}}{S_{\text{奇}}} = q$$

   • 若项数为 $2n~{\color{red}+}~1$，则

     $$\dfrac{S_{\text{奇}} - a_1}{S_{\text{偶}}} = q$$

裂项

核心思想：将 $f(n)$ 裂成类似于 $g(n) - g(n + 1)$ 的形式，使得累加的时候可以直接消掉中间的项。

$$\begin{aligned} \frac{1}{n(n + k)} &= \frac{1}{k}\left(\frac{1}{n} - \frac{1}{n + k}\right) \\ \frac{1}{n(n + 1)(n + 2)} &= \frac{1}{2} \left[\frac{1}{n(n + 1)} - \frac{1}{(n + 1)(n + 2)}\right] \\ \frac{1}{(2n - 1)(2n + 1)} &= \frac{1}{2}\left(\frac{1}{2n - 1} - \frac{1}{2n + 1}\right) \\ \frac{1}{\sqrt{a} + \sqrt{b}} &= \frac{1}{a - b}(\sqrt{a} - \sqrt{b}) \\ \ln\left(1 + \frac{1}{n}\right) &= \ln(n + 1) - \ln n \\ \frac{1}{a_n a_{n + k}} &= \frac{1}{dk}(\frac{1}{a_n} - \frac{1}{a_{n + k}}) \hspace{1em} \text{（}\{a_n\} \text{是等差数列）} \\ \frac{2^n}{(2^n + 1)(2^{n + 1} + 1)} &= \frac{1}{2^n + 1} - \frac{1}{2^{n + 1} + 1} \end{aligned}$$

求通项公式

$S_n$ 和 $a_n$ 的关系

已知 $f(a_n, S_n) = 0$（即 $a_n$ 和 $S_n$ 之间的等量关系），可以选择消去 $a_n$ 或 $S_n$。最后注意是否可以合并 $n = 1$ 和 $n \geq 2$ 的情况。

累加法

已知 $a_n - a_{n - 1} = f(n) \ (n \geq 2)$，考虑累加：

$$\begin{aligned} a_n - a_{n - 1} &= f(n) \\ a_{n - 1} - a_{n - 2} &= f(n - 1) \\ a_{n - 2} - a_{n - 3} &= f(n - 2) \\ \vdots \\ a_{2} - a_{1} &= f(2) \\ \end{aligned}$$

全部相加，得

$$a_n - a_1 = \sum_{i = 2}^{n}f(i)$$

对于 $\sum_{i = 2}^{n}f(i)$，可以考虑裂项、分组求和或直接套公式求和。最后看看 $n = 1$ 时能不能合并。

累乘法

已知 $a_n = a_{n - 1} \cdot f(n) \ (n \geq 2)$，可用 $a_n = \dfrac{a_n}{a_{n - 1}} \times \dfrac{a_{n - 1}}{a_{n - 2}} \times \cdots \times \dfrac{a_3}{a_2} \times \dfrac{a_2}{a_1} \times a_1$，转为基本求和。

构造法

1. 一阶线性递推 I：$a_{n + 1} = ka_n + b \ (k \neq 1,\ b \neq 0)$

   方法一：考虑构造 $a_{n + 1} + \lambda = k(a_n + \lambda)$，与原式比较系数，得 $\lambda = \dfrac{b}{k - 1}$。

   所以 $\left\{a_n + \dfrac{b}{k - 1}\right\}$ 是首项为 $a_1 + \dfrac{b}{k - 1}$，公比为 $k$ 的等比数列。

   方法二：由 $a_{n + 1} = ka_n + b$ 得 $a_n = ka_{n - 1} + b \ (n \geq 2)$，相减得 $a_{n + 1} - a_n = k(a_n - a_{n - 1})$。当 $a_n \neq a_{n - 1}$ 时，$\left\{a_{n + 1} - a_{n}\right\}$ 是等比数列，公比为 $k$。

2. 一阶线性递推 II：$a_{n + 1} = pa_n + qn + r \ (p \neq 1,\ q \neq 0)$

   考虑构造 $a_{n + 1} + \lambda(n + 1) + \mu = p(a_n + \lambda n + \mu)$，与原式比较系数，得

   $$\begin{cases} \lambda(p - 1) = q \\ \mu(p - 1) - \lambda = r \end{cases} \Rightarrow \begin{cases} \lambda = \dfrac{q}{p - 1} \\ \mu = \dfrac{r(p - 1) + q}{(p - 1)^2} \end{cases}$$

   所以 $\left\{a_n + \lambda n + \mu\right\}$ 是公比为 $p$ 的等比数列。

3. 简单分式递推：$a_{n + 1} = \dfrac{p a_n}{q a_n + r}$

   考虑两边同时取倒数，得 $\dfrac{1}{a_{n + 1}} = \dfrac{q a_n + r}{p a_n} \Rightarrow \dfrac{1}{a_{n + 1}} = \dfrac{r}{p} \cdot \dfrac{1}{a_n} + \dfrac{q}{p}$。

   若 $r = p$，则 $\left\{\dfrac{1}{a_n}\right\}$ 是等差数列，否则继续构造。

4. 含指数幂递推 I：$a_n = ka_{n - 1} + rp^n$（或 $a_n = ka_{n - 1} + rp^{n - 1}$）

   方法一：两边同时除以 $q^n$，得 $\dfrac{a_n}{q^n} = \dfrac{k a_{n - 1}}{p^n} + r = \dfrac{k}{p} \cdot \dfrac{a_{n - 1}}{p^{n - 1}} + r$（或 $\dfrac{a_n}{q^n} = \dfrac{k}{p} \cdot \dfrac{a_{n - 1}}{p^{n - 1}} + \dfrac{r}{p}$）。

   方法二：构造 $a_n + \lambda p^n = k(a_{n - 1} + \lambda p^{n - 1})$，比较系数，解得 $\lambda = \dfrac{p}{k - p}$。对于 $a_n = ka_{n - 1} + rp^{n - 1}$，可得 $\lambda = \dfrac{1}{k - p}$。

5. 含指数幂递推 II：$a_{n + 1}^k = pa_n^{2k} + qa_n^k + r$

   考虑变成 $\mu a_{n + 1}^k + \lambda = (\mu a_n^k + \lambda)^2$ 的形式，然后两边取对数：$\lg(\mu a_{n + 1}^k + \lambda) = 2\lg(\mu a_n^k + \lambda)$，所以 $\left\{\lg(\mu a_n^k + \lambda)\right\}$ 是等比数列。

6. 二阶线性递推：$a_n = pa_{n - 1} + qa_{n - 2} + r \ (n \geq 3)$

   考虑构造 $a_n + \lambda a_{n - 1} + \mu = k(a_{n - 1} + \lambda a_{n - 2} + \mu)$，解得 $k,\ \lambda,\ \mu$。后面继续构造。

隔项递推

考虑分奇偶分类讨论。

1. 隔项等差：$a_{n + 2} - a_{n} = d$

   1. $n$ 为奇数。令 $n = 2k - 1$（此处 $k$ 就是 $1 \sim n$ 的奇数项项数），得 $k = \dfrac{n + 1}{2}$。

      因此 $a_n = a_{2k - 1} = a_1 + ({\color{red}k} - 1)d = a_1 + \left(\dfrac{n + 1}{2} - 1\right)d = a_1 + \dfrac{n - 1}{2}d$。

   2. $n$ 为偶数。令 $n = 2k$，得 $k = \dfrac{n}{2}$。（好好看看哪个是你的首项！）

      因此 $a_n = a_{2k} = a_{\color{red}2} + (k - 1)d = a_2 + \left(\dfrac{n}{2} - 1\right)d = a_2 + \dfrac{n - 2}{2}d$。

   所以 $a_n = \begin{cases} a_1 + \dfrac{n - 1}{2} & \text{（}n~\text{为奇数）} \\ a_2 + \dfrac{n - 2}{2} & \text{（}n~\text{为偶数）} \\ \end{cases}$。

2. 隔项等比：$a_{n + 2} = qa_{n}$

   方法与上述类似。最后 $a_n = \begin{cases} a_1 \cdot q^{(n - 1) / 2} & \text{（}n~\text{为奇数）} \\ a_2 \cdot q^{(n - 2) / 2} & \text{（}n~\text{为偶数）} \\ \end{cases}$。

不动点法

对于 $y = f(x)$，若存在 $x_0$，使得 $x_0 = f(x_0)$，则 $x_0$ 是这个函数的不动点。

1. 一阶线性递推：$a_{n + 1} = ka_n + b \ (k \neq 1,\ b \neq 0)$

   1. 构造 $f(x) = kx + b$，令 $x = f(x)$，解出不动点 $x_0$。
   2. 原递推式两边同时减去 $x_0$，并化简，转构造数列。

2. 分式递推：$a_{n + 1} = \dfrac{p a_n + q}{r a_n + s}$

   构造 $f(x) = \dfrac{px + q}{rx + s}$，令 $x = f(x)$，解出不动点。考虑不动点的数量：

   1. 若有 $2$ 个不动点 $x_1,\ x_2$，分别用 $x_1,\ x_2$ 减去原递推式，得 $2$ 个式子，相除再化简，转构造数列。
   2. 若只有 $1$ 个不动点 $x_0$，用 $x_0$ 减去原递推式，取倒数再化简，转构造数列。
   3. 若没有，一般地，该数列的周期较短，手动代值计算，直到算出 $a_j = a_1$ 为止。若算了十几项还没有满足，看看你算错了没有。

特征根法

给定 $a_1 = m_1,\ a_2 = m_2$ 和递推式 $a_{n + 2} = pa_{n + 1} + qa_n$，有特征方程 $x^2 = px + q$。设方程的两根为 $\alpha,\ \beta$。

1. 若 $\alpha = \beta$，则 $a_n = (c_1 + nc_2) \cdot \alpha^n$。
2. 若 $\alpha \neq \beta$，则 $a_n = c_1 \cdot \alpha^n + c_2 \cdot \beta^n$。

其中 $c_1,\ c_2$ 是待定的系数，可通过 $a_1,\ a_2$ 求解。

对于 $a_{n + 1} = pa_n + q^n$ 也可以用特征根法求解。具体地，可变成 $a_{n} = pa_{n - 1} + q^{n - 1} \Rightarrow qa_n = pqa_{n - 1} + q^n \ (n \geq 2)$，两式相加得 $a_{n + 1} = (p + q)a_n - pqa_{n - 1}$，之后可以用特征根法求解。

求和

1. 套公式。注意等比数列的项数为奇数时，有前 $n$ 项和等于项数乘以中间项。
2. 分组。
3. 倒序相加法。参考等差数列求和公式的推导。
4. 分段求和法。
5. 裂项相消法。参考前面的“︁裂项”︁。
6. 错位相减法。参考等比数列求和公式的推导。

斐波那契数列

递推公式、通项公式

递推公式及其初始条件

$$a_1 = a_2 = 1,\ a_n = a_{n - 1} + a_{n - 2} \ (n \geq 3)$$

通项公式

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

性质

1. 前 $n$ 项和：$S_n = a_{n + 2} - 1$。
2. 奇数项和：$a_1 + a_3 + a_5 + \cdots + a_{2n - 1} = a_{2n}$。
3. 偶数项和：$a_2 + a_4 + a_6 + \cdots + a_{2n} = a_{2n + 1} - 1$。
4. 前 $n$ 项平方和：$\sum_{i = 1}^{n}a_i^2 = a_n a_{n + 1}$。
5. 被整数除的余数具有周期性。
6. $\dfrac{1}{a_1 a_3} + \dfrac{1}{a_2 a_4} + \cdots + \dfrac{1}{a_{2n - 3} a_{2n - 1}} + \dfrac{1}{a_{2n - 2}a_{2n}} = \dfrac{1}{a_1 a_2} - \dfrac{1}{a_{2n - 1} a_{2n}}$。