다중 중첩 시그마(다중 합산)

 

 

궁극적으로 다음 문제를 해결해 보겠다(내가 만듦).

임의 자연수 $n$에 대해 $$\sum_{i_{1}=1}^{n} \sum_{i_{2}=1}^{i_{1}} \sum_{i_{3}=1}^{i_{2}} \cdots \sum_{i_{100}=1}^{i_{99}} a_{i_{100}} = 1$$를 항상 만족시키는 수열 $a_{i}$가 있다. $a_{98}$을 구하여라.

보통 시그마가 100개 중첩된 것은 처음 보는 형식이라서 감도 안 온다. 사실 이전 글에서 설명한 시그마 역연산을 이용해 시그마 100개를 하나씩 하나씩 제거하면 된다(물론 규칙이 나온다). 먼저 다음과 같은 수열을 정의하자. $$\sum_{i_{1}=1}^{n} \sum_{i_{2}=1}^{i_{1}} \sum_{i_{3}=1}^{i_{2}} \cdots \sum_{i_{m}=1}^{i_{m-1}} a_{i_{m}} = 1$$ 를 만족하는 수열 $a_{i}$가 있을 때, $$E_{i}^{(m)}= a_{i}$$라고 하자. 그러면 문제는 $E_{98}^{(100)}$을 구하라는 말과 같다. 우선 $E_{i}^{(1)}$를 구해보자. $E_{1}^{(1)}=1$이다(당연히). 그리고 $E_{2}^{(1)}=1-1=0, E_{3}^{(1)}=1-1=0, \cdots $. 즉, $E_{i}^{(1)}$는 $1, 0, 0, 0, \cdots$이다. 일반적으로 항상 $E_{0}^{(m)}=0$라고 정의하면 $$E_{i}^{(m)}= E_{i}^{(m-1)}- E_{i-1}^{(m-1)}$$이 성립한다. 규칙이 존재하니 표로 정리해 보자.

$E_{i}^{(1)}$	1	0	0	0	0	0
$E_{i}^{(2)}$	1	-1	0	0	0	0
$E_{i}^{(3)}$	1	-2	1	0	0	0
$E_{i}^{(4)}$	1	-3	3	-1	0	0
$E_{i}^{(5)}$	1	-4	6	-4	1	0
$E_{i}^{(6)}$	1	-5	10	-10	5	-1

어딘가 매우 익숙하다. 바로 이항계수에 번갈아가며 $-1$을 곱한 결과이다. 이렇게까지만 하면 쉽게 답은 $$-\binom{99}{2}=-4851$$라고 구할 수 있다. 이제 자세하게 증명해 보자.

---

우선, $$ \displaystyle A_{i}^{(m)}=\left\{\begin{matrix}
 (-1)^{i+1}\times \displaystyle \binom{m-1}{i-1}&\mathrm{if} & 0<i\leq m\\
 0& \mathrm{if} & m<i \;\mathrm{or} \; i=0  \\
\end{matrix}\right.$$ 이렇게 수열을 정의하고 이 수열이 $E_{i}^{(m)}$과 같음을 보이겠다. 우선, $E_{i}^{(1)}= A_{i}^{(1)} $이 성립한다. 그리고 $i$가 홀수이면 $$A_{i}^{(m-1)}- A_{i-1}^{(m-1)}=\binom{m-2}{i-1}+\binom{m-2}{i-2}=\binom{m-1}{i-1}=A_{i}^{(m)}$$이고 $i$가 짝수이면 $$A_{i}^{(m-1)}- A_{i-1}^{(m-1)}=-\binom{m-2}{i-1}-\binom{m-2}{i-2}=-\binom{m-1}{i-1}=A_{i}^{(m)}$$으로 점화 조건도 성립한다. 따라서, $E_{i}^{(m)}= A_{i}^{(m)}$라고 할 수 있다. 따라서 처음 문제의 답은 $$a_{98}= E_{98}^{(100)}= -\binom{99}{2}=-4851$$이다.

---

https://waystring.tistory.com/4

조합적 항등식 증명

이 글의 내용을 이용해서 추가적으로 계산이 가능하다.
$$\sum_{i_{1}=1}^{n} \sum_{i_{2}=1}^{i_{1}} \sum_{i_{3}=1}^{i_{2}} \cdots \sum_{i_{m}=1}^{i_{m-1}} 1 =\frac{(n+m-1)!}{m!(n-1)!}$$가 성립한다.