거듭제곱의 합을 파헤치는 파울하버 공식의 비밀

수열의 합

우리는 고등학교에서 다양한 수열의 합을 구하게됩니다. 이때 $\sum$이란 기호를 처음 배우면서 가장 간단한 거듭제곱 수열들의 합을 유도하는 과정에 대해서 배우게 되죠.

 

$$\begin{align*}
\sum_{k=1}^n k &=\frac{n(n+1)}{2}\\
\sum_{k=1}^n k^2 &=\frac{n(n + 1)(2n + 1)}{6}\\
\sum_{k=1}^n k^3 &=\frac{n^2(n + 1)^2}{4}
\end{align*}$$

 

그런데 여러분들은 이 식들이 생각보다 매우 규칙적이라는 것을 알고 계셨나요? 오늘은 그 비밀을 함께 풀어보도록 하겠습니다.

1부터 $n$까지의 정수의 합

우선 가장 쉬운 $\sum_{k=1}^n k$부터 보도록 하겠습니다. 이 식은 흔히 $1$부터 $100$까지 더하여라 같은 등차수열의 합을 구하는데 사용되는 식입니다. 가우스가 어릴 적에 암산으로 풀었다는 사실로 더 유명한 문제죠.

이 식의 답을 구하는 과정은 어렵지 않습니다. 먼저 $1$부터 $n$까지의 수를 나열한 후 이 값들을 모두 더한 것을 $S$라 하겠습니다. 이제 같은 수열 하나를 더 만들어 방향만 바꾼 후 두 수열을 더해보겠습니다.

 

$$\begin{array}{ccccc}
S & + & S & = & 2S \\ 
\hline
1 & & n & & n+1 \\
2 & & n-1 & & n+1 \\
3 & & n-2 & & n+1 \\
\vdots & & \vdots & & \vdots \\
n-1 & & 2 & & n+1 \\
n & & 1 & & n+1 \\
\end{array}$$

 

이때 $2S$ 즉, 두 수열의 합을 보면 $n+1$이 $n$번 더해져 있이므로 $n\times(n+1)$입니다. 따라서 우리가 구해야하는 수열의 합 $S$는 두 수열을 더한 값을 $2$로 나눈 것과 같습니다.

 

$$S = \frac{n(n+1)}{2}$$

이 식을 이용하면 유용한 값들을 쉽게 찾을 수 있습니다. 예를들어 $k$가 홀수라면 $k=2m-1$을 대입하여 홀수들의 합은 제곱수를 만든다는 사실을 쉽게 증명할 수 있죠. 그리고 등차 수열은 $n$에 대한 $1$차 함수이므로 같은 방법으로 빠르게 해결할 수 있습니다.

 

$$\sum_{k=1}^n 2k-1 = 2\times \frac{n(n+1)}{2} - n=n^2$$

 

1부터 $n^2$까지의 정수의 합

$1$부터 $n^2$까지의 합을 구하는 문제는 앞서 본 문제와 같이 마냥 쉽지는 않습니다. 우리는 $k^2$이라는 항을 얻어내 $\sum_{k=1}^n k^2$의 값을 구하기 위해서 $(k-1)^3$의 전개식으로부터 시작해보겠습니다. $(k-1)^3$의 전개식은 다음과 같습니다.

 

$$
(k-1)^3 = k^3 - 3k^2 + 3k - 1
$$

 

우리가 필요한 것은 $k^2$이므로 $k^3$을 없애기 위해 식을 변형하면 다음과 같습니다.

 

$$
k^3 - (k-1)^3 = 3k^2 - 3k + 1
$$

 

이제 $\sum_{k=1}^n k^2$을 구하기 위해 양변에 각각 $\sum$을 취하겠습니다.

 

$$
\sum_{k=1}^n \left( k^3 - (k-1)^3 \right) = \sum_{k=1}^n \left(3k^2 - 3k + 1\right)
$$

 

먼저 좌변을 보겠습니다. 좌변의 일반항에 $1$부터 $n$까지 대입 한 후 각 항을 세로로 적고 모든 항을 더하면 같은 값에 부호만 다른 항들이 반복적으로 나오므로 소거할 수 있습니다. 따라서 좌변은 정리하면 $n^3$이 됩니다.

 

