Alternative account: User:Beneficii

Basic definition of a sum

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

Recursive summation

Where ${\displaystyle p\geq 0}$:

${\displaystyle \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})\,}$

${\displaystyle \sum _{i=m}^{i_{0}}\!{}^{0}\ {\mathit {f}}(i)={\mathit {f}}(i_{0})\,}$

${\displaystyle \sum _{i=m}^{i_{1}}\!{}^{1}\ {\mathit {f}}(i)=\sum _{i_{0}=m}^{i_{1}}{\mathit {f}}(i_{0})\,}$

${\displaystyle \mathrm {If\ } {\mathit {g}}(n)=\sum _{i=m}^{n}\!{}^{-p}\,{\mathit {f}}(i),\ \mathrm {then\ } {\mathit {f}}(n)=\sum _{i=m}^{n}\!{}^{p}\,{\mathit {g}}(i).\,}$

Where ${\displaystyle p>0}$:

${\displaystyle \sum _{i=m}^{i_{p}}\!{}^{p}\ {\mathit {f}}(i)=\sum _{i_{p-1}=m}^{i_{p}}\left[\sum _{i=m}^{i_{p-1}}\!{}^{p-1}\,{\mathit {f}}(i)\right]\,}$

${\displaystyle \sum _{i_{p-1}=m}^{i_{p}}\left[\sum _{i=m}^{i_{p-1}}\!{}^{p-1}\,{\mathit {f}}(i)\right]=\sum _{i=m}^{m}\!{}^{p-1}\,{\mathit {f}}(i)+\sum _{i=m}^{m+1}\!{}^{p-1}\,{\mathit {f}}(i)+\sum _{i=m}^{m+2}\!{}^{p-1}\,{\mathit {f}}(i)+\,...+\,\sum _{i=m}^{i_{p}-2}\!{}^{p-1}\,{\mathit {f}}(i)+\sum _{i=m}^{i_{p}-1}\!{}^{p-1}\,{\mathit {f}}(i)+\sum _{i=m}^{i_{p}}\!{}^{p-1}\,{\mathit {f}}(i)\,}$

Shifting of starting and ending indices

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

Proof of the equality of the shifting of indices:

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

Smaller summation notation

${\displaystyle \,\!\sum _{i=m}^{n}\!{}^{p}\ {\mathit {f}}(i)=\textstyle \!{}_{p}\!\sum _{i=m}^{n}{\mathit {f}}(i)\,}$

Recursive geometric series

${\displaystyle \,\!{\begin{array}{lcl}{}_{p}\!\sum _{i=m}^{n}r^{i}&=&{r^{n+p} \over (r-1)^{p}}-\sum _{k=0}^{p-1}{r^{m+p-(k+1)}\prod _{j=1}^{k}(n-m+j) \over k!(r-1)^{p-k}}\\&=&{r^{n+p} \over (r-1)^{p}}-\sum _{k=0}^{p-1}{r^{m+p-(k+1)}{(n-m+k)! \over (n-m)!} \over (r-1)^{p-k}k!}\\&=&{r^{n+p} \over (r-1)^{p}}-\sum _{k=0}^{p-1}\left({r^{m+p-(k+1)} \over (r-1)^{p-k}}\right){{n-m+k} \choose k}\end{array}}\,}$

Combinations proof (used in below proof)

${\displaystyle \mathrm {For\ non-negative\ integers\ } q\ \mathrm {and\ } t\geq q,\quad \sum _{z=q}^{t}{z \choose q}={t+1 \choose q+1}.\,}$

${\displaystyle t=q,\quad \sum _{z=q}^{q}{z \choose q}={q \choose q}=1={q+1 \choose q+1}\,}$

${\displaystyle t=c,\quad \sum _{z=q}^{c}{z \choose q}={c+1 \choose q+1}\,}$

${\displaystyle t=c+1,\quad \sum _{z=q}^{c+1}{z \choose q}=\sum _{z=q}^{c}{z \choose q}+{c+1 \choose q}={c+1 \choose q+1}+{c+1 \choose q}={(c+1)+1 \choose q+1}\,}$

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

Definition

${\displaystyle \mathrm {For\ a\ real\ number\ } r\neq 1\ \mathrm {and\ non-negative\ integers\ } m,\ p,\ \mathrm {and\ } i_{p},\ \mathrm {where\ } i_{p}\geq m,}$

${\displaystyle \sum _{i=m}^{i_{p}}\!\!{}^{p}\,r^{i}={r^{i_{p}+p} \over (r-1)^{p}}-\sum _{k=0}^{p-1}{r^{m+p-(k+1)}\prod _{j=1}^{k}(i_{p}-m+j) \over k!(r-1)^{p-k}}.\,}$

Base case (and some specific examples)

