数列と整数の融合問題です。類題として2014年の東大理科第5問などが挙げられますが、本問の方が単純です。
《問題》
数列$\{a_n\}$を
$a_1=1$、$a_2=1$、$a_{n+2}=a_{n+1}a_{n}+1 \ (n=1,2,3,\cdots)$
によって定める。$0$以上の整数$k$に対して、$k$を$3$で割った余りを$R(k)$とする。例えば、$R(5)=2$ である。$b_n=R(a_n)$ とし、$s_n=b_1+b_2+b_3+\cdots+b_n$ とおく。以下の問に答えよ。
（１）$b_1$、$b_2$、$b_3$、$\cdots$、$b_8$を求めよ。
（２）$0$以上整数$p,q$に対して、$R(3p+q)=R(q)$ が成り立つことを示せ。
（３）$R(a_{n+1}a_{n}+1)=R(b_{n+1}b_{n}+1)$ が成り立つことを示せ。
（４）$b_{n+4}=b_n$ が成り立つことを示せ。
（５）数列$\{s_n\}$の一般項を求めよ。
（岐阜大学2017 前期文系第５問）
《考え方》
（１）は列挙するだけですが、$b_n$の規則性に気付かせる誘導設問になっています。$a_n$を$a_1$から列挙していくと、
$1$、$1$、$2$、$3$、$7$、$22$、$155$、$3411$、$\cdots$
となるので、$b_1$、$b_2$、$b_3$、$\cdots$、$b_8$は
$1$、$1$、$2$、$0$、$1$、$1$、$2$、$0$、$\cdots$
となります。この時点で $b_{n+4}=b_n$ となることが予想できます。（２）と（３）で証明する事柄は（４）のための準備になっています。
（２）は特に解説の必要が無いと思います。$$R(3p+q)=R(3p)+R(q)=0+R(q)$$ですから自明です。
（２）を踏まえれば（３）も簡単です。$b_n$の性質より、ある整数$q_n$を用いて $a_n=3q_n+b_n$ と表すことができます。これより、$$\begin{align} a_{n+1}a_{n}+1 &=(3q_{n+1}+b_{n+1})(3q_n+b_n)+1 \\ &=3(3q_{n+1} q_n+b_n q_{n+1}+b_{n+1} q_n)+(b_{n+1} b_n+1) \end{align}$$となりますから、$$R(a_{n+1}a_{n}+1)=R(b_{n+1}b_{n}+1) \tag{3.1}$$が成り立つことが示されました。
（４）は帰納法を用いて証明するのが無難です。もちろん、次のように考えることもできます。$b_{n+4}=b_n$ が成り立つということは$a_{n+4}$と$a_n$は$3$で割った余りが等しいということになります。つまり $a_{n+4}-a_n$ は$3$で割り切れることになりますから、$a_{n+4}-a_n$ が$3$で割り切れることを証明すればOKです。しかしこの方針だと適切な式変形がかなり難しくなってしまいます。ここは大人しく（３）を利用しましょう。$(3.1)$式が成り立つということは$$b_{n+2}=R(b_{n+1}b_{n}+1) \tag{3.2}$$が成り立つということを意味しています。
帰納法の仮定は $b_{4k-3}=1$、$b_{4k-2}=1$、$b_{4k-1}=2$、$b_{4k}=0$ とします。まず$b_{4k+1}$について調べます。
$(3.2)$式と仮定より、$$\begin{align} b_{4k+1} &=R(b_{4k}b_{4k-1}+1) \\ &= R(0+1) \\ &=1 \end{align}$$となり成立しています。他でも同様に、$$\begin{align} b_{4k+2} &=R(b_{4k+1}b_{4k}+1) \\ &= R(0+1) \\ &=1 \end{align}$$となり成立。$$\begin{align} b_{4k+3} &=R(b_{4k+2}b_{4k+1}+1) \\ &= R(1+1) \\ &=2 \end{align}$$となり成立。$$\begin{align} b_{4k+4} &=R(b_{4k+3}b_{4k+2}+1) \\ &= R(2+1) \\ &=0 \end{align}$$となり成立。
以上より、すべての自然数$k$について
$b_{4k-3}=1$、$b_{4k-2}=1$、$b_{4k-1}=2$、$b_{4k}=0$
が成立しますから、$b_{n+4}=b_n$ が成り立つことが示されました。
（５）も$4$で割った余りで場合分けします。
$\begin{align} s_{4k-3}&=(1+1+2+0)(k-1)+1 \\ &=4(k-1)+1 \\ &=4 \cdot \left(\dfrac{n+3}{4}-1\right)+1 \\ &=n \end{align}$
$\begin{align} s_{4k-2}&=(1+1+2+0)(k-1)+1+1 \\ &=4(k-1)+2 \\ &=4 \cdot \left(\dfrac{n+2}{4}-1\right)+2 \\ &=n \end{align}$
$\begin{align} s_{4k-1}&=(1+1+2+0)(k-1)+1+1+2 \\ &=4(k-1)+4 \\ &=4 \cdot \left(\dfrac{n+1}{4}-1\right)+4 \\ &=n+1 \end{align}$
$\begin{align} s_{4k}&=(1+1+2+0)k \\ &=4k \\ &=4 \cdot \dfrac{n}{4} \\ &=n \end{align}$
となるので、答えは$$s_n=\begin{cases} n+1 &(n=4k-1,k \in \mathbb{N}) \\ n &(n \ne 4k-1,k \in \mathbb{N}) \end{cases}$$となります。
（コメント）
漸化式で与えられる数列の剰余は周期性を持つという事実が背景にある問題は類題多数です。