User:Cornince

Alternative account: User:Beneficii

Basic definition of a sum

$\sum _{i=m}^n{f}(i)={f}(m)+{f}(m+1)+{f}(m+2)+...+{f}(n-2)+{f}(n-1)+{f}(n)$

Recursive summation

Where $p\ge 0$:

$\sum _{i=m}^{i_p}{}^{p}f(i)=\sum _{i_{p-1}=m}^{i_p}\sum _{i_{p-2}=m}^{i_{p-1}}\sum _{i_{p-3}=m}^{i_{p-2}}...\sum _{i_2=m}^{i_3}\sum _{i_1=m}^{i_2}\sum _{i_0=m}^{i_1}f(i_0)$

$\sum _{i=m}^{i_0}{}^0{f}(i)={f}(i_0)$

$\sum _{i=m}^{i_1}{}^1{f}(i)=\sum _{i_0=m}^{i_1}{f}(i_0)$

$\mathrm{I}\mathrm{f}{g}(n)=\sum _{i=m}^n{}^{-p}{f}(i),\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}{f}(n)=\sum _{i=m}^n{}^p{g}(i).$

Where $p>0$:

$\sum _{i=m}^{i_p}{}^p{f}(i)=\sum _{i_{p-1}=m}^{i_p}[\sum _{i=m}^{i_{p-1}}{}^{p-1}{f}(i)]$

$\sum _{i_{p-1}=m}^{i_p}[\sum _{i=m}^{i_{p-1}}{}^{p-1}{f}(i)]=\sum _{i=m}^m{}^{p-1}{f}(i)+\sum _{i=m}^{m+1}{}^{p-1}{f}(i)+\sum _{i=m}^{m+2}{}^{p-1}{f}(i)+...+\sum _{i=m}^{i_p-2}{}^{p-1}{f}(i)+\sum _{i=m}^{i_p-1}{}^{p-1}{f}(i)+\sum _{i=m}^{i_p}{}^{p-1}{f}(i)$

Shifting of starting and ending indices

$\sum _{i=m}^n{f}(i)=\sum _{i=m+u}^{n+u}{f}(i-u)$

Proof of the equality of the shifting of indices:

$\begin{array}{lcl}\sum _{i=m+u}^{n+u}{f}(i-u)& =& {f}((m+u)-u)+{f}((m+u+1)-u)+{f}((m+u+2)-u)\\ & & +...+{f}((n+u-2)-u)+{f}((n+u-1)-u)+{f}((n+u)-u)\\ \\ & =& {f}(m)+{f}(m+1)+{f}(m+2)+...+{f}(n-2)+{f}(n-1)+{f}(n)\\ \\ & =& \sum _{i=m}^n{f}(i)\end{array}$

Smaller summation notation

$\sum _{i=m}^n{}^p{f}(i)={}_p{\sum }_{i=m}^n{f}(i)$

Recursive geometric series

$\begin{array}{lcl}{}_p\sum _{i=m}^n{r}^i& =& \frac{r^{n+p}}{(r-1{)}^p}-\sum _{k=0}^{p-1}\frac{r^{m+p-(k+1)}\prod _{j=1}^k(n-m+j)}{k!(r-1{)}^{p-k}}\\ & =& \frac{r^{n+p}}{(r-1{)}^p}-\sum _{k=0}^{p-1}\frac{r^{m+p-(k+1)}\frac{(n-m+k)!}{(n-m)!}}{(r-1{)}^{p-k}k!}\\ & =& \frac{r^{n+p}}{(r-1{)}^p}-\sum _{k=0}^{p-1}\left(\frac{r^{m+p-(k+1)}}{(r-1{)}^{p-k}}\right)(\genfrac{}{}{0ex}{}{n-m+k}{k})\end{array}$

Combinations proof (used in below proof)

$\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{-}\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{r}\mathrm{s}q\mathrm{a}\mathrm{n}\mathrm{d}t\ge q,\sum _{z=q}^t(\genfrac{}{}{0ex}{}{z}{q})=(\genfrac{}{}{0ex}{}{t+1}{q+1}).$

