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

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

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

但如裂項法那樣，要求$x_i=\mathrm{\Delta }{y}_i$的話，通常沒有那麼順利。

多項式公比求和

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

Template:Robox $\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)$
Template:Robox/Close

Template:Robox 對$\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)+\mathrm{\Delta }p(n)=(I+\mathrm{\Delta })p(n)$
$(I+\mathrm{\Delta })p(n)=q(I+\mathrm{\Delta })f(n)-f(n)=[(q-1)I+q\mathrm{\Delta }]f(n)$
$f(n)=\frac{I+\mathrm{\Delta }}{(q-1)I+q\mathrm{\Delta }}p(n)=\frac{1}{(q-1)I+q\mathrm{\Delta }}p(n+1)$

由於f,p都是m次多項式，以下可進行滿足條件${\mathrm{\Delta }}^{m+1}=0$的求逆運算：

$\frac{I+\mathrm{\Delta }}{(q-1)I+q\mathrm{\Delta }}=\frac{I+\mathrm{\Delta }}{q-1}\sum _{k=0}^m(\frac{-q}{q-1}{)}^k{\mathrm{\Delta }}^k$
$=\frac{1}{q-1}[\sum _{k=0}^m(\frac{-q}{q-1}{)}^k{\mathrm{\Delta }}^k+\sum _{k=0}^m(\frac{-q}{q-1}{)}^k{\mathrm{\Delta }}^{k+1}]=\frac{1}{q-1}[\sum _{k=0}^m(\frac{-q}{q-1}{)}^k{\mathrm{\Delta }}^k+\sum _{k=1}^m(\frac{-q}{q-1}{)}^{k-1}{\mathrm{\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}]{\mathrm{\Delta }}^k=\frac{1}{q-1}I-\frac{1}{(q-1{)}^2}\sum _{k=1}^m(\frac{-q}{q-1}{)}^{k-1}{\mathrm{\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}}{\mathrm{\Delta }}^k$
最後把算子表達式作用到p上得證。 Template:Robox/Close

Template:ExampleRobox 計算各階差分：$p(n)=a+(n-1)d,\mathrm{\Delta }p(n)=d$

$f(n)=\frac{a+(n-1)d}{r-1}-\frac{d}{(r-1{)}^2}$

$\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}]$ Template:Robox/Close

Template:ExampleRobox 計算各階差分：$p(n)=A+Bn+C{n}^2,\mathrm{\Delta }p(n)=B+C(2n+1)=B+C+2Cn,{\mathrm{\Delta }}^{2}p(n)=2C$

$f(n)=\frac{A+Bn+C{n}^2}{q-1}-\frac{B+C+2Cn}{(q-1{)}^2}+\frac{2C}{(q-1{)}^3}q$

$\sum _{k=1}^{n}p(k)q^{k-1}=[\frac{A+Bn+C{n}^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]$ Template:Robox/Close

Template:ExampleRobox $\sum _{k=1}^{\mathrm{\infty }}(A+Bk+C{k}^2)q^{k-1}=\frac{A}{1-q}+\frac{B+C}{(1-q{)}^2}+\frac{2C}{(1-q{)}^3}q$ Template:Robox/Close