$1$부터 $N$까지의 합에 $1$부터 $N$까지의 합 붙이기... $\times \infty$

이게 무슨 의미냐면, 먼저 $1$부터 $N$까지의 합부터 생각해보자.

 

$\sum\limits_{i=1}^{n} i$는 간단하게 $\frac{n(n+1)}{2}$로 쓸 수 있다. 그러면 이 값에 다시 시그마를 붙이면? $\sum\limits_{i=1}^{n} \frac{i(i+1)}{2}$이 된다. 이 값은 무엇일까? 일단은 그냥 식 정리를 해보자.

 

$\frac{1}{2} \sum\limits_{i=1}^{n} (i^{2}+i)$로 바꿔 쓸 수 있고,  $ \sum\limits_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} $이므로 $\frac{1}{2} (\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2})$가 된다.

$\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}$를 잘 정리해보자.

 

$\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} = \frac{n(n+1)(2n+1)}{6} + \frac{3n(n+1)}{6}  = \frac{ n(n+1)(2n+1)+3)}{6} = \frac{ n(n+1)(2n+4)}{6} = \frac{ n(n+1)(n+2)}{3} $가 된다. 이제 원래의 식에 적용해서$\frac{1}{2} \sum\limits_{i=1}^{n} (i^{2}+i) =$ $ \frac{ n(n+1)(n+2)}{6} $가 되는 것을 확인할 수 있다.

 

다음 식은 예상하겠지만 $\sum\limits_{i=1}^{n} \frac{ i(i+1)(i+2)}{6} $이 되겠다. 당연히 이 식을 구하기에는 너무 많은 식 정리가 필요하다. 여기서 하키스틱 항등식을 사용한다면 그 다음 시그마, 그 다음다음 시그마도 잘 구할 수 있다. 먼저 이 하키스틱 항등식은 다음과 같다.

 

$\sum\limits_{j=r}^{m} \binom{j}{r} = \binom{m+1}{r+1} $

 

앞서 만들었던 식 $\frac{n(n+1)}{2}$는 $\binom{n+1}{2}$로도 쓸 수 있다. $\sum\limits_{i=1}^{n} \binom{i+1}{2}$는 저 위의 식에서 $r = 2$, $j = i+1$라고 보면 $\sum\limits_{i=1}^{n} \binom{i+1}{2} = \sum\limits_{j=2}^{n+1} \binom{j}{2} = \binom{n+2}{3} $이 된다. $\frac{n(n+1)(n+2)}{6}$는 $\binom{n+2}{3}$이므로, 등식이 성립된다!

 

아까 식 정리를 어렵게 해야했던 $\sum\limits_{i=1}^{n} \frac{ i(i+1)(i+2)}{6} $는 이제 $\binom{n+3}{4}$라는 것을 쉽게 알 수 있다.

 

관련 문제

BOJ 13430