$t=q,\sum _{z=q}^q(\genfrac{}{}{0ex}{}{z}{q})=(\genfrac{}{}{0ex}{}{q}{q})=1=(\genfrac{}{}{0ex}{}{q+1}{q+1})$

$t=c,\sum _{z=q}^c(\genfrac{}{}{0ex}{}{z}{q})=(\genfrac{}{}{0ex}{}{c+1}{q+1})$

$t=c+1,\sum _{z=q}^{c+1}(\genfrac{}{}{0ex}{}{z}{q})=\sum _{z=q}^c(\genfrac{}{}{0ex}{}{z}{q})+(\genfrac{}{}{0ex}{}{c+1}{q})=(\genfrac{}{}{0ex}{}{c+1}{q+1})+(\genfrac{}{}{0ex}{}{c+1}{q})=(\genfrac{}{}{0ex}{}{(c+1)+1}{q+1})$

Proof by mathematical induction of the recursive geometric series (uses recursive summation notation)

Definition

$\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}r\ne 1\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{-}\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{r}\mathrm{s}m,p,\mathrm{a}\mathrm{n}\mathrm{d}{i}_p,\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}{i}_p\ge m,$

$\sum _{i=m}^{i_p}{}^p{r}^i=\frac{r^{i_p+p}}{(r-1{)}^p}-\sum _{k=0}^{p-1}\frac{r^{m+p-(k+1)}\prod _{j=1}^k(i_p-m+j)}{k!(r-1{)}^{p-k}}.$

Base case (and some specific examples)

$p=0,\sum _{i=m}^{i_0}{}^0{r}^i=\frac{r^{i_0+0}}{(r-1{)}^0}=r^{i_0}$

$p=1,\sum _{i=m}^{i_1}{}^1{r}^i=\frac{r^{i_1+1}}{(r-1{)}^1}-\frac{r^m}{0!(r-1{)}^1}=\frac{r^{i_1+1}-r^m}{r-1}$

$p=2,\sum _{i=m}^{i_2}{}^2{r}^i=\frac{r^{i_2+2}}{(r-1{)}^2}-\frac{r^{m+1}}{0!(r-1{)}^2}-\frac{r^m(i_2-m+1)}{1!(r-1{)}^1}=\frac{\frac{r^{i_2+2}-r^{m+1}}{r-1}-r^m(i_2-m+1)}{r-1}$

$p=3,$

$\sum _{i=m}^{i_3}{}^3{r}^i=\frac{r^{i_3+3}}{(r-1{)}^3}-\frac{r^{m+2}}{0!(r-1{)}^3}-\frac{r^{m+1}(i_3-m+1)}{1!(r-1{)}^2}-\frac{r^m(i_3-m+1)(i_3-m+2)}{2!(r-1{)}^1}$

$=\frac{\frac{\frac{r^{i_3+3}-r^{m+2}}{r-1}-r^{m+1}(i_3-m+1)}{r-1}-\frac{1}{2}{r}^m(i_3-m+1)(i_3-m+2)}{r-1}$

$p=4,$

$\sum _{i=m}^{i_4}{}^4{r}^i=\frac{r^{i_4+4}}{(r-1{)}^4}-\frac{r^{m+3}}{0!(r-1{)}^4}-\frac{r^{m+2}(i_4-m+1)}{1!(r-1{)}^3}-\frac{r^{m+1}(i_4-m+1)(i_4-m+2)}{2!(r-1{)}^2}$

$-\frac{r^m(i_4-m+1)(i_4-m+2)(i_4-m+3)}{3!(r-1{)}^1}$

$=\frac{\frac{\frac{\frac{r^{i_4+4}-r^{m+3}}{r-1}-r^{m+2}(i_4-m+1)}{r-1}-\frac{1}{2}{r}^{m+1}(i_4-m+1)(i_4-m+2)}{r-1}-\frac{1}{6}{r}^m(i_4-m+1)(i_4-m+2)(i_4-m+3)}{r-1}$

