错位相减法是透过两个求和式的相减化简求和数列的求和方法。
设 S n = ∑ k = 1 n p ( k ) q k − 1 {\displaystyle S_{n}=\sum _{k=1}^{n}p(k)q^{k-1}} q S n = ∑ k = 1 n p ( k ) q k {\displaystyle qS_{n}=\sum _{k=1}^{n}p(k)q^{k}} ( 1 − q ) S n = ∑ k = 1 n p ( k ) q k − 1 − ∑ k = 1 n p ( k ) q k = ∑ k = 0 n − 1 p ( k + 1 ) q k − ∑ k = 1 n p ( k ) q k = ∑ k = 1 n [ p ( k + 1 ) − p ( k ) ] q k + p ( 1 ) − p ( n + 1 ) q n S n = q 1 − q ∑ k = 1 n [ p ( k + 1 ) − p ( k ) ] q k − 1 + p ( 1 ) − p ( n + 1 ) q n 1 − q {\displaystyle {\begin{aligned}(1-q)S_{n}&=\sum _{k=1}^{n}p(k)q^{k-1}-\sum _{k=1}^{n}p(k)q^{k}\\~&=\sum _{k=0}^{n-1}p(k+1)q^{k}-\sum _{k=1}^{n}p(k)q^{k}\\~&=\sum _{k=1}^{n}[p(k+1)-p(k)]q^{k}+p(1)-p(n+1)q^{n}\\S_{n}&={\frac {q}{1-q}}\sum _{k=1}^{n}[p(k+1)-p(k)]q^{k-1}+{\frac {p(1)-p(n+1)q^{n}}{1-q}}\end{aligned}}}
每一次错位相减会对多项式进行一次差分,一个m阶多项式进行差分后是m-1阶多项式,所以可以在有限步内用错位相减法求出多项式公比求和。
q S n = ∑ k = 1 n q k {\displaystyle qS_{n}=\sum _{k=1}^{n}q^{k}} ( q − 1 ) S n = q n − 1 , S n = ∑ k = 1 n q k − 1 = q n − 1 q − 1 {\displaystyle (q-1)S_{n}=q^{n}-1,S_{n}=\sum _{k=1}^{n}q^{k-1}={\frac {q^{n}-1}{q-1}}}
代入上述结论: S n = r 1 − r ∑ k = 1 n d r k − 1 + a − ( a + d n ) r n 1 − r = d r ( 1 − r n ) ( 1 − r ) 2 + a − ( a + d n ) r n 1 − r {\displaystyle {\begin{aligned}S_{n}&={\frac {r}{1-r}}\sum _{k=1}^{n}dr^{k-1}+{\frac {a-(a+dn)r^{n}}{1-r}}\\~&={\frac {dr(1-r^{n})}{(1-r)^{2}}}+{\frac {a-(a+dn)r^{n}}{1-r}}\end{aligned}}}
S n = ∑ k = 1 n x k = ∑ k = 1 n x n + 1 − k {\displaystyle S_{n}=\sum _{k=1}^{n}x_{k}=\sum _{k=1}^{n}x_{n+1-k}} 若 x k + x n + 1 − k {\displaystyle x_{k}+x_{n+1-k}} 为常数,即可求出 2 S n {\displaystyle 2S_{n}}
S n = ∑ k = 1 n a + d ( k − 1 ) = ∑ k = 1 n a + d ( n − k ) {\displaystyle S_{n}=\sum _{k=1}^{n}a+d(k-1)=\sum _{k=1}^{n}a+d(n-k)} 2 S n = ∑ k = 1 n 2 a + d ( n − 1 ) = 2 a n + d n ( n − 1 ) {\displaystyle 2S_{n}=\sum _{k=1}^{n}2a+d(n-1)=2an+dn(n-1)} S n = a n + d n ( n − 1 ) 2 {\displaystyle S_{n}=an+d{\frac {n(n-1)}{2}}}