자연수 거듭제곱의 합 일반화 (조합론적 증명)

서론에 앞서, 결론부터 적자면

$$\sum\limits_{i=1}^n i^k = \sum_{i = 1}^{k}{}_{n+1} \mathrm{C} _{i+1} ~S(k,i) ~ i!$$

을 증명할 것이다.

서론

$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$가우스가 어릴적 했다고 전해지는 자연수 $1$부터 $n$까지의 합을 쉽게 구하는 법을 처음 보고 정말 대단하다고 생각했다. 이후에 공부를 좀 더 하면서 이 자연수의 합 공식이 조합(combination)과 굉장히 유사하게 생겼다고 느꼈다.

 

마치 ${}_{n+1}\mathrm{C}_{2}$로 표현하면 더욱 깔끔할 것 같아 이리저리 자료를 찾다가 마침 자연수 거듭제곱의 합을 조합론적으로 증명한 글을 보게 되었다. 역시! 조합과 관련이 있었다.

 

이번 글에서는 그 증명을 다듬고 일반화 한 내용을 소개하겠다.

 

그냥 자연수의 합 - $\sum\limits_{i=1}^n i$

다음을 조합론적으로 증명할 것이다.

$$1 + 2 + \cdots + n = {}_{n+1} \mathrm{C} _{2}$$

 

$1$부터 $n+1$까지 $n+1$개의 자연수에서 서로 다른 두 개의 자연수를 뽑는 경우를 생각하자. 편의상 두 수 중 큰 수를 $a$, 작은 수를 $b$라고 하자.

 

~(좌변)~

그러면 $a$는 $2$부터 $n+1$까지의 자연수가 될 수 있고, $a$가 자연수 $i (\le n+1)$라면 가능한 $b$의 수는 $i-1$개가 될 것이다.

($b$는 $1$, $2$, $\cdots$, $i-1$이 될 수 있으므로!)

 

즉, $a$가 $2$일때는 $b$를 고르는 수가 $1$개, $a$가 $3$일때는 $b$를 고르는 수가 $2$개, $\cdots$, $a$가 $n+1$일때는 $b$를 고르는 수가 $n$개가 되어 모두 $1 + 2 + \cdots + n$ 가지가 된다.

 

~(우변)~

여기서 $n+1$개의 자연수 중 서로 다른 두 수를 뽑는 경우의 수는 ${}_{n+1} \mathrm{C} _{2}$이다.

 

따라서 $$1 + 2 + \cdots + n = {}_{n+1} \mathrm{C} _{2}$$ 이 성립한다.

■

자연수 제곱의 합 - $\sum\limits_{i=1}^n i^2$

이제는 제곱의 합을 생각해보자. 다음을 증명하려고 한다.

$$1^2 + 2^2 + \cdots + n^2 = {}_{n+1} \mathrm{C} _{2} + 2! \times {}_{n+1} \mathrm{C} _{3}$$

$1$부터 $n+1$까지 $n+1$개의 자연수에서 세 개의 자연수를 뽑는 경우를 생각하자. 단, 뽑는 수 중에 가장 큰 수는 다른 두 수와 항상 다르다고 가정하자.

가장 큰 수를 $m$이라 하고, 나머지 두 수를 $m_1$, $m_2$라 하자.

 

~(좌변)~

$m = i$일 때 (단, $2 \le i \le n+1$) $m_1$과 $m_2$를 중복하여 선택하는 경우의 수는 $(i-1)^2$이다.

 

즉, 전체 경우의 수는 이를 모두 더한 $1^2 + 2^2 + \cdots + n^2$이다. 그런데, 이것은 다음과 같이 생각해볼 수도 있다.

 

~(우변)~

$n+1$개의 자연수에서 가장 큰 수를 포함하여(가장 큰 수는 항상 다르다고 가정함!) 두 종류의 수를 뽑아 배열하는 경우와 세 종류의 수를 뽑아 배열하는 경우로 나누어 생각할 수 있다.

1) 두 종류

두 종류의 수를 뽑는 경우의 수는 ${}_{n+1} \mathrm{C} _{2}$

이렇게 뽑으면 $m$에는 가장 큰 수가, $m_1$, $m_2$에는 나머지 한 종류의 수가 자동적으로 배열된다.

 

따라서 구하려는 경우의 수는 ${}_{n+1} \mathrm{C} _{2}$

2) 세 종류

세 종류의 수를 뽑는 경우의 수는 ${}_{n+1} \mathrm{C} _{3}$

뽑은 수 중 가장 큰 수를 $m$이라 하면, 뽑은 나머지 두 종류의 수를 $m_1$과 $m_2$에 배열하면 된다. 이는 $2!$ 가지이다.

 