Inductive step

$p=a,\sum _{i=m}^{i_a}{}^a{r}^i=\frac{r^{i_a+a}}{(r-1{)}^a}-\sum _{k=0}^{a-1}\frac{r^{m+a-(k+1)}\prod _{j=1}^k(i_a-m+j)}{k!(r-1{)}^{a-k}}$

$p=a+1,\sum _{i=m}^{i_{(a+1)}}{}^{(a+1)}{r}^i=\sum _{i_a=m}^{i_{(a+1)}}\left[\sum _{i=m}^{i_a}{}^a{r}^i\right]$

$=\sum _{i_a=m}^{i_{(a+1)}}[\frac{r^{i_a+a}}{(r-1{)}^a}-\sum _{k=0}^{a-1}\frac{r^{m+a-(k+1)}\prod _{j=1}^k(i_a-m+j)}{k!(r-1{)}^{a-k}}]$

$=\sum _{i_a=m}^{i_{(a+1)}}\left[\frac{r^{i_a+a}}{(r-1{)}^a}\right]-\sum _{i_a=m}^{i_{(a+1)}}\left[\sum _{k=0}^{a-1}\frac{r^{m+a-(k+1)}\prod _{j=1}^k(i_a-m+j)}{k!(r-1{)}^{a-k}}\right]$

$=\frac{\sum _{i_a=m}^{i_{(a+1)}}\left(r^{i_a+a}\right)}{(r-1{)}^a}-\sum _{i_a=m}^{i_{(a+1)}}\left[\sum _{k=0}^{a-1}\frac{r^{m+a-(k+1)}\left[\frac{(i_a-m+k)!}{(i_a-m)!}\right]}{(r-1{)}^{a-k}k!}\right]$

$=\frac{r^a\sum _{i_a=m}^{i_{(a+1)}}\left(r^{i_a}\right)}{(r-1{)}^a}-\sum _{i_a=m}^{i_{(a+1)}}\left[\sum _{k=0}^{a-1}\left(\frac{r^{m+a-(k+1)}}{(r-1{)}^{a-k}}\right)(\genfrac{}{}{0ex}{}{i_a-m+k}{k})\right]$

$=\frac{r^a\left(\frac{r^{i_{(a+1)}+1}-r^m}{r-1}\right)}{(r-1{)}^a}-\sum _{k=0}^{a-1}\left[\left(\frac{r^{m+a-(k+1)}}{(r-1{)}^{a-k}}\right)\sum _{i_a=m}^{i_{(a+1)}}(\genfrac{}{}{0ex}{}{i_a-m+k}{k})\right]$

Shifting of starting and ending indices (see above for proof):

$=\frac{r^{i_{(a+1)}+a+1}-r^{m+a}}{(r-1{)}^{a+1}}-\sum _{k=0}^{a-1}\left[\left(\frac{r^{m+a-(k+1)}}{(r-1{)}^{a-k}}\right)\sum _{i_a=k}^{i_{(a+1)}-m+k}(\genfrac{}{}{0ex}{}{i_a}{k})\right]$

See combinations proof above:

$=\frac{r^{i_{(a+1)}+a+1}}{(r-1{)}^{a+1}}-\frac{r^{m+a}}{(r-1{)}^{a+1}}-\sum _{k=0}^{a-1}\left(\frac{r^{m+a-(k+1)}}{(r-1{)}^{a-k}}\right)(\genfrac{}{}{0ex}{}{i_{(a+1)}-m+k+1}{k+1})$

Shifting of starting and ending indices (see above for proof):

$=\frac{r^{i_{(a+1)}+a+1}}{(r-1{)}^{a+1}}-\frac{r^{m+a}}{(r-1{)}^{a+1}}-\sum _{k=1}^{(a+1)-1}\left(\frac{r^{m+a-((k-1)+1)}}{(r-1{)}^{a-(k-1)}}\right)(\genfrac{}{}{0ex}{}{i_{(a+1)}-m+(k-1)+1}{(k-1)+1})$

