Problems and Solutions #014

Problem #014

음이 아닌 정수 $n$에 대하여 다음과 같이 이중차례곱(double factorial)을 정의하자.

$$n!!=\{\begin{array}{ll}1\cdot 3\cdot \cdots \cdot n,& \text{if }n\text{ is odd}\\ 2\cdot 4\cdot \cdots \cdot n,& \text{if }n\text{ is even}\end{array}$$

이 때, 자연수 $k$에 대하여 언제나

$$(4n)!!-(4n-1)!!=(4n+1)k$$

가 성립함을 증명하여라.

주어진 문제는, 음이 아닌 정수 $n$에 대하여

$$(4n)!!-(4n-1)!!\equiv 0(\mathrm{mod}(4n+1))$$

임을 보이는 문제와 동치이다. 먼저 $(4n)!!$과 $(4n-1)!!$은 각각 $2n$개의 짝수, $2n$개의 홀수의 곱이라는 사실을 기억하자. 이제 $(4n)!!$을 두 부분으로 나누어

$$(4n)!!=\underset{n\text{ entries}}{\underbrace{2\cdot 4\cdot 6\cdot \cdots \cdot (2n)}}\cdot \underset{n\text{ entries}}{\underbrace{(2n+2)\cdot \cdots \cdot (4n-4)\cdot (4n-2)\cdot (4n)}}$$

와 같이 적는다. 그러면 법 $(4n+1)$에 대하여

$$(4n)!!\equiv 2\cdot 4\cdot 6\cdot \cdots \cdot (2n)\cdot (-(2n-1))\cdot \cdots \cdot (-3)\cdot (-2)\cdot (-1)(\mathrm{mod}(4n+1))$$

이 성립한다. 마찬가지 방법으로 $(4n-1)!!$를 법 $(4n+1)$에 대하여 계산해 보면,

$$\begin{array}{rl}(4n-1)!!& =\underset{n\text{ entries}}{\underbrace{1\cdot 3\cdot 5\cdot \cdots \cdot (2n-1)}}\cdot \underset{n\text{ entries}}{\underbrace{(2n+1)\cdot \cdots \cdot (4n-5)\cdot (4n-3)\cdot (4n-1)}}\\ & \equiv 1\cdot 3\cdot 5\cdot \cdots \cdot (2n-1)\cdot (-(2n))\cdot \cdots \cdot (-6)\cdot (-4)\cdot (-2)(\mathrm{mod}(4n+1))\end{array}$$

위의 두 식을 빼주면,

$$(4n)!!-(4n-1)!!\equiv \prod _{k=1}^{2n}k-\prod _{k=1}^{2n}k=0(\mathrm{mod}(4n+1))$$

를 얻고, 따라서 주어진 명제가 성립함을 알 수 있다.