$$
\begin{align*}
& {1^3} &-&& 0^3& \\
&2^3 &-&& 1^3& \\
&3^3 &-&& 2^3&\\
&&\vdots&&& \\
+\quad&n^3 &-&& (n-1)^3& \\
\hline
&n^3&&&
\end{align*}
$$

 

다음으로 우변을 보겠습니다. 우변은 $\sum$에 선형성에 따라 분배해주면 식을 다음과 정리할 수 있습니다.

 

$$ \begin{align*}
&~\sum_{k=1}^n \left(3k^2 - 3k + 1\right) \\
=~ & 3  \sum_{k=1}^{n} k^2 - 3 \sum_{k=1}^{n} k + \sum_{k=1}^{n} 1 \\
=~ & 3  \sum_{k=1}^{n} k^2 - 3 \times \frac{n(n+1)}{2} + n \\
\end{align*}$$

 

마지막으로 정리된 결과를 원래식에 대입하여 $\sum_{k=1}^n k^2$으로 식을 정리해주면 $1$부터 $n^2$까지의 합을 구하는 공식을 구할 수 있습니다.

 

$$\begin{align*}
&&n^3 &= 3  \sum_{k=1}^{n} k^2 - 3 \frac{n(n+1)}{2} + n\\
\Rightarrow&& 3 \sum_{k=1}^{n} k^2 &= n^3 + 3 \times \frac{n(n+1)}{2} - n \\
\Rightarrow&& \sum_{k=1}^{n} k^2 &= \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n \\
\Rightarrow&& \sum_{k=1}^{n} k^2 & = \frac{n(n+1)(2n+1)}{6}
\end{align*}$$

 

그리고 같은 방법으로 어렵지 않게 $1$부터 $n^3$까지의 합을 구하는 공식도 구할 수 있습니다.

 

$$
\begin{align*}
&&(k-1)^4 &= k^4 - 4k^3 + 6k^2 - 4k + 1\\
\Rightarrow&&\sum_{k=1}^n \left( k^4 - (k-1)^4 \right) &= \sum_{k=1}^n \left( 4k^3 - 6k^2 + 4k - 1 \right) \\
\Rightarrow&&n^4 &= 4 \sum_{k=1}^{n} k^3 - 6 \sum_{k=1}^{n} k^2 + 4 \sum_{k=1}^{n} k - n \\
\Rightarrow&& 4 \sum_{k=1}^{n} k^3 &= n^4 + 6 \times \frac{n(n+1)(2n+1)}{6} - 4 \times \frac{n(n+1)}{2} + n \\
\Rightarrow&& \sum_{k=1}^{n} k^3 &= \frac{1}{4} n^4 + \frac{1}{2} n^3 + \frac{3}{4} n^2 + \frac{1}{4} n \\
\Rightarrow&& \sum_{k=1}^{n} k^3 &= \frac{n^2(n+1)^2}{4} = \left( \frac{n(n+1)}{2}\right)^2
\end{align*}
$$

 

여기까지는 고등학교 수업시간에 배우는 내용입니다. 그리고 학교에서 아마 이해를 돕기 위해 다양한 그림을 곁들이죠.

이 때의 결과는 내신이나 수능에 매번 출제되기도하고 나중에 정적분과 급수와의 관계에서 다시 등장하기에 보통은 외우고 있습니다.

 

$$
\int_{a}^{b} f(x) , dx = \lim_{{n \to \infty}} \sum_{{i=1}}^{n} f(x_i^*) \Delta x
$$

 

일반화된 패턴

이 공식을 보면 일정한 규칙이 보이시나요? 차수가 하나 증가한다는 것 이외에는 규칙이 있다고 상상하기는 어렵습니다. 시험에서도 세제곱이상의 식을 물어보는 문제는 잘 출제되지 않으므로 굳이 고민하고 싶지도 않습니다. 그럼에도 불구하고 규칙을 찾을 수 있을까요? 이 식을 자세히 관찰하면 공통적으로 갖고 있는 몇가지 특성을 더 찾아볼 수 있습니다.[^1]

 

