《ポイント》 有限個の状態に対して同じ規則で次の状態が決まるとき、状態列は途中から周期的になります。初項から周期的であることまで示すには、初期状態への復帰、または状態の推移が逆向きにも一意であることなど、追加の根拠が必要です。本問では（１）は1つの余り、（２）は連続する2つの余りを状態に取ると証明できます。まず数項を調べて周期を予想し、その後で一般の証明を行います。
《解答例》 （１） $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$で割ったときの余りは等しい。また、$b_{n+1}$ は0以上4以下なので、$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+2}$ は0以上4以下なので、$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$などと置いても良いと思います。数項を確かめることは予想には有効ですが、それだけでは全ての項の周期性の証明にはなりません。以下の状態による証明を使うと、一般の項への論理を短く示せます。
特に本問のような数列＋剰余類からの出題の場合は実験が欠かせません。まず数項で良いので確認してみてから証明のアウトラインを考える癖を付けることを推奨します。
補足：状態を使う簡潔な証明
（１）は $b_{n+1}\equiv2b_n+1\pmod5$、$0\le b_{n+1}\le4$ から次が一意に決まります。$1\to3\to2\to0\to1$ と初期状態に戻るので、以後も同じ4値を繰り返します。最初の4値が異なるので最小周期は4です。
（２）は状態を $(b_n,b_{n+1})$ とし、$(x,y)\mapsto(y,x+y\bmod5)$ と進めます。$(1,3)\to(3,4)\to(4,2)\to(2,1)\to(1,3)$ なので周期4。最初の4つの余りが異なり、最小周期も4です。1つの余りが一致しただけではなく、次を決める2項がそろって一致したことがポイントです。
途中からの周期性との違い
$a_1=1,a_{n+1}=2a_n$ の法4での余りは1,2,0,0,…。有限状態でも初項から周期的とは限りません。本問（１）の2倍＋1は法5で逆に戻れ、（２）の状態写像も $(u,v)\mapsto(v-u,u)$ と逆に戻れます。この違いを意識してください。
作問者の視点：必要な情報を状態に残す
この問題から学べるのは、単なる周期の暗記ではなく、次を決める情報の選び方です。（１）から（２）へ進むと、記憶すべき情報が1項から2項へ増えます。これは設問構造の数学的な読み解きであり、非公開の採点基準を示すものではありません。
関連解説：帰納法・不変量・剰余の周期／数列の学習ガイド