[math]2018年東京医科歯科大学数学問題1

問題
方針
解答
解説
関連問題
関連リンク

問題

$0$以上の整数$x, y$に対して、$R(x, y)$を次のように定義する。$$\begin{cases}xy = 0のとき、R(x, y) = 0\\ xy\ne 0のとき、xをyで割った余りをR(x, y)とする。\end{cases}$$正の整数$a, b$に対して、数列$\{r_n\}$を次のように定義する。$$r_1 = R(a, b), \ \ r_2 = R(b, r_1), \ \ r_{n+1} = R(r_{n-1}, r_n)\ \ (n = 2, 3, 4, \cdots)$$また、$r_n = 0$となる最小の$n$を$N$で表す。たとえば、$a = 7, b = 5$のとき$N = 3$である。次に、数列$\{f_n\}$を次のように定義する。$$f_1 = f_2 = 1, \ \ f_{n+1} = f_n + f_{n-1}\ \ (n = 2, 3, 4, \cdots)$$このとき以下の各問いに答えよ。
$(1)$ $a = f_{102}, b = f_{100}$のとき、$N$を求めよ。
$(2)$ 正の整数$a, b$について、$a$が$b$で割り切れないとき、$n\geq f_{N}$が成立することを示せ。
$(3)$ $2$以上の整数$n$について、$10f_n < f_{n+5}$が成立することを示せ。
$(4)$ 正の整数$a, b$について、$a$が$b$で割り切れないとき、$\displaystyle \sum_{k=1}^{N-1}{\frac{1}{r_k}} < \frac{259}{108}$が成立することを示せ。

方針

Euclidの互除法とフィボナッチ数列を題材にした比較的高級な問題である。

$(1)$ フィボナッチ数列の定義から$f_{n+1} = f_n + f_{n-1}$であるので、$f_{n+1}$を$f_n$で割った余りは$f_{n-1}$となる。丁寧に始めの数項を書き出してみると良い。

$(2)$ であるが、作り方から$$r_1 > r_2 > \cdots > r_n > \cdots$$であることは分かる。$N$が大きくなるときはどういうときかを考えると、$r_{n-1} = r_{n}\cdot q + r_{n-1}$なので、$q = 1$のときであると分かる。ここからフィボナッチ数列との関係を考察してみる。

$(3)$ シンプルに帰納法でよいだろう。

$(4)$ 素直に誘導に身を任せると良い。

解答

$(1)$ $f_{n+1} = f_{n}+f_{n-1}$であるから、$f_{n+1} = f_{n-1}+f_{n-2} + f_{n-1} = 2f_{n-1} + f_{n-2}$となる。Euclidの互除法から、$$\begin{eqnarray}r_1 & = & R(f_{102}, f_{100})\\ & = & f_{99}\\ r_2 & = & R(f_{100}, f_{99}) \\ & = & f_{98}\\ r_3 & = & R(f_{99}, f_{98})\\ & = & f_{97}\\ \cdots & = & \cdots \\ r_{97} & = & R(f_5, f_4)\\ & = & f_3 \\ r_{98} & = & R(f_4, f_3)\\ & = & f_2\\ r_{99} & = & R(f_3, f_2) \\ & = & 0\end{eqnarray}$$である。よって、$\underline{N = 99}$となる。

$(2)$ $$r_{i-1} = qr_{i} + r_{i+1}$$となる正の整数$q$が存在するので、$r_{i-1} \geq r_{i} + r_{i+1}\ \ (i = 2, 3, \cdots, N-1)$である。これから、$$r_{N-n+1} \geq f_{n}\ \ (n=2, 3, \cdots, N) \tag{b}\label{b}$$であることを数学的帰納法によって示す。$n = 2$のとき、示すべきは$r_{N-1}\geq f_2 = 1$であるが、$r_{N-1} > r_N = 0$よりこれは成立する。$n \leq k$のとき$r_{N-k+1}\geq f_k$の成立を仮定すると、$$\begin{eqnarray}r_{N-(k+1)+1} & = & r_{N-k}\\ & \geq & r_{N-k+1} + r_{N-K+2} \\ & \geq & f_k + f_{k-1} \\ & = & f_{k+1} \end{eqnarray}$$となり、\eqref{b}が成立する。\eqref{b}で特に$n = N$として、$r_1\geq f_N$である。

$(3)$ 数学的帰納法で示す。$n = 2$のとき、$f_1 = 1, f_2 = 1, f_3 = 2, f_4 = 3, f_5 =5,f_6 = 8, f_7 = 13$であるから、$10f_2 = 10 < f_7 = 13$で題意は成り立つ。$n \leq k$のとき$10f_k < f_{k+5}$が成立することを仮定すると、$$\begin{eqnarray}f_{k+6} & = & f_{k+5} + f_{k+4} \\ & > & 10(f_k + f_{k-1}) \\ & = & 10f_{k+1}\end{eqnarray}$$であり、$n = k+1$のときも題意が成り立つ。よって数学的帰納法により題意の成立が証明される。

$(4)$ \eqref{b}から$\displaystyle \frac{1}{r_{N-n+1}} \leq \frac{1}{f_n}\ \ (n = 2, 3, \cdots, N)$である。したがって、$$\sum_{k=1}^{N-1}{\frac{1}{r_k}} = \frac{1}{f_2} + \frac{1}{f_3} + \cdots + \frac{1}{f_N} \tag{c}\label{c}$$である。$(3)$から$n\geq 2$のとき$\displaystyle \frac{1}{f_{n+5}} < \frac{1}{10f_{n}}$であり、$n = 2, 3, \cdots, N$として足すと、$$\begin{eqnarray}\frac{1}{f_7} + \frac{1}{f_8} + \cdots + \frac{1}{f_{N+5}} & < & \frac{1}{10}\left(\frac{1}{f_2} + \frac{1}{f_3} + \cdots + \frac{1}{f_N}\right)\\ \iff \frac{1}{f_2} + \frac{1}{f_3} + \cdots + \frac{1}{f_N} + \frac{1}{f_{N+1}} + \cdots + \frac{1}{f_{N+5}}\\ -\left(\frac{1}{f_2} + \frac{1}{f_3} + \frac{1}{f_4} + \frac{1}{f_5} + \frac{1}{f_6}\right) & < & \frac{1}{10}\left(\frac{1}{f_2} + \frac{1}{f_3} + \cdots + \frac{1}{f_N}\right)\\ \iff \frac{9}{10}\left(\frac{1}{f_2} + \frac{1}{f_3} + \cdots + \frac{1}{f_N}\right) & < & \frac{1}{f_2} + \frac{1}{f_3} + \frac{1}{f_4} + \frac{1}{f_5} + \frac{1}{f_6}\\ & &- \left(\frac{1}{f_{N+1}} + \cdots + \frac{1}{f_{N+5}}\right) \\ & < & \left(\frac{1}{f_2} + \frac{1}{f_3} + \frac{1}{f_4} + \frac{1}{f_5} + \frac{1}{f_6} \right)\\ & = & 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{8} \\ & = & \frac{120+60+40+24+15}{120}\\ & = & \frac{259}{120}\end{eqnarray}$$である。これを整理すると、$$\frac{1}{f_2} + \frac{1}{f_3} + \cdots + \frac{1}{f_N} < \frac{10}{9}\cdot \frac{259}{120} = \frac{259}{108}$$となり、\eqref{c}と合わせて題意の不等式が成立する。