$$
\begin{align}
\sum_{k=1}^n k &= \frac{1}{2}n^2 + \frac{1}{2}n\\
\sum_{k=1}^n k^2 &= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n\\
\sum_{k=1}^n k^3 &= \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2\\
\end{align}
$$

 

좌변을 보면 모두 $k$의 멱함수의 합 꼴 되어있습니다. 따라서 좌변을 모두 더한다면 멱급수(주어진 변수를 거듭제곱한 항들의 무한급수)를 떠올릴 수 있습니다. 테일러 전개는 기본적으로 무한급수를 이용한 근사치 계산법으로, 우리가 다루는 합의 형태를 명확히 드러낼 수 있는 도구입니다. 따라서 이를 활용한다면 문제를 해결하는 중요한 열쇠가 될 수 있습니다.

 

$$
\begin{align*}
\sum_{k=0}^{n-1} e^{kx} &= \sum_{k=0}^{n-1} \sum_{m=0}^{\infty} \frac{k^m x^m}{m!} = \sum_{m=0}^{\infty} \left(\sum_{k=1}^{n-1} k^m \right) \frac{x^m}{m!}  &\cdots(1)\\
\\
\sum_{k=0}^{n-1} e^{kx} &= \frac{e^{nx}-1}{e^x-1} \\
&= \frac{e^{nx} - 1}{x} \cdot \frac{x}{e^x - 1} \\
&= \frac{e^{nx} - 1}{x} \cdot \sum_{l=0}^{\infty} B_l \frac{x^l}{l!} \\
&= \left( \sum_{k=0}^{\infty} \frac{n^{m+1}}{m+1} \cdot \frac{x^m}{m!} \right) \left( \sum_{l=0}^{\infty} B_l \frac{x^l}{l!} \right) \\
&= \sum_{m=0}^{\infty} \left( \sum_{i=0}^{j} \frac{1}{m-i+1} \binom{m}{i} B_i n^{m+1-i} \right) \frac{x^m}{m!} &\cdots(2)
\end{align*}
$$

 

$e^x = \sum \frac{1}{n!}x^n$임을 이용해 $x=mx$를 대입한다면 $(1)$번 식처럼 앞서 본 형태의 멱함수의 합을 유도할 수 있습니다. 반대로, $e^x$를 공비로 갖는 등비수열의 합으로 본다면 $(2)$번 식처럼 정리할 수 있습니다. 이 때, $\frac{x}{e^x -1}$의 테일러 전개는 잘 모르므로 계수를 $B_l$이라 두고 정리하겠습니다.

 

$(1)$번 식과 $(2)$번 식은 같으므로 이로부터 거듭제곱의 합을 다음과 같이 나타낼 수 있습니다. 이후 조합을 이용하면 앞선 계수가 깔끔하게 정리됩니다.

 

$$\begin{align*}
\sum_{k=1}^{n-1} k^m &= \sum_{i=0}^{m} \frac{1}{m-i+1} \binom{m}{i} B_i n^{m+1-i} \\
&= \sum_{i=0}^{m} \frac{m!}{(m-i+1) i! (m-i)!} B_i n^{m+1-i} \\
&= \frac{1}{m+1} \sum_{i=0}^{m} \binom{m+1}{i} B_i n^{m+1-i}
\end{align*}$$

 

마지막으로 양변에 $n^m$을 더하면, 거듭제곱의 합은 $B_i$라는 값을 이용해 변형할 수 있습니다. 여기서 갑자기 부호가 나와 이상하시겠지만 그것은 잠시만 나중에 다뤄보겠습니다.

 

$$\sum_{k=1}^{n} k^m = \frac{1}{m+1} \sum_{i=0}^{m} (-1)^i\binom{m+1}{i} B_i n^{m+1-i}$$

 

그렇다면 $B_i$가 무엇이길래 거듭제곱의 합을 구하는데 사용될 수 있을까요?

베르누이 수(Bernoulli numbers)

$B_i$는 앞서 보았듯이 $\frac{x}{e^x - 1}$를 이용해 정의됩니다.

