에르미트 항등식(Hermite's identity)

정리. 에르미트 항등식(Hermite's identity)

임의의 실수 $x \in \R$와 양의 정수 $n \in \N$에 대하여 다음이 성립한다.

\[ \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \cdots + \left\lfloor x + \frac{n-1}{n} \right\rfloor = \lfloor nx \rfloor \]

증명. 다음과 같이 함수 $f$를 정의한다.

\[ f(x) = \lfloor nx \rfloor - \sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor \]

이제 이 함수가 $f(x) \equiv 0$임을 보이면 충분하다.

먼저 $x = x + \tfrac{1}{n}$을 대입해 주면,

\begin{align*} f\left( x + \frac{1}{n} \right) &= \left\lfloor n \left(x + \frac{1}{n} \right) \right\rfloor - \sum_{k=0}^{n-1} \left\lfloor x + \frac{1}{n} + \frac{k}{n} \right\rfloor \\[5px] &= \left\lfloor nx + 1 \right\rfloor - \sum_{k=0}^{n-1} \left\lfloor x + \frac{k+1}{n} \right\rfloor \\[5px] &= \underbrace{\lfloor nx + 1 \rfloor}_{\lfloor nx \rfloor} - \sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor + \underbrace{\lfloor x+1 \rfloor - \lfloor x \rfloor}_{=0} \\[5px] &= f(x) \end{align*}

즉, 임의의 $x \in \R$에 대하여 $f(x) = f(x + \tfrac{1}{n})$이 성립한다. 또한 $0 \leq x < \tfrac{1}{n}$이면

\[ 0 \leq nx < 1 \implies \lfloor nx \rfloor = 0 \]

이고, 임의의 $0 \leq k \leq n-1$에 대하여

\[ 0 \leq \frac{k}{n} \leq x + \frac{k}{n} < \frac{k+1}{n} \leq 1 \implies \left\lfloor x + \frac{k}{n} \right\rfloor = 0 \]

을 얻는다. 따라서 $0 \leq x < \tfrac{1}{n}$인 범위에서 $f(x) = 0$임을 알 수 있다. 이제 $f(x)$가 주기가 $\tfrac{1}{n}$인 주기함수라는 사실로부터 $f(x) \equiv 0$을 얻고 증명이 완료된다.

예제1. (1968 IMO) 임의의 양의 정수 $n \in \N$에 대하여, 다음 무한급수의 합을 구하여라.

\[ \sum_{k=0}^{\infty} \left\lfloor \frac{n + 2^k}{2^{k+1}} \right\rfloor \]

풀이. 에르미트 항등식에서 $n=2$인 경우 $\lfloor x \rfloor + \lfloor x + \tfrac{1}{2} \rfloor = \lfloor 2x \rfloor$이 성립한다. 그러므로

\begin{align*} \definecolor{darkblue}{RGB}{12, 39, 76} \sum_{k=0}^{\infty} \left\lfloor \frac{n + 2^k}{2^{k+1}} \right\rfloor &= \lim_{k' \to \infty} \sum_{k=0}^{k'} \left\lfloor \frac{n}{2^{k+1}} + \frac{1}{2} \right\rfloor \\[5px] &= \lim_{k' \to \infty} \sum_{k=0}^{k'} \left( \left\lfloor \frac{n}{2^k} \right\rfloor - \left\lfloor \frac{n}{2^{k+1}} \right\rfloor \right) \\[5px] &= \lim_{k' \to \infty} \lfloor n \rfloor - \left\lfloor \frac{n}{2^{k'+1}} \right\rfloor \\[5px] &= n \tag*{$\textcolor{darkblue}{\blacksquare}$} \end{align*}

예제2. 임의의 양의 정수 $n \in \N$에 대하여, 다음 급수의 합을 구하여라.

\[ \sum_{0 \leq i < j \leq n} \left\lfloor \frac{x+i}{j} \right\rfloor \]

풀이. 주어진 급수를 $S_n$이라 하자. 그러면 에르미트 항등식에 의해 다음을 얻는다.

\[ S_n - S_{n-1} = \sum_{i=0}^{n-1} \left\lfloor \frac{x+i}{n} \right\rfloor = \sum_{i=0}^{n-1} \left\lfloor \frac{x}{n} + \frac{i}{n} \right\rfloor = \lfloor x \rfloor \]

또한 $S_1 = \lfloor x \rfloor$이므로, $S_n = n \lfloor x \rfloor$임을 알 수 있다.