따라서 구하려는 경우의 수는 $2! \times {}_{n+1} \mathrm{C} _{3}$

 

즉, 총 경우의 수는 다음과 같다.

$${}_{n+1} \mathrm{C} _{2} + 2! \times {}_{n+1} \mathrm{C} _{3}$$

그리고 이를 전개하면 $1^2 + 2^2 + \cdots + n^2$과 같음을 알 수 있다.

■

자연수 세제곱의 합 - $\sum\limits_{i=1}^n i^3$

세제곱의 합도 앞서 했던 것과 비슷하게 진행하면 된다. 먼저 보일 등식은 다음과 같다.

$$1^3 + 2^3 + \cdots + n^3 = {}_{n+1} \mathrm{C} _{2} + 3 \times 2! \times {}_{n+1} \mathrm{C} _{3} + 3! \times {}_{n+1} \mathrm{C} _{4}$$

식이 좀 더 복잡해졌지만, 마찬가지로 $1$부터 $n+1$까지 $n+1$개의 자연수에서 네 개의 자연수를 뽑는 경우를 생각하자. 당연히 여기서도 가장 큰 수는 다른 세 수와 항상 다르다.

가장 큰 수를 $m$이라 하고, 나머지 세 수를 $m_1$, $m_2$, $m_3$라 하자.

 

~(좌변)~

$m = i$일 때 (단, $2 \le i \le n+1$) $m_1$, $m_2$, $m_3$를 중복하여 선택하는 경우의 수는 $(i-1)^3$이다.

 

즉, 전체 경우의 수는 이를 모두 더한 $1^3 + 2^3 + \cdots + n^3$이다.

 

~(우변)~

$n+1$개의 자연수에서 가장 큰 수를 포함하여(가장 큰 수는 항상 다르다고 가정함!) 두 종류의 수를 뽑아 배열하는 경우, 세 종류의 수를 뽑아 배열하는 경우, 네 종류의 수를 뽑아 배열하는 경우로 나누어 생각할 수 있다.

1) 두 종류

두 종류의 수를 뽑는 경우의 수는 ${}_{n+1} \mathrm{C} _{2}$

이렇게 뽑으면 $m$에는 가장 큰 수가, $m_1$, $m_2$, $m_3$에는 나머지 한 종류의 수가 자동적으로 배열된다.

 

따라서 구하려는 경우의 수는 ${}_{n+1} \mathrm{C} _{2}$

2) 세 종류

세 종류의 수를 뽑는 경우의 수는 ${}_{n+1} \mathrm{C} _{3}$

뽑은 수 중 가장 큰 수를 $m$이라 하면, 뽑은 나머지 두 종류의 수들을 $m_1$, $m_2$, $m_3$에 배열하면 된다. 단, 두 종류 모두 사용하여 배열해야 한다.

조금 까다롭지만, 약간만 생각해보면 다음 상황과 같다는 것을 알 수 있다.

 

뽑은 두 종류의 수를 $a_1$과 $a_2$라 한다면, $m_1$, $m_2$, $m_3$은 각각 $a_1$과 $a_2$ 둘 중 하나를 선택할 수 있고, 전체적으로는 $a_1$, $a_2$ 모두 대응되어야 한다.

(모두 같은 종류를 선택하면 안된다! 그것은 한 종류를 선택하는 것과 다르지 않기 때문)

즉, 다음과 같은 대응 $f$에 대하여

$$ f : \{ m_1, m_2, m_3 \} \to \{ a_1, a_2 \}$$

$f$ 가 전사함수임과 동치이다.

 

원소 개수가 $x$개인 집합에서 $y$개인 집합으로의 전사함수의 개수는 다음과 같으므로

$$S(x,y) \times y!$$

따라서 이 경우에는 $S(3,2) \times 2! = 3 \times 2!$ 가지이다.

 

즉, 세 종류를 뽑았을 때는 $3 \times 2! \times {}_{n+1} \mathrm{C} _{3}$

3) 네 종류

마찬가지로 네 종류의 수를 뽑는 수는 ${}_{n+1} \mathrm{C} _{4}$

가장 큰 수를 $m$이라 하고, 나머지 세 종류의 수들을 $m_1$, $m_2$, $m_3$에 배열하면 되므로 $3!$

 

따라서 네 종류를 뽑았을 때는 $3! \times {}_{n+1} \mathrm{C} _{4}$

 

즉, 총 경우의 수는 다음과 같다.

$${}_{n+1} \mathrm{C} _{2} + 3 \times 2! \times {}_{n+1} \mathrm{C} _{3} + 3! \times {}_{n+1} \mathrm{C} _{4}$$