$$
\frac{x}{e^x - 1} = \sum_{k=0}^{\infty} B_i \frac{x^i}{i!}
$$

테일러 정리를 이용해 $B_i$를 찾아보면, 다음과 같이 $B_i$를 찾아낼 수 있습니다.[^2]

 

$$\begin{align*}
\frac{x}{e^x - 1} &= 1 - \frac{x}{2} + \frac{x^2}{12} - \frac{x^4}{720} + \frac{x^6}{30240} - \cdots\\
&=1\cdot \frac{1}{0!}-\frac{1}{2}\cdot \frac{x}{1!} + \frac{1}{6} \cdot \frac{x^2}{2!}-\frac{1}{30}\cdot \frac{x^4}{4!} + \frac{1}{42} \cdot \frac{x^6}{6!} - \cdots\\
\end{align*}$$

 

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
B_n & 1 & -\frac{1}{2} & \frac{1}{6} & 0 & -\frac{1}{30} & 0 & \frac{1}{42} & 0 & -\frac{1}{30} & 0 & \frac{5}{66} & 0 & -\frac{691}{2730} \\
\end{array}$$

 

얼핏 보면 이 숫자들이 너무 불규칙적이라 별로 중요하지 않다고 생각하실 수도 있습니다. 그런데 사실 이 숫자들은 우리가 생각보다 자주 등장합니다.[^3]

 

$\coth(x)$는 지수함수를 이용해 정의할 수 있으므로,

$$\coth(x) = \frac{\cosh(x)}{\sinh(x)} = \frac{e^x + e^{-x}}{e^x - e^{-x}}$$

 

앞서 보았던 베르누이 함수의 짝수 부분만 고려한 함수로 나타낼 수 있습니다.

$$\sum_{n=0}^{\infty} \frac{B_{2n} x^{2n}}{(2n)!} = \frac{x}{2} \coth \left( \frac{x}{2} \right)$$

 

복소수에서의 오일러 공식을 이용하면 $\cot(x)=i\coth(ix)$와 같으므로,

 

$$
\coth(ix) = \frac{\cos(ix)}{i\sin(x)} = \frac{1}{i} \cdot \frac{\cos(ix)}{\sin(x)} = \frac{\cos(x)}{\sin(x)} \cdot \frac{1}{i} = \frac{1}{i} \cot(x)
$$

 

앞선 식을 이용해 $\cot(x)$에 대한 생성함수를 얻을 수 있습니다.

$$\sum_{n=0}^{\infty} \frac{(-1)^n B_{2n} x^{2n}}{(2n)!} = \frac{x}{2} \cot \left( \frac{x}{2} \right)$$

 

마지막으로 $\tan(x) = \cot(x) - 2 \cot(2x)$이므로, 앞선 식을 정리하면, 베르누이 수를 이용해 $\tan$의 테일러 전개도 구할 수 있습니다. 불규칙해 보였던 $\tan(x)$의 테일러 전개의 계수들이 거듭제곱의 합과 연결이 되는거죠.

 

$$\begin{align*}
\tan(x) &= \sum_{n=0}^{\infty} \frac{(-1)^n B_{2n} 2^{2n} \left( x^{2n-1} - 2 \cdot 2^{2n-1} x^{2n-1} \right)}{(2n)!}\\
&= \sum_{n=1}^{\infty} \frac{(-1)^{n-1} B_{2n} \left(2^{2n} - 1\right) 2^{2n-1} x^{2n-1}}{(2n)!}\\
&= \sum_{n=1}^{\infty} \frac{B_{2n} (-4)^{n} \left(1-4^n \right) x^{2n-1}}{(2n)!}\\
&= x+\frac{x^3}{3}+\frac{2x^5}{15}+\frac{17x^7}{315}+\frac{62x^9}{2835} + \cdots
\end{align*}$$

 

그런데 여기서 끝이 아닙니다. 베르누이 수를 이용해 다음과 같은 베르누이 다항식을 정의해보겠습니다.

 

$$
B_n(x) = \sum_{k=0}^{n} \binom{n}{k} B_{n-k} x^{k}
$$

 

