From Wikibooks, open books for an open world
∀
k
∈
N
0
∀
n
∈
N
0
:
s
u
m
_
o
f
_
p
o
w
e
r
s
(
k
,
n
)
=
∑
i
=
1
n
i
k
=
1
k
+
1
(
(
n
+
1
)
k
+
1
−
1
−
∑
j
=
0
k
−
1
(
k
+
1
j
)
s
u
m
_
o
f
_
p
o
w
e
r
s
(
j
,
n
)
)
{\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)}
∑
i
=
1
n
(
(
i
+
1
)
k
+
1
−
i
k
+
1
)
=
∑
i
=
1
n
(
∑
j
=
0
k
+
1
(
k
+
1
j
)
i
j
−
i
k
+
1
)
[[Binomial Theorem]]
=
∑
i
=
1
n
(
(
k
+
1
k
+
1
)
i
k
+
1
+
(
k
+
1
k
)
i
k
+
∑
j
=
0
k
−
1
(
k
+
1
j
)
i
j
−
i
k
+
1
)
recursive definition
=
∑
i
=
1
n
(
(
k
+
1
)
i
k
+
∑
j
=
0
k
−
1
(
k
+
1
j
)
i
j
)
=
(
k
+
1
)
∑
i
=
1
n
i
k
+
∑
i
=
1
n
∑
j
=
0
k
−
1
(
k
+
1
j
)
i
j
[[Summation is Linear]]
=
(
k
+
1
)
∑
i
=
1
n
i
k
+
∑
j
=
0
k
−
1
∑
i
=
1
n
(
k
+
1
j
)
i
j
[[Summation is Linear]]
=
(
k
+
1
)
∑
i
=
1
n
i
k
+
∑
j
=
0
k
−
1
(
k
+
1
j
)
∑
i
=
1
n
i
j
[[Summation is Linear]]
{\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:
∑
i
=
1
n
(
(
i
+
1
)
k
+
1
−
i
k
+
1
)
=
∑
i
=
1
n
(
i
+
1
)
k
+
1
−
∑
i
=
1
n
i
k
+
1
[[Summation is Linear]]
=
∑
i
=
1
n
(
i
+
1
)
k
+
1
−
∑
i
=
1
n
i
k
+
1
+
1
k
+
1
−
1
k
+
1
=
1
k
+
1
+
∑
i
=
2
n
+
1
i
k
+
1
−
∑
i
=
1
n
i
k
+
1
−
1
k
+
1
=
∑
i
=
1
n
+
1
i
k
+
1
−
∑
i
=
1
n
i
k
+
1
−
1
k
+
1
=
(
n
+
1
)
k
+
1
+
∑
i
=
1
n
i
k
+
1
−
∑
i
=
1
n
i
k
+
1
−
1
k
+
1
recursive definition
=
(
n
+
1
)
k
+
1
−
1
{\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:
(
k
+
1
)
∑
i
=
1
n
i
k
+
∑
j
=
0
k
−
1
(
k
+
1
j
)
∑
i
=
1
n
i
j
=
(
n
+
1
)
k
+
1
−
1
⟹
(
k
+
1
)
∑
i
=
1
n
i
k
=
(
n
+
1
)
k
+
1
−
1
−
∑
j
=
0
k
−
1
(
k
+
1
j
)
∑
i
=
1
n
i
j
{\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:
s
u
m
_
o
f
_
p
o
w
e
r
s
(
k
,
n
)
=
∑
i
=
1
n
i
k
=
1
k
+
1
(
(
n
+
1
)
k
+
1
−
1
−
∑
j
=
0
k
−
1
(
k
+
1
j
)
∑
i
=
1
n
i
j
)
=
1
k
+
1
(
(
n
+
1
)
k
+
1
−
1
−
∑
j
=
0
k
−
1
(
k
+
1
j
)
s
u
m
_
o
f
_
p
o
w
e
r
s
(
j
,
n
)
)
{\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}}}
Template:Qed
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/454cec6e207b54a1b4c8cb636e709b2013182caf)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eff77d5436a83692be32cb006fe694a333751c5f)