$=\frac{r^{i_{(a+1)}+a+1}}{(r-1{)}^{a+1}}-\frac{r^{m+a}}{(r-1{)}^{a+1}}-\sum _{k=1}^{(a+1)-1}\left(\frac{r^{m+a-k+1-1}}{(r-1{)}^{a-k+1}}\right)(\genfrac{}{}{0ex}{}{i_{(a+1)}-m+k}{k})$

Adding case k=0 to the summation, means that the same must be subtracted from the summation:

$=\frac{r^{i_{(a+1)}+(a+1)}}{(r-1{)}^{(a+1)}}-\frac{r^{m+a}}{(r-1{)}^{a+1}}-[\sum _{k=0}^{(a+1)-1}\left(\frac{r^{m+(a+1)-k-1}}{(r-1{)}^{(a+1)-k}}\right)(\genfrac{}{}{0ex}{}{i_{(a+1)}-m+k}{k})-\left(\frac{r^{m+a}}{(r-1{)}^{a+1}}\right)(\genfrac{}{}{0ex}{}{i_{(a+1)}-m}{0})]$

Terms cancel out.

$=\frac{r^{i_{(a+1)}+(a+1)}}{(r-1{)}^{(a+1)}}-\sum _{k=0}^{(a+1)-1}\left(\frac{r^{m+(a+1)-(k+1)}}{(r-1{)}^{(a+1)-k}}\right)(\genfrac{}{}{0ex}{}{i_{(a+1)}-m+k}{k})$

$=\frac{r^{i_{(a+1)}+(a+1)}}{(r-1{)}^{(a+1)}}-\sum _{k=0}^{(a+1)-1}\frac{r^{m+(a+1)-(k+1)}\left[\frac{(i_{(a+1)}-m+k)!}{(i_{(a+1)}-m)!}\right]}{(r-1{)}^{(a+1)-k}k!}$

$\sum _{i=m}^{i_{(a+1)}}{}^{(a+1)}{r}^i=\frac{r^{i_{(a+1)}+(a+1)}}{(r-1{)}^{(a+1)}}-\sum _{k=0}^{(a+1)-1}\frac{r^{m+(a+1)-(k+1)}\prod _{j=1}^k(i_{(a+1)}-m+j)}{k!(r-1{)}^{(a+1)-k}}$

Q.E.D.

A general formula for recursive summation series

First proof, used in second proof

One method