몇 가지 베르누이 다항식을 예로 보면,

$$\begin{align*}
B_0(x) &= 1\\
B_1(x) &= x - \frac{1}{2}\\
B_2(x) &= x^2 - x + \frac{1}{6}\\
B_3(x) &= x^3 - \frac{3}{2}x^2 + \frac{1}{2}x\\
B_4(x) &= x^4 - 2x^3 + x^2 - \frac{1}{30}\\
\vdots
\end{align*}$$

 

베르누이 수 $B_n$는 베르누이 다항식의 $x = 0$에서 값 $B_n = B_n(0)$입니다. 이제 $n$이 커감에 따라 함수를 그려보도록 하겠습니다. 베르누이 다항식은 처음에는 규칙이 없어보일 수 있지만 $n$이 커질수록 변동폭이 증가합니다. 특히, 홀수 $n$에서는 사인 함수와, 짝수 $n$에서는 코사인 함수와 유사한 패턴을 나타내며 수렴하는 경향이 있습니다. 이는 결국 주기적인 삼각 함수의 성질과 맞물리게 됩니다.

주기가 1인 $\tilde{B}_n(x)$를 아래와 같이 정의하면,

 

$$\tilde{B}_n(x) = B_n(x), \quad 0 \leq x < 1, \quad \tilde{B}_n(x+1) = \tilde{B}_n(x), \quad x \in \mathbb{R}$$

 

주기적 베르누이 함수 $\tilde{B}_n(x)$는 $n \geq 2$일 때, $n-1$차 미분까지 연속이며, 푸리에 급수는 다음과 같습니다.

 

$$\begin{align*}
\tilde{B}_{2n}(x) &= (-1)^{n+1}\frac{2(2n)!}{(2\pi)^{2n}} \sum_{m=1}^{\infty} \frac{\cos(2m\pi x)}{m^{2n}}\\
\tilde{B}_{2n+1}(x) &= (-1)^{n+1}\frac{2(2n+1)!}{(2\pi)^{2n+1}} \sum_{m=1}^{\infty} \frac{\sin(2m\pi x)}{m^{2n+1}}
\end{align*}$$

 

앞서 본 결과와 잘 맞아 떨어지죠. 이 식으로 알 수 있는 정보가 더 있을까요? 마지막으로 이 식의 양변에 $0$을 대입해보면 어떻게 될까요? 양변에 $0$을 대입하면 $\cos 0=1$이므로, 우변이 간단하게 정리됩니다. 이 때, $\sum_{m=1}^{\infty} \frac{1}{m^{2n}}$은 너무나 유명한 식이 됩니다.

 

$$\tilde{B}_{2n}(0) = (-1)^{n+1} \frac{2(2n)!}{(2\pi)^{2n}} \sum_{m=1}^{\infty} \frac{1}{m^{2n}}$$

 

바로 리만 제타 함수죠.

 

$$\zeta(s) = \sum_{m=1}^{\infty} \frac{1}{m^s}$$

 

따라서 리만 제타 함수에 짝수를 대입한 값은 베르누이 수를 이용해 찾을 수 있습니다. 이렇게 보면 리만 제타함수가 짝수를 정의역으로 가질 때, 함숫값에 $\pi$가 들어가는 이유를 색다르게 해석할 수 있습니다.[^4]

 

$$
\begin{align*}
 &\tilde{B}_{2n}(0) = (-1)^{n+1} \frac{2(2n)!}{(2\pi)^{2n}} \zeta(2n)\\
\Rightarrow \quad &
\zeta(2n) = \frac{(-1)^{n+1} B_{2n} (2\pi)^{2n}}{2(2n)!}
\end{align*}
$$

파울 하버의 공식

이야기가 멀리 가버렸지만, 다시 원래 문제인 거듭제곱의 합으로 돌아와보겠습니다. 앞서 유도했던 이 식은 파울하버 공식(Faulhaber’s formula)이라 불립니다. 이제는 $B_i$의 값들이 익숙하므로 손쉽게 거듭제곱의 합을 구할 수 있을 것 처럼 보입니다.

 

