問題#B013 ★★★☆
（１）
$a_1=1$、$a_{n+1}=2a_n+1 \ (n=1,2,\cdots)$ で定められる数列$\{ a_n \}$について、第$n$項$a_n$を$5$で割ったときの余りを$b_n$とするとき、数列$\{ b_n \}$は周期数列であることを示せ。
（２）
$a_1=1$、$a_2=3$、$a_{n+2}=a_{n+1}+a_n \ (n=1,2,\cdots)$ で定められる数列$\{ a_n \}$について、第$n$項$a_n$を$5$で割ったときの余りを$b_n$とするとき、数列$\{ b_n \}$は周期数列であることを示せ。
《ポイント》
割る数を定数としたとき、漸化式で帰納的に定義される数列の余りは周期性を持つことが知られています。本問はこの事実を追認するための問題で、ごくたまに入試問題の題材になることがあります。小さい$n$で実際に割り算してみると解答の道筋が見えてきます。
《解答例》
（１）
$b_n$を小さい$n$について書き出してみると$b_1=1$、$b_2=3$、$b_3=2$、$b_4=0$、$b_5=1$、$b_6=3$、$\cdots$となるから数列$\{ b_n \}$は周期$4$で$1$、$3$、$2$、$0$を繰り返すと予想される。
$b_n$は $0 \leqq b_n \leqq 4$ を満たすから、$a_n=5c_n+b_n$ 満たすような数列$\{ c_n \}$を定義できる。よって漸化式より、
$\begin{align}a_{n+1} &=2a_n+1 \\
\therefore 5c_{n+1}+b_{n+1} &=2(5c_n+b_n)+1 \\
5c_{n+1}+b_{n+1} &=10c_n+(2b_n+1) \\
b_{n+1}-(2b_n+1) &=5(2c_n-c_{n+1}) \end{align}$
となる。右辺は$5$の倍数であるから $2b_n+1$ を$5$で割ったときの余りと$b_{n+1}$を$5$で割ったときの余りは等しい。このことと $2b_n+1 \geqq b_{n+1}$ より、$2b_n+1$ を$5$で割ったときの余りが$b_{n+1}$となる。ここで $b_1=b_5=1$ となり同じ値が現れているから、それ以降の $2b_n+1$ を$5$で割ったときの余りはすべて共通に現れるため、$b_2=b_6$、$b_3=b_7$、$b_4=b_8$、$\cdots$が次々に言える。故に数列$\{ b_n \}$はすべての正の整数$k$に対して$b_{k+4}=b_{k}$を満たすから周期数列である。
□
《（１）別解 》
$\begin{align}a_{n+4} &=2a_{n+3}+1 \\
&=4a_{n+2}+3 \\
&=8a_{n+1}+7 \\
&=16a_{n}+15 \\
&=15(a_{n}+1)+a_n \\
&\equiv a_{n} \pmod{5} \end{align}$
故に$a_{n+4}$と$a_n$は$5$で割ったときの余りが一致するから数列$\{ b_n \}$は周期$4$の周期数列である。
□
（２）
$b_n$を小さい$n$について書き出してみると$b_1=1$、$b_2=3$、$b_3=4$、$b_4=2$、$b_5=1$、$b_6=3$、$\cdots$となるから数列$\{ b_n \}$は周期$4$で$1$、$3$、$4$、$2$を繰り返すと予想される。
$b_n$は $0 \leqq b_n \leqq 4$ を満たすから、$a_n=5c_n+b_n$ 満たすような数列$\{ c_n \}$を定義できる。よって漸化式より、
$\begin{align}a_{n+2} &=a_{n+1}+a_n \\
\therefore 5c_{n+2}+b_{n+2} &=(5c_{n+1}+b_{n+1})+(5c_n+b_n) \\
b_{n+2}-(b_{n+1}+b_n) &=5\{(c_{n+1}+c_n)-c_{n+2}\} \end{align}$
となる。右辺は$5$の倍数であるから $b_{n+1}+b_n$ を$5$で割ったときの余りと$b_{n+2}$を$5$で割ったときの余りは等しい。このことと $b_{n+1}+b_n \geqq b_{n+1}$ より、$b_{n+1}+b_n$ を$5$で割ったときの余りが$b_{n+2}$となる。ここで $b_1=b_5=1$、$b_2=b_6=3$ となり同じ値が現れているから、それ以降の $b_{n+1}+b_n$ を$5$で割ったときの余りはすべて共通に現れるため、$b_3=b_7$、$b_4=b_8$、$\cdots$が次々に言える。故に数列$\{ b_n \}$はすべての正の整数$k$に対して$b_{k+4}=b_{k}$を満たすから周期数列である。
□
《（２）別解 》
$\begin{align}a_{n+4}-a_n &=a_{n+3}+a_{n+2}-a_n \\
&=2a_{n+2}+a_{n+1}-a_n \\
&=3a_{n+1}+a_{n} \end{align}$
となる。ここで $3a_{n+1}+a_{n}$ がすべての正の整数$n$に対して$5$の倍数となることを示す。$3a_{2}+a_{1}=10$、$3a_{3}+a_{2}=15$より、$n=1、2$のとき成立する。ここで$3a_{k+1}+a_{k}$、$3a_{k+2}+a_{k+1}$がともに$5$の倍数であると仮定する。
$\begin{align}3a_{k+3}+a_{k+2} &=4a_{k+2}+3a_{k+1} \\
&=(3a_{k+2}+a_{k+1})+a_{k+2}+2a_{k+1} \\
&=(3a_{k+2}+a_{k+1})+(3a_{k+1}+a_{k}) \end{align}$
仮定より $3a_{k+1}+a_{k}$、$3a_{k+2}+a_{k+1}$ はともに$5$の倍数であるから、$n=k+2$のときも成立する。故にすべての正の整数$n$に対して $3a_{n+1}+a_{n}$ は$5$の倍数である。
これより $a_{n+4}-a_n$ は$5$の倍数であるから$a_{n+4}$と$a_n$は$5$で割ったときの余りが等しい。よって数列$\{ b_n \}$は周期$4$の周期数列である。
□
《コメント》
なかなかゴツイ論証になりました。解答例では数列$\{ c_n \}$を持ち出していますが、適当な整数で$a_n=5M+b_n$などと置いても良いと思います。余りの周期性は半ば自明な事実（確かめれば直ぐに分かる）なので、入試問題で出題されるのは周期性を利用する問題ばかりですが、周期性を証明する問題が出ないとも限りません（解答例よりも優れた証明方法があるかもしれません･･･）。
特に本問のような数列＋剰余類からの出題の場合は実験が欠かせません。まず数項で良いので確認してみてから証明のアウトラインを考える癖を付けることを推奨します。