그리고 이를 전개하면 $1^3 + 2^3 + \cdots + n^3$과 같음을 알 수 있다.

■

일반화 - $\sum\limits_{i=1}^n i^k$

자, 그럼 준비운동은 모두 마쳤다. (사실 거의 다 했다...) 일반적인 상황을 위해 자연수 $k$에 대한 $k$-거듭제곱의 합을 구해보자.

앞과 마찬가지로 $1$부터 $n+1$까지 $n+1$개의 자연수에서 $k+1$ 개의 자연수를 뽑는 경우를 생각하자. 당연히 여기서도 가장 큰 수는 다른 $k$개의 수와 항상 다르다.

가장 큰 수를 $m$이라 하고, 나머지 세 수를 $m_1$, $m_2$, $\cdots$, $m_k$라 하자.

 

~(좌변이 될 것)~

$m = i$일 때 (단, $2 \le i \le n+1$) $m_1$, $m_2$, $\cdots$, $m_k$를 중복하여 선택하는 경우의 수는 $(i-1)^k$이다.

 

즉, 전체 경우의 수는 이를 모두 더한 $1^k + 2^k + \cdots + n^k$이다.

 

~(우변이 될 것)~

$n+1$개의 자연수에서 가장 큰 수를 포함하여(가장 큰 수는 항상 다르다고 가정함!) $i$ 종류 (단, $2 \le i \le k + 1$)의 수를 뽑아 배열하는 경우를 생각하자.

 

먼저, $i$ 종류의 수를 뽑는 경우의 수는 ${}_{n+1} \mathrm{C} _{i}$

 

$m$에 가장 큰 수를 할당하고, 나머지 $i-1$ 종류의 수들을 $m_1$, $m_2$, $\cdots$, $m_k$에 빠짐없이 배열하면 되므로 다음 상황과 같다. 

뽑은 $i-1$ 종류의 수를 $a_1$, $a_2$, $\cdots$, $a_{i-1}$ 라고 하면 대응 $f$ 에 대해

$$ f : \{ m_1, m_2, \cdots,  m_k \} \to \{ a_1, a_2, \cdots,  a_{i-1}\}$$

$f$ 가 전사함수임과 동치이다.

 

즉, 그러한 경우의 수는 $S(k,i-1) \times (i-1)!$

 

따라서 $i$ 종류를 뽑는 경우의 수는 $S(k,i-1) \times (i-1)! \times {}_{n+1} \mathrm{C} _{i}$

 

그러므로, 전체 경우의 수는 다음과 같다.

$$\sum_{i = 2}^{k+1} {}_{n+1} \mathrm{C} _{i} ~ S(k,i-1) ~ (i-1)!  $$

좀 더 깔끔하게 정리해보면 다음과 같다.

$$\sum_{i = 1}^{k}{}_{n+1} \mathrm{C} _{i+1} ~S(k,i) ~ i!  $$

 

결론적으로 다음이 성립한다.

$$\sum\limits_{i=1}^n i^k = \sum_{i = 1}^{k}{}_{n+1} \mathrm{C} _{i+1} ~S(k,i) ~ i!$$

■

결론

역사적으로도 자연수의 거듭제곱의 합을 일반화하려는 시도가 있었다. 그 과정에서 베르누이 수도 탄생하게 되었고, 여러 부수적인 발전을 이끌어내었다. (사실 이를 통해 베르누이 수와 집합의 분할 수(제 2종 스털링 수)와의 관계도 알아낼 수 있을 법 한데... 뭐, 그것은 나중으로 미루겠다.) 

 

이번에 도출한 새로운 식이 실질적으로 더욱 효과적인 계산을 위해 쓰일 수 있을 것이라고는 생각하지 않는다. 한 눈에 봐도 팩토리얼 계산이나 제 2종 스털링 수 계산이 거듭제곱보다 더 복잡도가 높아보이며 메모이제이션 등을 사용하지 않으면 recursion 계산할 때 stack overflow가 나버릴 것이 분명하기 때문에...

 

하지만! 일반화 된 공식의 심미성은 수많은 오버헤드들을 잠시나마 잊게 해준다. 이것이 일반화의 묘미 아닐까.

아름답고 깔끔하다! ☺️

위 그림같이 기존의 해석적인 방법으로 공식을 도출할 때에는 그 규칙을 찾아내기가 무척 힘들었지만, 조합론적 방법을 사용하면 규칙이 보인다는 것이 흥미로웠다. 조합론적 증명은 정말 강력한 방법이라는 것을 다시금 깨달을 수 있었다. 

 

마치며, 이 증명의 모티브가 된 글의 작성자에게 감사의 인사를 전한다.

Reference

https://blog.naver.com/eunmikorea/221317844150