${\displaystyle p=0,\quad \sum _{i=m}^{i_{0}}\!\!{}^{0}\,r^{i}={\cfrac {r^{i_{0}+0}}{(r-1)^{0}}}=r^{i_{0}}\,}$

${\displaystyle p=1,\quad \sum _{i=m}^{i_{1}}\!\!{}^{1}\,r^{i}={\cfrac {r^{i_{1}+1}}{(r-1)^{1}}}-{\cfrac {r^{m}}{0!(r-1)^{1}}}={\cfrac {r^{i_{1}+1}-r^{m}}{r-1}}\,}$

${\displaystyle p=2,\quad \sum _{i=m}^{i_{2}}\!\!{}^{2}\,r^{i}={\cfrac {r^{i_{2}+2}}{(r-1)^{2}}}-{\cfrac {r^{m+1}}{0!(r-1)^{2}}}-{\cfrac {r^{m}(i_{2}-m+1)}{1!(r-1)^{1}}}={\cfrac {{\cfrac {r^{i_{2}+2}-r^{m+1}}{r-1}}-r^{m}(i_{2}-m+1)}{r-1}}\,}$

${\displaystyle p=3,\,}$

${\displaystyle \quad \sum _{i=m}^{i_{3}}\!\!{}^{3}\,r^{i}={\cfrac {r^{i_{3}+3}}{(r-1)^{3}}}-{\cfrac {r^{m+2}}{0!(r-1)^{3}}}-{\cfrac {r^{m+1}(i_{3}-m+1)}{1!(r-1)^{2}}}-{\cfrac {r^{m}(i_{3}-m+1)(i_{3}-m+2)}{2!(r-1)^{1}}}\,}$

${\displaystyle ={\cfrac {{\cfrac {{\cfrac {r^{i_{3}+3}-r^{m+2}}{r-1}}-r^{m+1}(i_{3}-m+1)}{r-1}}-{\tfrac {1}{2}}r^{m}(i_{3}-m+1)(i_{3}-m+2)}{r-1}}\,}$

${\displaystyle p=4,\,}$

${\displaystyle \quad \sum _{i=m}^{i_{4}}\!\!{}^{4}\,r^{i}={\cfrac {r^{i_{4}+4}}{(r-1)^{4}}}-{\cfrac {r^{m+3}}{0!(r-1)^{4}}}-{\cfrac {r^{m+2}(i_{4}-m+1)}{1!(r-1)^{3}}}-{\cfrac {r^{m+1}(i_{4}-m+1)(i_{4}-m+2)}{2!(r-1)^{2}}}\,}$

${\displaystyle -{\cfrac {r^{m}(i_{4}-m+1)(i_{4}-m+2)(i_{4}-m+3)}{3!(r-1)^{1}}}\,}$

${\displaystyle ={\cfrac {{\cfrac {{\cfrac {{\cfrac {r^{i_{4}+4}-r^{m+3}}{r-1}}-r^{m+2}(i_{4}-m+1)}{r-1}}-{\tfrac {1}{2}}r^{m+1}(i_{4}-m+1)(i_{4}-m+2)}{r-1}}-{\tfrac {1}{6}}r^{m}(i_{4}-m+1)(i_{4}-m+2)(i_{4}-m+3)}{r-1}}\,}$

Inductive step

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

${\displaystyle p=a+1,\quad \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]\,}$

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

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

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

${\displaystyle ={r^{a}\sum _{{i_{a}}=m}^{i_{(a+1)}}\left(r^{i_{a}}\right) \over (r-1)^{a}}-\sum _{{i_{a}}=m}^{i_{(a+1)}}\left[\sum _{k=0}^{a-1}\left({r^{m+a-(k+1)} \over (r-1)^{a-k}}\right){i_{a}-m+k \choose k}\right]\,}$

${\displaystyle ={r^{a}\left({r^{i_{(a+1)}+1}-r^{m} \over r-1}\right) \over (r-1)^{a}}-\sum _{k=0}^{a-1}\left[\left({r^{m+a-(k+1)} \over (r-1)^{a-k}}\right)\sum _{{i_{a}}=m}^{i_{(a+1)}}{i_{a}-m+k \choose k}\right]\,}$

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

${\displaystyle ={r^{i_{(a+1)}+a+1}-r^{m+a} \over (r-1)^{a+1}}-\sum _{k=0}^{a-1}\left[\left({r^{m+a-(k+1)} \over (r-1)^{a-k}}\right)\sum _{i_{a}=k}^{i_{(a+1)}-m+k}{i_{a} \choose k}\right]\,}$

See combinations proof above:

${\displaystyle ={r^{i_{(a+1)}+a+1} \over (r-1)^{a+1}}-{r^{m+a} \over (r-1)^{a+1}}-\sum _{k=0}^{a-1}\left({r^{m+a-(k+1)} \over (r-1)^{a-k}}\right){i_{(a+1)}-m+k+1 \choose k+1}\,}$

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