$$\sum_{k=1}^{n} k^m = \frac{1}{m+1} \sum_{i=0}^{m} (-1)^i\binom{m+1}{i} B_i n^{m+1-i}$$

 

이 식을 이용해 거듭제곱의 합을 구하기에 앞서, 건너 뛰었던 증명을 조금 자세히 들여다 보겠습니다.

$$\begin{align}
\sum_{k=1}^{n-1} k^m &= \sum_{i=0}^{m} \frac{1}{m-i+1} \binom{m}{i} B_i n^{m+1-i} \\
&= \sum_{i=0}^{m} \frac{m!}{(m-i+1) i! (m-i)!} B_i n^{m+1-i} \\
&= \frac{1}{m+1} \sum_{i=0}^{m} \binom{m+1}{i} B_i n^{m+1-i}
\end{align}$$

 

$\sum_{k=1}^{n} k^m$을 구하기 위해 $\sum_{k=1}^{n-1} k^m$에 $n^m$을 더해보겠습니다. $\frac{1}{m+1}$로 식을 묶어 표현하면 다음과 같이 정리됩니다.

$$\begin{align}
& \sum_{k=1}^{n} k^m = \sum_{k=1}^{n-1} k^m + n^m \\
\Rightarrow ~& \sum_{k=1}^{n} k^m = \frac{1}{m+1} \sum_{i=0}^{m} \binom{m+1}{i} B_i n^{m+1-i} + n^m\\
\Rightarrow ~& \sum_{k=1}^{n} k^m = \frac{1}{m+1} \left( \sum_{i=0}^{m} \binom{m+1}{i} B_i n^{m+1-i} + (m+1) n^m \right)\\
\end{align}$$

 

이때, $i=1$인 항에 주목해보겠습니다. $B_1 = -\frac{1}{2}$이고, $\binom{m+1}{1} = m+1$이므로,

 

$$\begin{align}
&\binom{m+1}{1} B_1 n^{m+1-1} +(m+1) n^{m}\\
= ~ &(m+1) \left( -\frac{1}{2} \right) n^{m} +(m+1) n^{m}\\
= ~&-\frac{(m+1)}{2} n^{m} + (m+1) n^{m} \\
= ~&\frac{(m+1)}{2} n^{m} \\
= ~& (-1)^1 \binom{m+1}{1} B_1 n^{m+1-1}
\end{align}
$$

 

식은 다음과 같이 다시 쓸 수 있습니다.

 

$$
\sum_{k=1}^{n} k^m = \frac{1}{m+1} \left( \binom{m+1}{0} B_0 n^{m+1} + (-1)^1 \binom{m+1}{1} B_1 n^{m+1-1} + \sum_{i=2}^{m} \binom{m+1}{i} B_i n^{m+1 - i} \right)
$$

 

베르누이 수 $B_i$는 $i \ge3$인 홀수 일 때 $B_i = 0$이므로 $(-1)^\text{(홀수)}=-1$이지만 영향을 미치지 않고,

 

$$\begin{array}{c|c}
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots\\
\hline
B_n & 1 & -\frac{1}{2} & \frac{1}{6} & 0 & -\frac{1}{30} & 0 & \frac{1}{42} & 0 & -\frac{1}{30} & 0 & \frac{5}{66} & 0 & -\frac{691}{2730} \\
\end{array}
\end{array}$$

 

짝수 일 때는 $(-1)^\text{(짝수)}=1$이므로 같은 식입니다. 따라서, 다음과 같이 식을 정리할 수 있지요.

 

$$\sum_{k=1}^{n} k^m = \frac{1}{m+1} \sum_{i=0}^{m} (-1)^i\binom{m+1}{i} B_i n^{m+1-i}$$

 

파울하버의 공식을 이용하면 $\sum_{k=1}^{n} k^m$에 대하여, $\sum_{k=1}^{10^{6}} k^{10}$와 같은 복잡한 거듭제곱의 합도 컴퓨터를 사용해 빠르게 계산할 수 있습니다.

 

