錯位相減法是透過兩個求和式的相減化簡求和數列的求和方法。
設 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}}}