$\begin{array}{rlrl}n\ge m,& \sum _{i=m}^n[\sum _{j=m}^i(\genfrac{}{}{0ex}{}{i-j+k}{k})f(j)]& =& \sum _{j=m}^m(\genfrac{}{}{0ex}{}{(m)-j+k}{k})f(j)+\sum _{j=m}^{m+1}(\genfrac{}{}{0ex}{}{(m+1)-j+k}{k})f(j)\\ & & & +\sum _{j=m}^{m+2}(\genfrac{}{}{0ex}{}{(m+2)-j+k}{k})f(j)+\cdots +\sum _{j=m}^{n-2}(\genfrac{}{}{0ex}{}{(n-2)-j+k}{k})f(j)\\ & & & +\sum _{j=m}^{n-1}(\genfrac{}{}{0ex}{}{(n-1)-j+k}{k})f(j)+\sum _{j=m}^n(\genfrac{}{}{0ex}{}{(n)-j+k}{k})f(j)\\ & & =& [(\genfrac{}{}{0ex}{}{(m)-(m)+k}{k})f(m)]+[(\genfrac{}{}{0ex}{}{(m+1)-(m)+k}{k})f(m)\\ & & & +(\genfrac{}{}{0ex}{}{(m+1)-(m+1)+k}{k})f(m+1)]+[(\genfrac{}{}{0ex}{}{(m+2)-(m)+k}{k})f(m)\\ & & & +(\genfrac{}{}{0ex}{}{(m+2)-(m+1)+k}{k})f(m+1)+(\genfrac{}{}{0ex}{}{(m+2)-(m+2)+k}{k})f(m+2)]\\ & & & +\cdots +[(\genfrac{}{}{0ex}{}{(n-2)-(m)+k}{k})f(m)+(\genfrac{}{}{0ex}{}{(n-2)-(m+1)+k}{k})f(m+1)\\ & & & +(\genfrac{}{}{0ex}{}{(n-2)-(m+2)+k}{k})f(m+2)+\cdots +(\genfrac{}{}{0ex}{}{(n-2)-(n-4)+k}{k})f(n-4)\\ & & & +(\genfrac{}{}{0ex}{}{(n-2)-(n-3)+k}{k})f(n-3)+(\genfrac{}{}{0ex}{}{(n-2)-(n-2)+k}{k})f(n-2)]\\ & & & +[(\genfrac{}{}{0ex}{}{(n-1)-(m)+k}{k})f(m)+(\genfrac{}{}{0ex}{}{(n-1)-(m+1)+k}{k})f(m+1)\\ & & & +(\genfrac{}{}{0ex}{}{(n-1)-(m+2)+k}{k})f(m+2)+\cdots +(\genfrac{}{}{0ex}{}{(n-1)-(n-3)+k}{k})f(n-3)\\ & & & +(\genfrac{}{}{0ex}{}{(n-1)-(n-2)+k}{k})f(n-2)+(\genfrac{}{}{0ex}{}{(n-1)-(n-1)+k}{k})f(n-1)]\\ & & & +[(\genfrac{}{}{0ex}{}{(n)-(m)+k}{k})f(m)+(\genfrac{}{}{0ex}{}{(n)-(m+1)+k}{k})f(m+1)\\ & & & +(\genfrac{}{}{0ex}{}{(n)-(m+2)+k}{k})f(m+2)+\cdots +(\genfrac{}{}{0ex}{}{(n)-(n-2)+k}{k})f(n-2)\\ & & & +(\genfrac{}{}{0ex}{}{(n)-(n-1)+k}{k})f(n-1)+(\genfrac{}{}{0ex}{}{(n)-(n)+k}{k})f(n)]\\ & & =& [(\genfrac{}{}{0ex}{}{k}{k})f(m)]+[(\genfrac{}{}{0ex}{}{1+k}{k})f(m)+(\genfrac{}{}{0ex}{}{k}{k})f(m+1)]\\ & & & +[(\genfrac{}{}{0ex}{}{2+k}{k})f(m)+(\genfrac{}{}{0ex}{}{1+k}{k})f(m+1)+(\genfrac{}{}{0ex}{}{k}{k})f(m)]\\ & & & +\cdots +[(\genfrac{}{}{0ex}{}{n-2-m+k}{k})f(m)+(\genfrac{}{}{0ex}{}{n-3-m+k}{k})f(m+1)\\ & & & +(\genfrac{}{}{0ex}{}{n-4-m+k}{k})f(m+2)+\cdots +(\genfrac{}{}{0ex}{}{2+k}{k})f(n-4)\\ & & & +(\genfrac{}{}{0ex}{}{1+k}{k})f(n-3)+(\genfrac{}{}{0ex}{}{k}{k})f(n-2)]\\ & & & +[(\genfrac{}{}{0ex}{}{n-1-m+k}{k})f(m)+(\genfrac{}{}{0ex}{}{n-2-m+k}{k})f(m+1)\\ & & & +(\genfrac{}{}{0ex}{}{n-3-m+k}{k})f(m+2)+\cdots +(\genfrac{}{}{0ex}{}{2+k}{k})f(n-3)\\ & & & +(\genfrac{}{}{0ex}{}{1+k}{k})f(n-2)+(\genfrac{}{}{0ex}{}{k}{k})f(n-1)]\\ & & & +[(\genfrac{}{}{0ex}{}{n-m+k}{k})f(m)+(\genfrac{}{}{0ex}{}{n-1-m+k}{k})f(m+1)\\ & & & +(\genfrac{}{}{0ex}{}{n-2-m+k}{k})f(m+2)+\cdots +(\genfrac{}{}{0ex}{}{2+k}{k})f(n-2)\\ & & & +(\genfrac{}{}{0ex}{}{1+k}{k})f(n-1)+(\genfrac{}{}{0ex}{}{k}{k})f(n)]\\ & & =& f(m)[(\genfrac{}{}{0ex}{}{k}{k})+(\genfrac{}{}{0ex}{}{1+k}{k})+(\genfrac{}{}{0ex}{}{2+k}{k})\\ & & & +\cdots +(\genfrac{}{}{0ex}{}{n-2-m+k}{k})+(\genfrac{}{}{0ex}{}{n-1-m+k}{k})+(\genfrac{}{}{0ex}{}{n-m+k}{k})]\\ & & & +f(m+1)[(\genfrac{}{}{0ex}{}{k}{k})+(\genfrac{}{}{0ex}{}{1+k}{k})+(\genfrac{}{}{0ex}{}{2+k}{k})\\ & & & +\cdots +(\genfrac{}{}{0ex}{}{n-3-m+k}{k})+(\genfrac{}{}{0ex}{}{n-2-m+k}{k})+(\genfrac{}{}{0ex}{}{n-1-m+k}{k})]\\ & & & +f(m+2)[(\genfrac{}{}{0ex}{}{k}{k})+(\genfrac{}{}{0ex}{}{1+k}{k})+(\genfrac{}{}{0ex}{}{2+k}{k})\\ & & & +\cdots +(\genfrac{}{}{0ex}{}{n-4-m+k}{k})+(\genfrac{}{}{0ex}{}{n-3-m+k}{k})+(\genfrac{}{}{0ex}{}{n-2-m+k}{k})]\\ & & & +\cdots +f(n-2)[(\genfrac{}{}{0ex}{}{k}{k})+(\genfrac{}{}{0ex}{}{1+k}{k})+(\genfrac{}{}{0ex}{}{2+k}{k})]\\ & & & +f(n-1)[(\genfrac{}{}{0ex}{}{k}{k})+(\genfrac{}{}{0ex}{}{1+k}{k})]+f(n)\left[(\genfrac{}{}{0ex}{}{k}{k})\right]\\ & & =& \sum _{j=m}^n(\genfrac{}{}{0ex}{}{n-j+k+1}{k+1})f(j)\end{array}$

