数列 \{x_n\}，\{y_n\} を次の式
x_1 = 0，x_{n+1} = x_n + n + 2\cos\left(\dfrac{2\pi x_n}{3}\right) (n = 1,\ 2,\ 3,\ \cdots)
y_{3m+1} = 3m，y_{3m+2} = 3m + 2，y_{3m+3} = 3m + 4 (m = 0,\ 1,\ 2,\ \cdots)
により定める。このとき，数列 \{x_n - y_n\} の一般項を求めよ。
x_1 = 0 は整数です。x_n が整数なら \cos\dfrac{2\pi x_n}{3} は 1 か -\dfrac{1}{2} で、x_{n+1} も整数になる。したがって x_n はすべて整数で、3 で割った余りによって 2\cos\dfrac{2\pi x_n}{3} の値が決まります。
x_n が 3 の倍数のとき 2\cos\dfrac{2\pi x_n}{3} = 2、3 の倍数でないとき 2\cos\dfrac{2\pi x_n}{3} = -1 です。
はじめの項を順に求めると、x_1 = 0、x_2 = 3、x_3 = 7、x_4 = 9、x_5 = 15、x_6 = 22、x_7 = 27 となる。
y_n ははじめから 0、2、4、3、5、7、6 と続きます。x_n - y_n を並べると 0、1、3、6、10、15、21 で、n 番目は 1 + 2 + \cdots + (n - 1) = \dfrac{n(n-1)}{2} になっている。
そこで、すべての n で x_n = y_n + \dfrac{n(n-1)}{2} となることを、n についての数学的帰納法で示します。n = 1 では 0 = 0 + 0 で成り立つ。
y_n の隣り合う項の差は、n を 3 で割った余りによって次のように決まります。
y_{3m+2} - y_{3m+1} = 2、y_{3m+3} - y_{3m+2} = 2
y_{3m+4} = 3(m+1) だから、y_{3m+4} - y_{3m+3} は 3(m+1) - (3m+4) = -1 になる。
ある n で x_n = y_n + \dfrac{n(n-1)}{2} が成り立つとします。漸化式から x_{n+1} = y_n + \dfrac{n(n+1)}{2} + 2\cos\dfrac{2\pi x_n}{3} となり、2\cos\dfrac{2\pi x_n}{3} = y_{n+1} - y_n を示せば x_{n+1} = y_{n+1} + \dfrac{n(n+1)}{2} が得られる。
示すことは、n = 3m + 1、3m + 2 のとき x_n は 3 の倍数で、n = 3m + 3 のとき x_n は 3 の倍数でないことです。
n = 3m + 1 のとき、y_n = 3m で \dfrac{n(n-1)}{2} = 3 \cdot \dfrac{m(3m+1)}{2} です。m(3m+1) は偶数だから、x_n は 3 の倍数になる。
n = 3m + 2 のとき、y_n = 3m + 2 で \dfrac{n(n-1)}{2} = \dfrac{9m(m+1)}{2} + 1 です。m(m+1) は偶数で、x_n = 3m + 3 + \dfrac{9m(m+1)}{2} は 3 の倍数。
n = 3m + 3 のとき、y_n = 3m + 4 で \dfrac{n(n-1)}{2} = 3 \cdot \dfrac{(m+1)(3m+2)}{2} です。(m+1)(3m+2) も偶数だから、x_n を 3 で割った余りは 1 になります。
どの場合も 2\cos\dfrac{2\pi x_n}{3} = y_{n+1} - y_n となり、n + 1 でも等式が成り立つ。よって数列 \{x_n - y_n\} の一般項は x_n - y_n = \dfrac{n(n-1)}{2} です。