|
本帖最后由 fungarwai 于 2020-7-25 14:11 编辑
我隨便貼過來看看能顯示多少
[hide=Chapter 0 Basic properties of finite difference]
Definition
Define \(\Delta p(x)=p(x+1)-p(x)\) which is called Finite difference
Linear operator
\(\Delta\) is a linear operator such that
\(\begin{cases}\Delta (p_1(x)+p_2(x))=\Delta p_1(x)+\Delta p_2(x)\\
\Delta (kp(x))=k\Delta p(x)\end{cases}\)
n th power of finite difference
\(\Delta^n p(x)=\Delta (\Delta^{n-1} p(x)
=\sum_{k=0}^n (-1)^{n-k}\binom{n}{k} p(x+k)\)
General results of high power finite difference
Define the degree of polynomial \(p(k)\) as \(\deg(p)\), for the polynomial with leadiing coefficient 1 :
\(\deg(p)=n\Rightarrow \begin{cases}\Delta^{n+1}p(x)=0\\
\Delta^n p(x)=n!\end{cases}\)[/hide]
[hide=Chapter 1 Newton's series]
Every polynomial can be represented by each degree of its finite difference
\(p(x)=\sum_{m=0}^{deg(p)} \binom{x-a}{m}\Delta^m p(a)\) which is known as Newton's series
[hide=Proof]Let \(p(x)=\sum_{m=0}^{deg(p)} c_m \binom{x-a}{m}=c_0+c_1\binom{x-a}{1}+c_2\binom{x-a}{2}+\dots+c_{deg(p)}\binom{x-a}{deg(p)}\)
\(p(a)=c_0\)
\(\Delta \binom{x-a}{k}=\binom{x+1-a}{k}-\binom{x-a}{k}=\binom{x-a}{k-1}\)
\(\Delta p(x)=c_1+c_2\binom{x-a}{1}+c_3\binom{x-a}{2}+\dots+c_{deg(p)}\binom{x-a}{deg(p)-1}\)
\(\Delta p(a)=c_1\)
\(\Delta^m p(k)=c_m+c_{m+1}\binom{x-a}{1}+c_{m+2}\binom{x-a}{2}+\dots+c_{deg(p)}\binom{x-a}{deg(p)-m}\)
\(\Delta^m p(a)=c_m\)[/hide]
[hide=Example]\(p(x)=x^2,\Delta p(x)=2x+1,\Delta^2 p(x)=2\)
\(p(x)=a^2+(2a+1)\binom{x-a}{1}+2\binom{x-a}{2}\)[/hide][/hide]
[size=150]Chapter 2 Summation with polynomial only
\(\sum_{k=1}^n p(k)=\sum_{m=0}^{deg(p)} \binom{n}{m+1}\Delta^m p(1)\)
[hide=Proof]\(\sum_{k=1}^n \binom{k-1}{m}=\binom{n}{m+1}\) which is called Hockey-stick identity
\(\sum_{k=1}^n p(k)=\sum_{m=0}^{deg(p)} \Delta^m p(1) \sum_{k=1}^n \binom{x-1}{m}=\sum_{m=0}^{deg(p)} \binom{n}{m+1}\Delta^m p(1)\)[/hide]
[hide=Example]\(p(k)=k,~\Delta p(k)=1\)
\(\sum_{k=1}^n k=\binom{n}{1}+\binom{n}{2}\)
\(p(k)=k^2,~\Delta p(k)=2k+1,~\Delta^2 p(k)=2\)
\(\sum_{k=1}^n k^2=\binom{n}{1}+3\binom{n}{2}+2\binom{n}{3}\)
\(p(k)=k^3,~\Delta p(k)=3k^2+3k+1,~\Delta^2 p(k)=6k+6,~\Delta^3 p(k)=6\)
\(\sum_{k=1}^n k^3=\binom{n}{1}+7\binom{n}{2}+12\binom{n}{3}+6\binom{n}{4}\)[/hide]
[size=150]Chapter 3 Summation with geometric sequence
\(\sum_{k=1}^n p(k)q^{k-1}=f(n)q^n-f(0)\), where \(f(n)
=\frac{p(n)}{q-1}+\frac{1}{(q-1)^2}\sum_{k=1}^{deg(p)} \frac{(-1)^kq^{k-1}}{(q-1)^{k-1}}\Delta^k(p(n))
=\frac{1}{q-1}\sum_{k=0}^{deg(p)} (\frac{-q}{q-1})^k\Delta^k p(n+1)\)
[hide=Proof]\(\Delta (\sum_{k=1}^n p(k)q^{k-1})=\Delta(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)\)
\((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)\)
\(\frac{I+\Delta}{(q-1)I+q\Delta}=\frac{I+\Delta}{q-1}\sum_{k=0}^{deg(p)} (\frac{-q}{q-1})^k \Delta^k\)
\(=\frac{1}{q-1}[\sum_{k=0}^{deg(p)} (\frac{-q}{q-1})^k \Delta^k+\sum_{k=0}^{deg(p)} (\frac{-q}{q-1})^k \Delta^{k+1}]
=\frac{1}{q-1}[\sum_{k=0}^{deg(p)} (\frac{-q}{q-1})^k \Delta^k+\sum_{k=1}^{deg(p)} (\frac{-q}{q-1})^{k-1} \Delta^k]\)
\(=\frac{1}{q-1}I+\frac{1}{q-1}\sum_{k=1}^{deg(p)} [(\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}^{deg(p)} (\frac{-q}{q-1})^{k-1} \Delta^k\)
\(=\frac{1}{q-1}I+\frac{1}{(q-1)^2}\sum_{k=1}^{deg(p)} \frac{(-1)^k q^{k-1}}{(q-1)^{k-1}} \Delta^k\)[/hide]
[hide=Example]\(p(k)=k^2,\Delta p(k)=2k+1,\Delta^2 p(k)=2\)
\(f(n)=\frac{n^2}{q-1}-\frac{2n+1}{(q-1)^2}+\frac{2}{(q-1)^3}q\)
\(\sum_{k=1}^n k^2 q^{k-1}=(\frac{n^2}{q-1}-\frac{2n+1}{(q-1)^2}+\frac{2}{(q-1)^3}q)q^n+\frac{1}{(q-1)^2}-\frac{2}{(q-1)^3}q\)
When \(|q|<1\), \(\sum_{k=1}^{\infty} k^2 q^{k-1}=\frac{1}{(q-1)^2}-\frac{2}{(q-1)^3}q=\frac{1+q}{(1-q)^3}\)
[/hide]
[hide=Chapter 4 Summation with geometric sequence and factorial]\(\sum_{n=0}^{\infty} \frac{p(n)}{n!}x^n=e^x\sum_{m=0}^{deg(p)} \frac{\Delta^m p(0)}{m!}x^m\)
[hide=Proof]\(\sum_{n=0}^\infty \frac{p(n)}{n!}x^n
=\sum_{m=0}^{deg(p)} \sum_{n=0}^\infty \binom{n}{m}\frac{\Delta^m p(0)}{n!}x^n\)
\(=\sum_{m=0}^{deg(p)} \frac{\Delta^m p(0)}{m!}x^m\sum_{n=m}^\infty \frac{1}{(n-m)!}x^{n-m}
=e^x \sum_{m=0}^{deg(p)} \frac{\Delta^m p(0)}{m!}x^m\)
This is related to a significant formula from Schaum's Outline of Calculus of Finite Differences and Difference Equations
\(\sum_{k=0}^\infty u_k v_k x^k=\sum_{k=0}^\infty \frac{\Delta^k u_0 x^k}{k!}\frac{d^k}{dx^k}(\sum_{l=0}^\infty v_l x^l)\)
\(\sum_{k=0}^\infty u_k v_k x^k
=\sum_{k=0}^\infty \sum_{l=0}^\infty \binom{k}{l}\Delta^l u_0 v_k x^k
=\sum_{k=0}^\infty \sum_{l=k}^\infty \binom{l}{k}\Delta^k u_0 v_l x^l\)
\(=\sum_{k=0}^\infty \frac{\Delta^k u_0 x^k}{k!}\sum_{l=k}^\infty l(l-1)\dots(l-k+1) v_l x^{l-k}\)
\(=\sum_{k=0}^\infty \frac{\Delta^k u_0 x^k}{k!}\frac{d^k}{dx^k}(\sum_{l=0}^\infty v_l x^l)\)[/hide]
[hide=Example]\(p(k)=2k+1,\Delta p(k)=2\)
\(\sum_{n=0}^\infty \frac{p(n)}{n!}x^n=(1+2x)e^x\)[/hide][/hide]
[hide=Chapter 5 Summation with Harmonic number]Define \(H_n=\sum_{k=1}^n \frac{1}{k}\) as Harmonic number
\(\sum_{k=1}^n H_k p(k)=(\sum_{m=0}^{deg(p)} \binom{n+1}{m+1} \Delta^m p(0))H_n-\sum_{m=0}^{deg(p)}\frac{1}{m+1}\binom{n}{m+1}\Delta^m p(0)\)
[hide=Proof]\(\sum_{k=1}^n H_k p(k)=\sum_{k=1}^n \sum_{t=1}^k \frac{p(k)}{t}
=\sum_{t=1}^n \sum_{k=t}^n p(k)
=\sum_{t=1}^n \frac{1}{t} (\sum_{k=1}^n p(k)-\sum_{k=1}^{t-1} p(k))\)
\(=(\sum_{m=0}^{deg(p)}\binom{n+1}{m+1}\Delta^m p(0))H_n-
\sum_{m=0}^{deg(p)}\sum_{t=1}^n \frac{1}{t}\binom{t}{m+1}\Delta^m p(0)\)
\(=(\sum_{m=0}^{deg(p)}\binom{n+1}{m+1}\Delta^m p(0))H_n-
\sum_{m=0}^{deg(p)}\frac{1}{m+1}\binom{n}{m+1}\Delta^m p(0)\)[/hide]
[hide=Example]\(p(k)=2k+1,\Delta p(k)=2\)
\(\sum_{k=1}^n H_k p(k)=(n+1+(n+1)n)H_n-(n+\frac{1}{2}n(n-1))
=(n+1)^2 H_n-\frac{1}{2}n(n+1)\)[/hide][/hide] |
|