Inductive method

$\begin{array}{rlrl}n\ge m,& \sum _{i=m}^n[\sum _{j=m}^i(\genfrac{}{}{0ex}{}{i-j+k}{k})f(j)]& =& \sum _{j=m}^n(\genfrac{}{}{0ex}{}{n-j+k+1}{k+1})f(j)\\ n=m,& \sum _{i=m}^m[\sum _{j=m}^i(\genfrac{}{}{0ex}{}{i-j+k}{k})f(j)]& =& \sum _{j=m}^m(\genfrac{}{}{0ex}{}{(m)-j+k}{k})f(j)\\ & & =& (\genfrac{}{}{0ex}{}{m-(m)+k}{k})f(m)=(\genfrac{}{}{0ex}{}{k}{k})f(m)=f(m)=(\genfrac{}{}{0ex}{}{k+1}{k+1})f(m)\\ & & =& (\genfrac{}{}{0ex}{}{(m)-(m)+k+1}{k+1})f(m)=\sum _{j=m}^m(\genfrac{}{}{0ex}{}{(m)-j+k+1}{k+1})f(j)\\ n=x,& \sum _{i=m}^x[\sum _{j=m}^i(\genfrac{}{}{0ex}{}{i-j+k}{k})f(j)]& =& \sum _{j=m}^x(\genfrac{}{}{0ex}{}{x-j+k+1}{k+1})f(j)\\ n=x+1,& \sum _{i=m}^{x+1}[\sum _{j=m}^i(\genfrac{}{}{0ex}{}{i-j+k}{k})f(j)]& =& \sum _{j=m}^{x+1}(\genfrac{}{}{0ex}{}{(x+1)-j+k}{k})f(j)+\sum _{i=m}^x[\sum _{j=m}^i(\genfrac{}{}{0ex}{}{i-j+k}{k})f(j)]\\ & & =& \sum _{j=m}^{x+1}(\genfrac{}{}{0ex}{}{(x+1)-j+k}{k})f(j)+\sum _{j=m}^x(\genfrac{}{}{0ex}{}{x-j+k+1}{k+1})f(j)\\ & & =& (\genfrac{}{}{0ex}{}{(x+1)-(x+1)+k}{k})f(x+1)\\ & & & +\sum _{j=m}^x(\genfrac{}{}{0ex}{}{(x+1)-j+k}{k})f(j)+\sum _{j=m}^x(\genfrac{}{}{0ex}{}{x-j+k+1}{k+1})f(j)\\ & & =& f(x+1)+\sum _{j=m}^x(\genfrac{}{}{0ex}{}{x-j+k+1}{k})f(j)+\sum _{j=m}^x(\genfrac{}{}{0ex}{}{x-j+k+1}{k+1})f(j)\\ & & =& f(x+1)+\sum _{j=m}^x[(\genfrac{}{}{0ex}{}{x-j+k+1}{k})+(\genfrac{}{}{0ex}{}{x-j+k+1}{k+1})]f(j)\\ & & =& f(x+1)+\sum _{j=m}^x(\genfrac{}{}{0ex}{}{x-j+k+2}{k+1})f(j)\\ & & =& (\genfrac{}{}{0ex}{}{(x+1)-(x+1)+k+1}{k+1})f(x+1)+\sum _{j=m}^x(\genfrac{}{}{0ex}{}{(x+1)-j+k+1}{k+1})f(j)\\ & & =& \sum _{j=m}^{x+1}(\genfrac{}{}{0ex}{}{(x+1)-j+k+1}{k+1})f(j)\end{array}$

