递推式转和式

发表于

总结一下数学基础

求和因子法

用途

解形如 ai=cai−1+ba_i = ca_{i - 1} + b 的线性递推式。

做法

寻找一个数 sis_i 使得 csi=si−1cs_i = s_{i - 1} , 两边都乘上 sis_i

那么 :

siai=csiai−1+sibsiai=si−1ai−1+sib设Ti=siaiTi=Ti−1+sib即Tn=T0+∑i=1nsiban=Tnsn=T0+∑i=1nsibsns_ia_i = cs_ia_{i - 1} + s_ib\\ s_ia_i = s_{i - 1}a_{i - 1} + s_ib\\ 设 T_i = s_ia_i\\ T_i = T_{i - 1} + s_ib\\ 即 T_n = T_0 + \sum_{i=1}^{n}s_ib\\ a_n = \frac{T_n}{s_n} = \frac{T_0 + \sum_{i=1}^{n}s_ib}{s_n}

实践一下

解 T0=0T_0 = 0 , Ti=2Ti−1+1T_i = 2T_{i - 1} + 1

取 si=12is_i = \frac{1}{2^i}

那么 :

12iTi=12i2Ti−1+12i12iTi=12i−1Ti−1+12i设Ai=12iTiAi=Ai−1+12iAn=A0+∑i=1n12iAn=∑i=1n12iAn=1−12nTn=2nAn=2n(1−12n)=2n−1\frac{1}{2^i}T_i = \frac{1}{2^i}2T_{i - 1} + \frac{1}{2^i}\\ \frac{1}{2^i}T_i = \frac{1}{2^{i - 1}}T_{i - 1} + \frac{1}{2^i}\\ 设 A_i = \frac{1}{2^i}T_i\\ A_i = A_{i - 1} + \frac{1}{2^i}\\ A_n = A_0 + \sum_{i=1}^{n} \frac{1}{2^i}\\ A_n = \sum_{i=1}^{n} \frac{1}{2^i}\\ A_n = 1 - \frac{1}{2^n}\\ T_n = 2^nA_n = 2^n(1 - \frac{1}{2^n}) = 2^n - 1

等比数列法 （不知道叫什么，自己取的名）

用途

解形如 ai=cai−1+ba_i = ca_{i - 1} + b 的线性递推式。

结论

an=cn(a0+bc−1)−bc−1a_n = c^n(a_0 + \frac{b}{c - 1}) - \frac{b}{c - 1}

证明

设存在一个 xx 使得 ai+x=c(ai−1+x)a_i+x = c(a_{i - 1} + x)

尝试求出 xx

∵ai+x=c(ai−1+x)∴ai+x=cai−1+cx∵ai=cai−1+b∴cai−1+b+x=cai−1+cx∴b+x=cx∴b=(c−1)x∴x=bc−1\because a_i+x = c(a_{i - 1} + x)\\ \therefore a_i + x = ca_{i - 1} + cx\\ \because a_i = ca_{i - 1} + b\\ \therefore ca_{i - 1} + b + x = ca_{i - 1} + cx\\ \therefore b + x = cx\\ \therefore b = (c - 1)x\\ \therefore x = \frac{b}{c - 1}\\

所以 ai+bc−1=c(ai−1+bc−1)a_i+\frac{b}{c - 1} = c(a_{i - 1} + \frac{b}{c - 1})

设 TiT_i 表示 ai+bc−1a_i + \frac{b}{c - 1}

那么 Ti=cTi−1T_i = cT_{i - 1}

Tn=cnT0T_n = c^nT_0

an+bc−1=cn(a0+bc−1)a_n + \frac{b}{c - 1} = c^n(a_0 + \frac{b}{c - 1})

an=cn(a0+bc−1)−bc−1a_n = c^n(a_0 + \frac{b}{c - 1}) - \frac{b}{c - 1}

实践一下

解 T0=0T_0 = 0 , Ti=2Ti−1+1T_i = 2T_{i - 1} + 1

Tn=2n(T0+12−1)−12−1Tn=2n(0+1)−1Tn=2n−1T_n = 2^n(T_0 + \frac{1}{2 - 1}) - \frac{1}{2 - 1}\\ T_n = 2^n(0 + 1) - 1\\ T_n = 2^n - 1

剩下的先咕着