k 次方求和問題
解 k 次方求和問題。
最後更新:
呈現部分成果
連結是計算至 $\sum_{i = 1}^{n} i^{100}$ 的結果
介紹
任給一數 $k \in \mathbb{N}$，試將 $\sum_{i = 1}^{n} i^k$ 轉換成多項式結果，例如 $k = 2$ 時
$$ \begin{align*} \sum_{i = 1}^{n} i^2 = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n^1 \end{align*} $$關鍵步驟在於
$$ \begin{align*} n^k = \sum_{i = 1}^n i^k - \sum_{i = 1}^n (i - 1)^k \end{align*} $$範例
從 $k = 0$ 開始
$$ \sum_{i = 1}^{n} i^0 = \sum_{i = 1}^{n} 1 = n $$對 $k = 1$ 時
$$
\begin{align*}
n^2
& = \sum_{i = 1}^{n} i^2 - \sum_{i = 1}^{n} (i - 1)^2 \newline
& = \sum_{i = 1}^{n} \left[ i^2 - (i - 1)^2 \right] \newline
& = \sum_{i = 1}^{n} (2i - 1) \newline
& = 2 \sum_{i = 1}^{n} i - \sum_{i = 1}^{n} 1
\end{align*}
$$
將 $\sum_{i = 1}^{n} i$ 移項
$$
\begin{align*}
\sum_{i = 1}^{n} i
& = \frac{1}{2} \left( n^2 + \sum_{i = 1}^{n} 1 \right) \\
& = \frac{1}{2} n^2 + \frac{1}{2} n
\end{align*}
$$
同理，當 $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*}
$$
將 $\sum_{i = 1}^{n} i^2$ 移項
$$
\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*}
$$
運用相同方式，對任意 $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*}
$$
因此
$$
\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*}
$$
令 $\sum_{i = 1}^{n} i^k = S_k$，獲得以下公式
$$
\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*}
$$
另解
找到其他人的解法，過程真的很精妙！分享給大家
Python 實作
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 = ' ')