京都大学 1999年度後期・文系数学後期第3問解答・解説

問題

座標平面上で， $x$ 座標と $y$ 座標が共に整数である点を格子点という． $n$ は自然数であるとして，不等式

x > 0, y > 0, lo g_{2} \frac{y}{x} ≦ x ≦ n

を満たす格子点の個数を求めよ．

出典：京都大学 1999年度後期日程第2次学力試験後期・文系後期第3問

整数 $x$ を $1, \dots, n$ に固定する。対数不等式を $y ≦ x 2^{x}$ に直して各 $x$ の個数を数え、有限和を計算する。

条件 $x > 0, x ≦ n$ より、 $x$ は

1, 2, \dots, n

のいずれかである。 $x$ を固定すると

lo g_{2} \frac{y}{x} ≦ x

は、底2の対数が増加関数であることから

\frac{y}{x} ≦ 2^{x}, y ≦ x 2^{x}

と同値である。 $y$ は正の整数なので、この $x$ に対して $y$ は

1, 2, \dots, x 2^{x}

の $x 2^{x}$ 通りある。

従って求める格子点の個数は

x = 1 \sum n x 2^{x}

である。有限等比数列を微分するか、数学的帰納法を用いると

x = 1 \sum n x 2^{x} = 2 + (n - 1) 2^{n + 1} .

実際、 $n = 1$ では両辺は2であり、右辺に次項 $(n + 1) 2^{n + 1}$ を加えると

2 + n 2^{n + 2} = 2 + {(n + 1) - 1} 2^{(n + 1) + 1}

となる。

よって格子点の個数は

2 + (n - 1) 2^{n + 1}

である。