Solve sum of k-th powers problem
Solve sum of k-th powers problem.
There is the result of $\sum_{i = 1}^{n} i^{100}$
Introduction
Given $k \in \mathbb{N}$, convert
$$ \sum_{i = 1}^{n} i^k $$into a polynomial by the following fact
$$
n^k
= \sum_{i = 1}^n i^k
- \sum_{i = 1}^n (i - 1)^k.
$$
Example
Start with $k = 0$,
$$
\sum_{i = 1}^{n} i^0
= \sum_{i = 1}^{n} 1
= n.
$$
To find $k = 1$,
$$
\begin{align*}
n^2
& = \sum_{i = 1}^{n} i^2
- \sum_{i = 1}^{n} (i - 1)^2 \\
& = \sum_{i = 1}^{n} \left[ i^2 - (i - 1)^2 \right] \\
& = \sum_{i = 1}^{n} (2i - 1) \\
& = 2 \sum_{i = 1}^{n} i - \sum_{i = 1}^{n} 1.
\end{align*}
$$
Therefore
$$
\begin{align*}
\sum_{i = 1}^{n} 1
& = \frac{1}{2} \left( n^2 + \sum_{i = 1}^{n} 1 \right) \\
& = \frac{1}{2} n^2 + \frac{1}{2} n.
\end{align*}
$$
Then for $k = 2$,
$$
\begin{align*}
n^3
& = \sum_{i = 1}^{n} i^3
- \sum_{i = 1}^{n} (i - 1)^3 \\
& = \sum_{i = 1}^{n} \left[ i^3 - (i - 1)^3 \right] \\
& = \sum_{i = 1}^{n} (3i^2 - 3i + 1) \\
& = 3 \sum_{i = 1}^{n} i^2 - 3 \sum_{i = 1}^{n} i + \sum_{i = 1}^{n} 1.
\end{align*}
$$
Therefore
$$
\begin{align*}
\sum_{i = 1}^{n} i^2
& = \frac{1}{3} \left( n^3 + 3 \sum_{i = 1}^{n} i - \sum_{i = 1}^{n} 1 \right) \\
& = \frac{1}{3} \left( n^3 + 3 \left[ \frac{1}{2} n^2 + \frac{1}{2} n \right] - n \right) \\
& = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n.
\end{align*}
$$
We can use this method to find $\sum_{i = 1}^n i^k$ for any $k \in \mathbb N$.
$$
\begin{align*}
n^{k + 1}
& = \sum_{i = 1}^{n} i^{k + 1} - \sum_{i = 1}^{n} (i - 1)^{k + 1} \\
& = \sum_{i = 1}^{n} \left[ i^{k + 1} - (i - 1)^{k + 1} \right] \\
& = \sum_{i = 1}^{n} \left[ i^{k + 1} - \sum_{j = 0}^{k + 1} \binom{k + 1}{j} i^{j} (-1)^{k + 1 - j} \right] \\
& = \sum_{i = 1}^{n} \left[ i^{k + 1} - \left( i^{k + 1} - (k + 1) i^{k} + \sum_{j = 0}^{k - 1} \binom{k + 1}{j} i^{j} (-1)^{k + 1 - j} \right) \right] \\
& = \sum_{i = 1}^{n} \left[ (k + 1) i^{k} + \sum_{j = 0}^{k - 1} \binom{k + 1}{j} i^{j} (-1)^{k + 1 - j} \right] \\
& = (k + 1) \sum_{i = 1}^{n} i^k
+ \sum_{i = 1}^{n} \sum_{j = 0}^{k - 1} \binom{k + 1}{j} i^{j} (-1)^{k + 1 - j}
\end{align*}
$$
Therefore
$$
\begin{align*}
\sum_{i = 1}^{n} i^k
& = \frac{1}{k + 1} \left[ n^{k + 1} + \sum_{i = 1}^{n} \sum_{j = 0}^{k - 1} \binom{k + 1}{j} i^{j} (-1)^{k + 1 - j} \right] \\
& = \frac{1}{k + 1} \left[ n^{k + 1} + \sum_{j = 0}^{k - 1} \left[ \binom{k + 1}{j} (-1)^{k + 1 - j} \sum_{i = 1}^{n} i^j \right] \right]
\end{align*}
$$
Let $\sum_{i = 1}^{n} i^k = S_k$, we have
$$
\begin{align*}
S_k
= \frac{1}{k + 1} \left[ n^{k + 1} + \sum_{j = 1}^{k} \binom{k + 1}{j} (-1)^{k - j} S_j \right]
\end{align*}
$$
Algorithm
from fractions import Fraction
from math import comb
import numpy as np
k = int(input())
p = k + 1
A = np.zeros((p, p)) + Fraction()
for i in range(p):
for j in range(p):
if i >= j:
A[i][j] = Fraction(comb(i + 1, j)) if (i + j) % 2 == 0 else Fraction(-comb(i + 1, j))
else:
A[i][j] = Fraction(0)
B = np.zeros(p) + Fraction()
B[0] = 1 / A[k][k]
A[k] = A[k] / A[k][k]
for i in range(1, p):
B[i] = - A[k][k - i] / A[k - i][k - i]
A[k] = A[k] - (A[k][k - i] / A[k - i][k - i]) * A[k - i]
print(f"\\frac{{1}}{{{p}}} n^{{{p}}}", end = ' ')
for i in range(1, p):
if B[i].numerator != 0:
print("+" if B[i].numerator > 0 else "-", end = ' ')
if abs(B[i].numerator) == 1 and B[i].denominator == 1:
print(f"n^{{{p - i}}}", end = ' ')
elif B[i].denominator == 1:
print(f"{abs(B[i].numerator)} n^{{{p - i}}}", end = ' ')
else:
print(f"\\frac{{{abs(B[i].numerator)}}}{{{B[i].denominator}}} n^{{{p - i}}}", end = ' ')