User:Ans/Sum of Sequence of Nth Powers

Theorem

\forall k \in ℕ_{0} \forall n \in ℕ_{0} : s u m_o f_p o w e r s (k, n) = \sum_{i = 1}^{n} i^{k} = \frac{1}{k + 1} ({(n + 1)}^{k + 1} - 1 - \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) s u m_o f_p o w e r s (j, n))

Proof by Sum of Differences of One Higher Order Powers

$\begin{matrix} \sum_{i = 1}^{n} ({(i + 1)}^{k + 1} - i^{k + 1}) & = \sum_{i = 1}^{n} (\sum_{j = 0}^{k + 1} (\binom{k + 1}{j}) i^{j} - i^{k + 1}) & [[Binomial Theorem]] \\ = \sum_{i = 1}^{n} ((\binom{k + 1}{k + 1}) i^{k + 1} + (\binom{k + 1}{k}) i^{k} + \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) i^{j} - i^{k + 1}) & recursive definition \\ = \sum_{i = 1}^{n} ((k + 1) i^{k} + \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) i^{j}) \\ = (k + 1) \sum_{i = 1}^{n} i^{k} + \sum_{i = 1}^{n} \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) i^{j} & [[Summation is Linear]] \\ = (k + 1) \sum_{i = 1}^{n} i^{k} + \sum_{j = 0}^{k - 1} \sum_{i = 1}^{n} (\binom{k + 1}{j}) i^{j} & [[Summation is Linear]] \\ = (k + 1) \sum_{i = 1}^{n} i^{k} + \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) \sum_{i = 1}^{n} i^{j} & [[Summation is Linear]] \end{matrix}$

On the other hand:

$\begin{matrix} \sum_{i = 1}^{n} ({(i + 1)}^{k + 1} - i^{k + 1}) & = \sum_{i = 1}^{n} {(i + 1)}^{k + 1} - \sum_{i = 1}^{n} i^{k + 1} & [[Summation is Linear]] \\ = \sum_{i = 1}^{n} {(i + 1)}^{k + 1} - \sum_{i = 1}^{n} i^{k + 1} + 1^{k + 1} - 1^{k + 1} \\ = 1^{k + 1} + \sum_{i = 2}^{n + 1} i^{k + 1} - \sum_{i = 1}^{n} i^{k + 1} - 1^{k + 1} \\ = \sum_{i = 1}^{n + 1} i^{k + 1} - \sum_{i = 1}^{n} i^{k + 1} - 1^{k + 1} \\ = {(n + 1)}^{k + 1} + \sum_{i = 1}^{n} i^{k + 1} - \sum_{i = 1}^{n} i^{k + 1} - 1^{k + 1} & recursive definition \\ = {(n + 1)}^{k + 1} - 1 \end{matrix}$

Therefore:

$\begin{matrix} (k + 1) \sum_{i = 1}^{n} i^{k} + \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) \sum_{i = 1}^{n} i^{j} & = {(n + 1)}^{k + 1} - 1 \\ ⟹ & (k + 1) \sum_{i = 1}^{n} i^{k} & = {(n + 1)}^{k + 1} - 1 - \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) \sum_{i = 1}^{n} i^{j} \end{matrix}$

Therefore:

$\begin{matrix} s u m_o f_p o w e r s (k, n) = \sum_{i = 1}^{n} i^{k} & = \frac{1}{k + 1} ({(n + 1)}^{k + 1} - 1 - \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) \sum_{i = 1}^{n} i^{j}) \\ = \frac{1}{k + 1} ({(n + 1)}^{k + 1} - 1 - \sum_{j = 0}^{k - 1} (\binom{k + 1}{j}) s u m_o f_p o w e r s (j, n)) \end{matrix}$

Template:Qed

This work is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license. In short: you are free to share and to make derivatives of this work under the conditions that you appropriately attribute it, and that you only distribute it under the same, similar or a compatible license. Any of the above conditions can be waived if you get permission from the copyright holder.