${\displaystyle ={r^{i_{(a+1)}+a+1} \over (r-1)^{a+1}}-{r^{m+a} \over (r-1)^{a+1}}-\sum _{k=1}^{(a+1)-1}\left({r^{m+a-((k-1)+1)} \over (r-1)^{a-(k-1)}}\right){i_{(a+1)}-m+(k-1)+1 \choose (k-1)+1}\,}$

${\displaystyle ={r^{i_{(a+1)}+a+1} \over (r-1)^{a+1}}-{r^{m+a} \over (r-1)^{a+1}}-\sum _{k=1}^{(a+1)-1}\left({r^{m+a-k+1-1} \over (r-1)^{a-k+1}}\right){i_{(a+1)}-m+k \choose k}\,}$

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

${\displaystyle ={r^{i_{(a+1)}+(a+1)} \over (r-1)^{(a+1)}}-{r^{m+a} \over (r-1)^{a+1}}-\left[\sum _{k=0}^{(a+1)-1}\left({r^{m+(a+1)-k-1} \over (r-1)^{(a+1)-k}}\right){i_{(a+1)}-m+k \choose k}-\left({r^{m+a} \over (r-1)^{a+1}}\right){i_{(a+1)}-m \choose 0}\right]\,}$

Terms cancel out.

${\displaystyle ={r^{i_{(a+1)}+(a+1)} \over (r-1)^{(a+1)}}-\sum _{k=0}^{(a+1)-1}\left({r^{m+(a+1)-(k+1)} \over (r-1)^{(a+1)-k}}\right){i_{(a+1)}-m+k \choose k}\,}$

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

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

Q.E.D.

A general formula for recursive summation series

First proof, used in second proof

One method

${\displaystyle {\begin{aligned}n\geq m,&\sum _{i=m}^{n}\left[\sum _{j=m}^{i}{i-j+k \choose k}f(j)\right]&=&\sum _{j=m}^{m}{(m)-j+k \choose k}f(j)+\sum _{j=m}^{m+1}{(m+1)-j+k \choose k}f(j)\\&&&+\sum _{j=m}^{m+2}{(m+2)-j+k \choose k}f(j)+\cdots +\sum _{j=m}^{n-2}{(n-2)-j+k \choose k}f(j)\\&&&+\sum _{j=m}^{n-1}{(n-1)-j+k \choose k}f(j)+\sum _{j=m}^{n}{(n)-j+k \choose k}f(j)\\&&=&\left[{(m)-(m)+k \choose k}f(m)\right]+\left[{(m+1)-(m)+k \choose k}f(m)\right.\\&&&\left.+{(m+1)-(m+1)+k \choose k}f(m+1)\right]+\left[{(m+2)-(m)+k \choose k}f(m)\right.\\&&&\left.+{(m+2)-(m+1)+k \choose k}f(m+1)+{(m+2)-(m+2)+k \choose k}f(m+2)\right]\\&&&+\cdots +\left[{(n-2)-(m)+k \choose k}f(m)+{(n-2)-(m+1)+k \choose k}f(m+1)\right.\\&&&\left.+{(n-2)-(m+2)+k \choose k}f(m+2)+\cdots +{(n-2)-(n-4)+k \choose k}f(n-4)\right.\\&&&\left.+{(n-2)-(n-3)+k \choose k}f(n-3)+{(n-2)-(n-2)+k \choose k}f(n-2)\right]\\&&&+\left[{(n-1)-(m)+k \choose k}f(m)+{(n-1)-(m+1)+k \choose k}f(m+1)\right.\\&&&\left.+{(n-1)-(m+2)+k \choose k}f(m+2)+\cdots +{(n-1)-(n-3)+k \choose k}f(n-3)\right.\\&&&\left.+{(n-1)-(n-2)+k \choose k}f(n-2)+{(n-1)-(n-1)+k \choose k}f(n-1)\right]\\&&&+\left[{(n)-(m)+k \choose k}f(m)+{(n)-(m+1)+k \choose k}f(m+1)\right.\\&&&\left.+{(n)-(m+2)+k \choose k}f(m+2)+\cdots +{(n)-(n-2)+k \choose k}f(n-2)\right.\\&&&\left.+{(n)-(n-1)+k \choose k}f(n-1)+{(n)-(n)+k \choose k}f(n)\right]\\&&=&\left[{k \choose k}f(m)\right]+\left[{1+k \choose k}f(m)+{k \choose k}f(m+1)\right]\\&&&+\left[{2+k \choose k}f(m)+{1+k \choose k}f(m+1)+{k \choose k}f(m)\right]\\&&&+\cdots +\left[{n-2-m+k \choose k}f(m)+{n-3-m+k \choose k}f(m+1)\right.\\&&&\left.+{n-4-m+k \choose k}f(m+2)+\cdots +{2+k \choose k}f(n-4)\right.\\&&&\left.+{1+k \choose k}f(n-3)+{k \choose k}f(n-2)\right]\\&&&+\left[{n-1-m+k \choose k}f(m)+{n-2-m+k \choose k}f(m+1)\right.\\&&&\left.+{n-3-m+k \choose k}f(m+2)+\cdots +{2+k \choose k}f(n-3)\right.\\&&&\left.+{1+k \choose k}f(n-2)+{k \choose k}f(n-1)\right]\\&&&+\left[{n-m+k \choose k}f(m)+{n-1-m+k \choose k}f(m+1)\right.\\&&&\left.+{n-2-m+k \choose k}f(m+2)+\cdots +{2+k \choose k}f(n-2)\right.\\&&&\left.+{1+k \choose k}f(n-1)+{k \choose k}f(n)\right]\\&&=&f(m)\left[{k \choose k}+{1+k \choose k}+{2+k \choose k}\right.\\&&&\left.+\cdots +{n-2-m+k \choose k}+{n-1-m+k \choose k}+{n-m+k \choose k}\right]\\&&&+f(m+1)\left[{k \choose k}+{1+k \choose k}+{2+k \choose k}\right.\\&&&\left.+\cdots +{n-3-m+k \choose k}+{n-2-m+k \choose k}+{n-1-m+k \choose k}\right]\\&&&+f(m+2)\left[{k \choose k}+{1+k \choose k}+{2+k \choose k}\right.\\&&&\left.+\cdots +{n-4-m+k \choose k}+{n-3-m+k \choose k}+{n-2-m+k \choose k}\right]\\&&&+\cdots +f(n-2)\left[{k \choose k}+{1+k \choose k}+{2+k \choose k}\right]\\&&&+f(n-1)\left[{k \choose k}+{1+k \choose k}\right]+f(n)\left[{k \choose k}\right]\\&&=&\sum _{j=m}^{n}{n-j+k+1 \choose k+1}f(j)\end{aligned}}\,}$

