# User:Ans/Sum of Sequence of Nth Powers

## Theorem

${\displaystyle \forall k\in \mathbb {N} _{0}\forall n\in \mathbb {N} _{0}:\operatorname {sum\_of\_powers} (k,n)=\sum _{i\mathop {=} 1}^{n}i^{k}={\frac {1}{k+1}}\left({\left({n+1}\right)^{k+1}-1-\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}\operatorname {sum\_of\_powers} (j,n)}\right)}$

## Proof by Sum of Differences of One Higher Order Powers

{\displaystyle {\begin{aligned}\sum _{i\mathop {=} 1}^{n}\left({\left({i+1}\right)^{k+1}-i^{k+1}}\right)&=\sum _{i\mathop {=} 1}^{n}\left({\sum _{j\mathop {=} 0}^{k+1}{\binom {k+1}{j}}i^{j}-i^{k+1}}\right)&{\text{[[Binomial Theorem]]}}\\&=\sum _{i\mathop {=} 1}^{n}\left({{\binom {k+1}{k+1}}i^{k+1}+{\binom {k+1}{k}}i^{k}+\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}i^{j}-i^{k+1}}\right)&{\text{recursive definition}}\\&=\sum _{i\mathop {=} 1}^{n}\left({(k+1)i^{k}+\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}i^{j}}\right)\\&=(k+1)\sum _{i\mathop {=} 1}^{n}i^{k}+\sum _{i\mathop {=} 1}^{n}\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}i^{j}&{\text{[[Summation is Linear]]}}\\&=(k+1)\sum _{i\mathop {=} 1}^{n}i^{k}+\sum _{j\mathop {=} 0}^{k-1}\sum _{i\mathop {=} 1}^{n}{\binom {k+1}{j}}i^{j}&{\text{[[Summation is Linear]]}}\\&=(k+1)\sum _{i\mathop {=} 1}^{n}i^{k}+\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}\sum _{i\mathop {=} 1}^{n}i^{j}&{\text{[[Summation is Linear]]}}\\\end{aligned}}}

On the other hand:

{\displaystyle {\begin{aligned}\sum _{i\mathop {=} 1}^{n}\left({\left({i+1}\right)^{k+1}-i^{k+1}}\right)&=\sum _{i\mathop {=} 1}^{n}\left({i+1}\right)^{k+1}-\sum _{i\mathop {=} 1}^{n}i^{k+1}&{\text{[[Summation is Linear]]}}\\&=\sum _{i\mathop {=} 1}^{n}\left({i+1}\right)^{k+1}-\sum _{i\mathop {=} 1}^{n}i^{k+1}+1^{k+1}-1^{k+1}\\&=1^{k+1}+\sum _{i\mathop {=} 2}^{n+1}i^{k+1}-\sum _{i\mathop {=} 1}^{n}i^{k+1}-1^{k+1}\\&=\sum _{i\mathop {=} 1}^{n+1}i^{k+1}-\sum _{i\mathop {=} 1}^{n}i^{k+1}-1^{k+1}\\&=\left({n+1}\right)^{k+1}+\sum _{i\mathop {=} 1}^{n}i^{k+1}-\sum _{i\mathop {=} 1}^{n}i^{k+1}-1^{k+1}&{\text{recursive definition}}\\&=\left({n+1}\right)^{k+1}-1\\\end{aligned}}}

Therefore:

${\displaystyle {\begin{array}{rrl}&\displaystyle (k+1)\sum _{i\mathop {=} 1}^{n}i^{k}+\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}\sum _{i\mathop {=} 1}^{n}i^{j}&\displaystyle =\left({n+1}\right)^{k+1}-1\\\implies &\displaystyle (k+1)\sum _{i\mathop {=} 1}^{n}i^{k}&\displaystyle =\left({n+1}\right)^{k+1}-1-\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}\sum _{i\mathop {=} 1}^{n}i^{j}\\\end{array}}}$

Therefore:

{\displaystyle {\begin{aligned}\operatorname {sum\_of\_powers} (k,n)=\sum _{i\mathop {=} 1}^{n}i^{k}&={\frac {1}{k+1}}\left({\left({n+1}\right)^{k+1}-1-\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}\sum _{i\mathop {=} 1}^{n}i^{j}}\right)\\&={\frac {1}{k+1}}\left({\left({n+1}\right)^{k+1}-1-\sum _{j\mathop {=} 0}^{k-1}{\binom {k+1}{j}}\operatorname {sum\_of\_powers} (j,n)}\right)\\\end{aligned}}}