数学B 数学的帰納法 問題 29 解説

方針・初手

$a_k$ を直接求め続けるのではなく、$3$ で割った余りだけを追う。漸化式

$$ a_{k+2}=a_{k+1}+a_k $$

より、余り $b_k$ も $3$ を法として同じ形の漸化式に従う。したがって、$b_k$ の周期を調べれば、$c_n$ の性質が扱いやすくなる。

解法1

$a_0=1,\ a_1=2$ であるから、

$$ b_0=1,\quad b_1=2 $$

である。また、$a_{k+2}=a_{k+1}+a_k$ より、

$$ b_{k+2}\equiv b_{k+1}+b_k \pmod 3 $$

が成り立つ。ただし $b_k$ は $0,1,2$ のいずれかである。

順に計算すると、

$$ \begin{aligned} b_0&=1,\\ b_1&=2,\\ b_2&\equiv 1+2\equiv 0 \pmod 3,\\ b_3&\equiv 2+0\equiv 2 \pmod 3,\\ b_4&\equiv 0+2\equiv 2 \pmod 3,\\ b_5&\equiv 2+2\equiv 1 \pmod 3,\\ b_6&\equiv 2+1\equiv 0 \pmod 3. \end{aligned} $$

よって

$$ b_0,b_1,\ldots,b_6=1,2,0,2,2,1,0 $$

である。

さらに続けると、

$$ b_7\equiv 1+0\equiv 1 \pmod 3,\quad b_8\equiv 0+1\equiv 1 \pmod 3,\quad b_9\equiv 1+1\equiv 2 \pmod 3 $$

となる。したがって

$$ (b_8,b_9)=(1,2)=(b_0,b_1) $$

である。

漸化式は直前の2項で次の項が一意に決まるので、ここから

$$ b_{k+8}=b_k $$

がすべての $k\geqq 0$ で成り立つ。つまり、$b_k$ は周期 $8$ をもつ。

1周期分は

$$ b_0,b_1,\ldots,b_7=1,2,0,2,2,1,0,1 $$

であり、その和は

$$ 1+2+0+2+2+1+0+1=9 $$

である。

よって、任意の $n\geqq 0$ に対して、

$$ \begin{aligned} c_{n+8}-c_n &=b_{n+1}+b_{n+2}+\cdots+b_{n+8}\\ &=9 \end{aligned} $$

である。したがって

$$ c_{n+8}=c_n+9 $$

が成り立つ。

次に、

$$ n+1\leqq c_n\leqq \frac{3}{2}(n+1) $$

を示す。

$n+1$ を $8$ で割って、

$$ n+1=8q+r\quad (q\geqq 0,\ 0\leqq r\leqq 7) $$

とおく。

周期 $8$ の1周期の和は $9$ であるから、

$$ c_n=9q+T_r $$

と書ける。ただし

$$ T_r=b_0+b_1+\cdots+b_{r-1} $$

とし、$T_0=0$ とする。

1周期

$$ 1,2,0,2,2,1,0,1 $$

について部分和を調べると、

$$ \begin{array}{c|cccccccc} r&0&1&2&3&4&5&6&7\\ \hline T_r&0&1&3&3&5&7&8&8 \end{array} $$

である。

まず下限を示す。

上の表より、すべての $0\leqq r\leqq 7$ に対して

$$ T_r\geqq r $$

が成り立つ。したがって、

$$ \begin{aligned} c_n-(n+1) &=(9q+T_r)-(8q+r)\\ &=q+(T_r-r)\\ &\geqq 0 \end{aligned} $$

である。よって

$$ n+1\leqq c_n $$

が成り立つ。

次に上限を示す。

上の表より、すべての $0\leqq r\leqq 7$ に対して

$$ T_r\leqq \frac{3}{2}r $$

が成り立つ。したがって、

$$ \begin{aligned} \frac{3}{2}(n+1)-c_n &=\frac{3}{2}(8q+r)-(9q+T_r)\\ &=12q+\frac{3}{2}r-9q-T_r\\ &=3q+\left(\frac{3}{2}r-T_r\right)\\ &\geqq 0 \end{aligned} $$

である。よって

$$ c_n\leqq \frac{3}{2}(n+1) $$

が成り立つ。

以上より、

$$ n+1\leqq c_n\leqq \frac{3}{2}(n+1) $$

が示された。

解説

この問題の中心は、$a_k$ そのものではなく、$3$ で割った余り $b_k$ の周期性を見ることである。

漸化式が

$$ a_{k+2}=a_{k+1}+a_k $$

なので、余りについても $3$ を法として

$$ b_{k+2}\equiv b_{k+1}+b_k \pmod 3 $$

が成り立つ。初期値の組 $(b_0,b_1)$ が再び現れれば、それ以後は同じ列が繰り返される。

不等式の証明では、$c_n$ を周期 $8$ ごとに分けるのが自然である。1周期の和が $9$ であり、残りの部分和 $T_r$ だけを個別に確認すれば、全体の評価に帰着できる。

答え

(1)

$$ b_0,b_1,\ldots,b_6=1,2,0,2,2,1,0 $$

(2)

$$ c_{n+8}=c_n+9 $$

(3)

$$ n+1\leqq c_n\leqq \frac{3}{2}(n+1) $$