음이 아닌 정수 $n$에 대하여 다음과 같이 이중차례곱(double factorial)을 정의하자.
\[ n!! = \begin{cases} 1 \cdot 3 \cdot \cdots \cdot n, \quad & \text{if
$n$ is odd} \\ 2 \cdot 4 \cdot \cdots \cdot n, & \text{if $n$ is even}
\end{cases} \]
가 성립함을 증명하여라.
주어진 문제는, 음이 아닌 정수 $n$에 대하여
\[ (4n)!! - (4n-1)!! \equiv 0 \pmod{(4n+1)} \]
임을 보이는 문제와 동치이다. 먼저 $(4n)!!$과 $(4n-1)!!$은 각각 $2n$개의 짝수, $2n$개의 홀수의 곱이라는 사실을
기억하자. 이제 $(4n)!!$을 두 부분으로 나누어
\[ (4n)!! = \underbrace{2 \cdot 4 \cdot 6 \cdot \cdots \cdot
(2n)}_{\text{$n$ entries}} \cdot \underbrace{(2n+2) \cdot \cdots \cdot
(4n-4) \cdot (4n-2) \cdot (4n)}_{\text{$n$ entries}} \]
와 같이 적는다. 그러면 법 $(4n+1)$에 대하여
\[ (4n)!! \equiv 2 \cdot 4 \cdot 6 \cdot \cdots \cdot (2n) \cdot (-(2n-1)) \cdot \cdots \cdot (-3) \cdot (-2) \cdot (-1) \pmod{(4n+1)} \]
이 성립한다. 마찬가지 방법으로 $(4n-1)!!$를 법 $(4n+1)$에 대하여 계산해 보면,
\[ \begin{aligned} (4n-1)!! &= \underbrace{1 \cdot 3 \cdot
5 \cdot \cdots \cdot (2n-1)}_{\text{$n$ entries}} \cdot \underbrace{(2n+1)
\cdot \cdots \cdot (4n-5) \cdot (4n-3) \cdot (4n-1)}_{\text{$n$ entries}} \\
&\equiv 1 \cdot 3 \cdot 5 \cdot \cdots \cdot (2n-1) \cdot (-(2n)) \cdot \cdots \cdot (-6) \cdot (-4) \cdot (-2) \pmod{(4n+1)}
\end{aligned} \]
위의 두 식을 빼주면,
\[ (4n)!! - (4n-1)!! \equiv \prod_{k=1}^{2n} k - \prod_{k=1}^{2n} k = 0
\pmod{(4n+1)} \]
를 얻고, 따라서 주어진 명제가 성립함을 알 수 있다.