Second proof, this one for the general formula for recursive summation series

$\begin{array}{rlrl}p\ge 1,& \sum _{i=m}^{i_p}{}^{p}f(i)& =& \sum _{i=m}^{i_p}(\genfrac{}{}{0ex}{}{i_p-i+p-1}{p-1})f(i)\\ p=1,& \sum _{i=m}^{i_1}{}^{1}f(i)& =& \sum _{i=m}^{i_1}(\genfrac{}{}{0ex}{}{i_1-i}{0})f(i)=\sum _{i=m}^{i_1}f(i)\\ p=s,& \sum _{i=m}^{i_s}{}^{s}f(i)& =& \sum _{i=m}^{i_s}(\genfrac{}{}{0ex}{}{i_s-i+s-1}{s-1})f(i)\\ p=s+1,& \sum _{i=m}^{i_{s+1}}{}^{s+1}f(i)& =& \sum _{i_s=m}^{i_{s+1}}[\sum _{i=m}^{i_s}{}^s{f}(i)]\\ & & =& \sum _{i_s=m}^{i_{s+1}}[\sum _{i=m}^{i_s}(\genfrac{}{}{0ex}{}{i_s-i+s-1}{s-1})f(i)]\\ & & =& \sum _{i=m}^{i_{s+1}}(\genfrac{}{}{0ex}{}{i_{s+1}-i+(s+1)-1}{(s+1)-1})f(i)\\ \end{array}$

Miscellaneous items (some valid, some not)

$\begin{array}{rl}& =\sum _{i=m}^{i_{s+1}}f(i)\sum _{j=0}^{i_{s+1}-i}(\genfrac{}{}{0ex}{}{j+s-1}{s-1})\\ & =\sum _{i=m}^{i_{s+1}}f(i)\sum _{j=s-1}^{i_{s+1}-i+s-1}(\genfrac{}{}{0ex}{}{[j-(s-1)]+s-1}{s-1})\\ & =\sum _{i=m}^{i_{s+1}}f(i)\sum _{j=s-1}^{i_{s+1}-i+s-1}(\genfrac{}{}{0ex}{}{j}{s-1})\\ & =\sum _{i=m}^{i_{s+1}}(\genfrac{}{}{0ex}{}{i_{s+1}-i+(s+1)-1}{(s+1)-1})f(i)\end{array}$