이 식을 직접 합산 한다면, 모든 $k$의 값을 개별적으로 제곱하고 더해야 하므로, $n$개의 항에 대해 반복을 수행하기 때문에 $n$이 커질 수록 선형적으로 연산이 증가합니다.($\mathcal{O}(n m \log n)$) 반면에 파울하버 공식은 거듭제곱 합을 계산할 때 개별 항을 모두 계산하지 않고, 베르누이 수와 이항 계수 등을 사용해 적은 계산만으로도 결과를 구할 수 있습니다. 파울하버 공식에서 다항식의 차수는 $m+1$이므로($\mathcal{O}(m^2 \log n)$), $m$이 작을 경우 직접 합산에 비해 속도는 수천 배에서 수백만 배까지 더 빠르며, 큰 $n$에서도 거의 일정한 시간 내에 결과를 얻을 수 있습니다.

import time
from mpmath import bernoulli, binomial, mp

# mpmath로 정밀도를 높여 연산하기
mp.dps = 100  # 소수점 이하 100자리까지 계산

# 직접 합산 방식
def direct_sum(n, m):
    return sum(k**m for k in range(1, n + 1))

# 파울하버 공식 방식 (mpmath 사용, 결과를 정수형으로 변환)
def faulhaber_sum(n, m):
    result = mp.mpf(0)
    for i in range(m + 1):
        result += (-1) ** i * binomial(m + 1, i) * bernoulli(i) * n ** (m + 1 - i)

    # 최종 결과를 정수형으로 변환
    return int(result / (m + 1))


# 예시
n = 10**6
m = 10


# 직접 합산 방식 시간 측정

start_time = time.time()
direct_result = direct_sum(n, m)
direct_time = time.time() - start_time

# 파울하버 공식 방식 시간 측정
start_time = time.time()
faulhaber_result = faulhaber_sum(n, m)
faulhaber_time = time.time() - start_time

# 결과 출력
print(f"직접합산 공식 결과: {direct_result}, 시간: {direct_time:.6f}초")
print(f"파울하버 공식 결과: {faulhaber_result}, 시간: {faulhaber_time:.6f}초")

파울하버 공식은 단순히 수학적 계산의 효율성을 높여줄 뿐만 아니라, 복잡한 문제를 단순화하여 접근하는 데 큰 도움을 줄 수도 있습니다.[^5]

 

[!note] 오일러-매클로린 공식 (Euler–Maclaurin formula)
오일러-마클로린 공식은 적분과 급수의 근사 관계를 통해 복잡한 급수를 간단하게 계산하는 데 사용됩니다.
$$\sum_{k=a}^n f(k) - \int_a^n f(x) , dx = \frac{f(n) + f(a)}{2} + \sum_{k=1}^{\infty} B_{2k} \frac{f^{(2k-1)}(n) - f^{(2k-1)}(a)}{(2k)!}$$

복잡해 보이는 수식 뒤에 숨겨진 패턴과 논리를 발견하는 과정은 단순한 계산을 넘어 수학의 본질을 이해하고 응용하는 것과 연결됩니다. 앞서 본 제타함수의 공식은 양자장론에서 무한대가 발생하는 진동수의 합을 처리할 때 제타 함수 규칙화(zeta function regularization)기법에 응용될 수 있습니다.

$$\zeta(2n) = (-1)^{n+1} \frac{B_{2n} (2\pi)^{2n}}{2 (2n)!}$$

 

우리가 배운 단순한 급수의 합이 리만 제타 함수나 양자 물리학에서 중요한 역할을 한다는 것은 수학이 한정된 지식이 아니라 끊임없이 연결되는 학문이라는 점을 보여줍니다. 수학을 배우는 것이 단순히 계산을 하고 문제를 푸는 것이 아니라, 새로운 영역을 탐구하는 첫걸음이라는 사실을 기억해보면 어떨까요?

 

 

[^1]: proof of Faulhaber’s formula (planetmath.org)
[^2]: Bernoulli Number
[^3]: Bernoulli numbers, taylor series expansion of tan x
[^4]: Bernoulli Polynomials, Fourier Series and Zeta Numbers Scheufens, Ernst E
[^5]: Maclaurin's Second Formula and its Generalization