Summing Combinations

어쩌다 보니 다음과 같은 합을 하게 되었다.

\[\sum_{m=0}^n \binom{4n}{4m}+\binom{4n}{4m+1}\]

의외라면 의외인데, 이 합은 정확하게 계산할 수 있다. 이항전개를 적당히 잘 조합하면 구할 수 있기 때문.

\[(1+x)^{n}=\sum_{m=0}^n \binom{n}{m}x^m\]

위의 식에서 $n$을 $4n$으로 뻥튀기하고, $x^4=1$이란 조건을 집어넣으면 다음 식을 얻는다.

$x^4=1\Rightarrow(1+x)^{4n}=\sum_{m=0}^n \binom{4n}{4m}+\binom{4n}{4m+1}x+\binom{4n}{4m+2}x^2+\binom{4n}{4m+3}x^3$

우리 모두 $x^4=1$의 답이 $1, i, -1, -i$라는 사실을 알고 있으므로, 다음과 같은 합을 생각해 볼 수 있다.

\[\alpha(1+1)^{4n}+\beta(1+i)^{4n}+\gamma(1-1)^{4n}+\delta(1-i)^{4n}\]

첫 식에 집어넣으면, 다음과 같은 조건이 필요하다는 것을 알 수 있다.

\[\alpha+\beta+\gamma+\delta=1\\\alpha+i\beta-\gamma-i\delta=1\\\alpha-\beta+\gamma-\delta=0\\\alpha-i\beta-\gamma+i\delta=0\]

이 이후를 푸는 것은 별로 어려운 일이 아니므로 여기까지만.$\alpha,\beta, \gamma, \delta$를 구한 뒤 합만 하면 된다. 4가 아닌 경우로 확장하는 것은 별로 어려운 일이 아니니 넘어가기로 하자.