$\begin{array}{rl}& =\sum _{i=m}^{i_{s+1}}(\genfrac{}{}{0ex}{}{i_{s+1}-i+s-1}{s-1})\sum _{j=m}^{i}f(j)\end{array}$

$f(x)=\frac{n-0}{h-0}x+0=\frac{n}{h}x$

$F(x)=\frac{n}{2h}{x}^2+C$

$g(x)=\frac{n-b}{h-0}x+b=\frac{n-b}{h}x+b$

$G(x)=\frac{n-b}{2h}{x}^2+bx+C$

$A_f=F(h)-F(0)=[\frac{n}{2h}(h{)}^2+C]-[\frac{n}{2h}(0{)}^2+C]=\frac{1}{2}nh$

$A_g=G(h)-G(0)=[\frac{n-b}{2h}(h{)}^2+b(h)+C]-[\frac{n-b}{2h}(0{)}^2+b(0)+C]=\frac{1}{2}nh-\frac{1}{2}bh+bh=\frac{1}{2}nh+\frac{1}{2}bh$

$A=A_g-A_f=(\frac{1}{2}nh+\frac{1}{2}bh)-\left(\frac{1}{2}nh\right)=\frac{1}{2}\mathbf{𝐛}\mathbf{𝐡}$

$\begin{array}{rl}& =(i_{k+1}-m+1)(\genfrac{}{}{0ex}{}{k-1}{k-1})\sum _{i=m}^{i_{k+1}}f(i)+(i_{k+1}-m)(\genfrac{}{}{0ex}{}{k}{k-1})\sum _{i=m}^{i_{k+1}-1}f(i)\\ & +(i_{k+1}-m-1)(\genfrac{}{}{0ex}{}{k+1}{k-1})\sum _{i=m}^{i_{k+1}-2}f(i)+\dots +3(\genfrac{}{}{0ex}{}{i_{k+1}-m+2+k-1}{k-1})\sum _{i=m}^{m+2}f(i)\\ & +2(\genfrac{}{}{0ex}{}{i_{k+1}-m+1+k-1}{k-1})\sum _{i=m}^{m+1}f(i)+(\genfrac{}{}{0ex}{}{i_{k+1}-m+k-1}{k-1})\sum _{i=m}^{m}f(i)\end{array}$

これ、ちょっとちがうね。

$\begin{array}{rl}& =f(m)\sum _{j=m}^{i_{k+1}}(i_{k+1}-j+1)(\genfrac{}{}{0ex}{}{j-m+k-1}{k-1})+f(m+1)\sum _{j=m}^{i_{k+1}-1}(i_{k+1}-j+1)(\genfrac{}{}{0ex}{}{j-m+k-1}{k-1})\\ & +f(m+2)\sum _{j=m}^{i_{k+1}-2}(i_{k+1}-j+1)(\genfrac{}{}{0ex}{}{j-m+k-1}{k-1})+\dots +f(i_{k+1}-2)\sum _{j=m}^{m+2}(i_{k+1}-j+1)(\genfrac{}{}{0ex}{}{j-m+k-1}{k-1})\\ & +f(i_{k+1}-1)\sum _{j=m}^{m+1}(i_{k+1}-j+1)(\genfrac{}{}{0ex}{}{j-m+k-1}{k-1})+f(i_{k+1})\sum _{j=m}^m(i_{k+1}-j+1)(\genfrac{}{}{0ex}{}{j-m+k-1}{k-1})\end{array}$

$=\sum _{i=m}^{i_{k+1}}f(i)\sum _{j=0}^{i_{k+1}-i}(i_{k+1}-j-m+1)(\genfrac{}{}{0ex}{}{j+k-1}{k-1})$ これもちがう。