代數/本書課文/求和/差分算子求逆法

把差分算子作用在和式兩邊，可見若差分算子表達式的逆可以計算出來的話，和式便可求解。

$S(n)=\sum _{k=1}^{n}p(k)\Rightarrow \Delta S(n)=p(n+1)\Rightarrow S(n)=\Delta ^{-1}p(n+1)$

但如裂項法那樣，要求$x_{i}=\Delta y_{i}$的話，通常沒有那麼順利。

多項式公比求和

$\sum _{k=1}^{n}p(k)q^{k-1}=f(n)q^{n}-f(0)$

$f(n)={\frac {p(n)}{q-1}}+{\frac {1}{(q-1)^{2}}}\sum _{k=1}^{m}{\frac {(-1)^{k}q^{k-1}}{(q-1)^{k-1}}}\Delta ^{k}(p(n))={\frac {1}{q-1}}\sum _{k=0}^{m}({\frac {-q}{q-1}})^{k}\Delta ^{k}p(n+1)$

其中$\Delta p(n)=p(n+1)-p(n),m=deg(p)$

這是顯式地將和式寫成差分算子表達式的一個例子。

證明多項式公比求和有表達式：$\sum _{k=1}^{n}p(k)q^{k-1}=f(n)q^{n}-f(0)$ 其中$deg(f)=deg(p)=m$ $\sum _{k=1}^{n}q^{k-1}={\frac {q^{n}-1}{q-1}}$ 設$\sum _{k=1}^{n}p(k)q^{k-1}=f(n)q^{n}+C$ 當$m=deg(p)=1$時，$deg(f)=m=1$ 兩邊逐項求導：$\sum _{k=1}^{n}(k-1)p(k)q^{k-2}=[{\frac {df(n)}{dq}}+nf(n)q^{-1}]q^{n}+{\frac {dC}{dq}}$ 可見兩邊多項式的階數同時增加1 $\sum _{k=0}^{n}p(k)q^{k-1}=f(n)q^{n}+C+p(0)q^{-1}$ 代入$n=0$得到$p(0)q^{-1}=f(0)+C+p(0)q^{-1}\Rightarrow C=-f(0)$

證明：$f(n)={\frac {p(n)}{q-1}}+{\frac {1}{(q-1)^{2}}}\sum _{k=1}^{m}{\frac {(-1)^{k}q^{k-1}}{(q-1)^{k-1}}}\Delta ^{k}(p(n))={\frac {1}{q-1}}\sum _{k=0}^{m}({\frac {-q}{q-1}})^{k}\Delta ^{k}p(n+1)$ 其中$\Delta p(n)=p(n+1)-p(n),m=deg(p)$ 對$\sum _{k=1}^{n}p(k)q^{k-1}=f(n)q^{n}-f(0)$兩邊差分 $p(n+1)q^{n}=f(n+1)q^{n+1}-f(n)q^{n}$ $p(n+1)=qf(n+1)-f(n)$ $p(n+1)=p(n)+\Delta p(n)=(I+\Delta )p(n)$ $(I+\Delta )p(n)=q(I+\Delta )f(n)-f(n)=[(q-1)I+q\Delta ]f(n)$ $f(n)={\frac {I+\Delta }{(q-1)I+q\Delta }}p(n)={\frac {1}{(q-1)I+q\Delta }}p(n+1)$ 由於f,p都是m次多項式，以下可進行滿足條件$\Delta ^{m+1}=0$的求逆運算： ${\frac {I+\Delta }{(q-1)I+q\Delta }}={\frac {I+\Delta }{q-1}}\sum _{k=0}^{m}({\frac {-q}{q-1}})^{k}\Delta ^{k}$ $={\frac {1}{q-1}}[\sum _{k=0}^{m}({\frac {-q}{q-1}})^{k}\Delta ^{k}+\sum _{k=0}^{m}({\frac {-q}{q-1}})^{k}\Delta ^{k+1}]={\frac {1}{q-1}}[\sum _{k=0}^{m}({\frac {-q}{q-1}})^{k}\Delta ^{k}+\sum _{k=1}^{m}({\frac {-q}{q-1}})^{k-1}\Delta ^{k}]$ $={\frac {1}{q-1}}I+{\frac {1}{q-1}}\sum _{k=1}^{m}[({\frac {-q}{q-1}})^{k}+({\frac {-q}{q-1}})^{k-1}]\Delta ^{k}={\frac {1}{q-1}}I-{\frac {1}{(q-1)^{2}}}\sum _{k=1}^{m}({\frac {-q}{q-1}})^{k-1}\Delta ^{k}$ $={\frac {1}{q-1}}I+{\frac {1}{(q-1)^{2}}}\sum _{k=1}^{m}{\frac {(-1)^{k}q^{k-1}}{(q-1)^{k-1}}}\Delta ^{k}$ 最後把算子表達式作用到p上得證。

例子：差比數列求和 計算各階差分：$p(n)=a+(n-1)d,\Delta p(n)=d$ $\displaystyle f(n)={\frac {a+(n-1)d}{r-1}}-{\frac {d}{(r-1)^{2}}}$ $\displaystyle \sum _{k=1}^{n}[a+(k-1)d]r^{k-1}=[{\frac {a+(n-1)d}{r-1}}-{\frac {d}{(r-1)^{2}}}]r^{n}-[{\frac {a-d}{r-1}}-{\frac {d}{(r-1)^{2}}}]$

例子：求$\displaystyle \sum _{k=1}^{n}(A+Bk+Ck^{2})q^{k-1}$ 計算各階差分：$p(n)=A+Bn+Cn^{2},\Delta p(n)=B+C(2n+1)=B+C+2Cn,\Delta ^{2}p(n)=2C$ $\displaystyle f(n)={\frac {A+Bn+Cn^{2}}{q-1}}-{\frac {B+C+2Cn}{(q-1)^{2}}}+{\frac {2C}{(q-1)^{3}}}q$ $\displaystyle \sum _{k=1}^{n}p(k)q^{k-1}=[{\frac {A+Bn+Cn^{2}}{q-1}}-{\frac {B+C+2Cn}{(q-1)^{2}}}+{\frac {2C}{(q-1)^{3}}}q]q^{n}-[{\frac {A}{q-1}}-{\frac {B+C}{(q-1)^{2}}}+{\frac {2C}{(q-1)^{3}}}q]$

$\sum _{k=1}^{\infty }p(k)q^{k-1}={\frac {p(0)}{1-q}}+{\frac {1}{(1-q)^{2}}}\sum _{k=1}^{m}{\frac {q^{k-1}}{(1-q)^{k-1}}}\Delta ^{k}(p(0)),~|q|<1$

例子：求$\displaystyle \sum _{k=1}^{\infty }(A+Bk+Ck^{2})q^{k-1},~|q|<1$ $\displaystyle \sum _{k=1}^{\infty }(A+Bk+Ck^{2})q^{k-1}={\frac {A}{1-q}}+{\frac {B+C}{(1-q)^{2}}}+{\frac {2C}{(1-q)^{3}}}q$