Inductive method

${\displaystyle {\begin{aligned}n\geq m,\quad &\sum _{i=m}^{n}\left[\sum _{j=m}^{i}{i-j+k \choose k}f(j)\right]&=&\sum _{j=m}^{n}{n-j+k+1 \choose k+1}f(j)\\n=m,\quad &\sum _{i=m}^{m}\left[\sum _{j=m}^{i}{i-j+k \choose k}f(j)\right]&=&\sum _{j=m}^{m}{(m)-j+k \choose k}f(j)\\&&=&{m-(m)+k \choose k}f(m)={k \choose k}f(m)=f(m)={k+1 \choose k+1}f(m)\\&&=&{(m)-(m)+k+1 \choose k+1}f(m)=\sum _{j=m}^{m}{(m)-j+k+1 \choose k+1}f(j)\\n=x,\quad &\sum _{i=m}^{x}\left[\sum _{j=m}^{i}{i-j+k \choose k}f(j)\right]&=&\sum _{j=m}^{x}{x-j+k+1 \choose k+1}f(j)\\n=x+1,\quad &\sum _{i=m}^{x+1}\left[\sum _{j=m}^{i}{i-j+k \choose k}f(j)\right]&=&\sum _{j=m}^{x+1}{(x+1)-j+k \choose k}f(j)+\sum _{i=m}^{x}\left[\sum _{j=m}^{i}{i-j+k \choose k}f(j)\right]\\&&=&\sum _{j=m}^{x+1}{(x+1)-j+k \choose k}f(j)+\sum _{j=m}^{x}{x-j+k+1 \choose k+1}f(j)\\&&=&{(x+1)-(x+1)+k \choose k}f(x+1)\\&&&+\sum _{j=m}^{x}{(x+1)-j+k \choose k}f(j)+\sum _{j=m}^{x}{x-j+k+1 \choose k+1}f(j)\\&&=&f(x+1)+\sum _{j=m}^{x}{x-j+k+1 \choose k}f(j)+\sum _{j=m}^{x}{x-j+k+1 \choose k+1}f(j)\\&&=&f(x+1)+\sum _{j=m}^{x}\left[{x-j+k+1 \choose k}+{x-j+k+1 \choose k+1}\right]f(j)\\&&=&f(x+1)+\sum _{j=m}^{x}{x-j+k+2 \choose k+1}f(j)\\&&=&{(x+1)-(x+1)+k+1 \choose k+1}f(x+1)+\sum _{j=m}^{x}{(x+1)-j+k+1 \choose k+1}f(j)\\&&=&\sum _{j=m}^{x+1}{(x+1)-j+k+1 \choose k+1}f(j)\end{aligned}}\,}$