解説

方針・初手

漸化式は、$n$ の偶奇によって処理が変わる。まずは具体的に $a_{10}$ まで計算する。

その後、$a_{n+4}$ を考えると、$n,n+1,n+2,n+3$ の偶奇が一巡するため、$a_n$ との関係が整理しやすい。

解法1

まず初項から順に計算する。

$$ a_1=0

$$

$n=1$ は奇数なので、

$$ a_2=2a_1=0

$$

$n=2$ は偶数なので、

$$ a_3=a_2+1=1

$$

$n=3$ は奇数なので、

$$ a_4=2a_3=2

$$

$n=4$ は偶数なので、

$$ a_5=a_4+1=3

$$

同様に続けると、

$$ \begin{aligned} a_6&=2a_5=6,\\ a_7&=a_6+1=7,\\ a_8&=2a_7=14,\\ a_9&=a_8+1=15,\\ a_{10}&=2a_9=30. \end{aligned}

$$

したがって、

$$ a_{10}=30

$$

である。

次に、$a_{n+4}$ を $a_n$ で表す。

**(i)**

$n$ が奇数のとき

$n$ が奇数なら、$n+1$ は偶数、$n+2$ は奇数、$n+3$ は偶数である。よって、

$$ \begin{aligned} a_{n+1}&=2a_n,\\ a_{n+2}&=a_{n+1}+1=2a_n+1,\\ a_{n+3}&=2a_{n+2}=2(2a_n+1)=4a_n+2,\\ a_{n+4}&=a_{n+3}+1=4a_n+3. \end{aligned}

$$

したがって、

$$ a_{n+4}=4a_n+3

$$

である。

**(ii)**

$n$ が偶数のとき

$n$ が偶数なら、$n+1$ は奇数、$n+2$ は偶数、$n+3$ は奇数である。よって、

$$ \begin{aligned} a_{n+1}&=a_n+1,\\ a_{n+2}&=2a_{n+1}=2(a_n+1)=2a_n+2,\\ a_{n+3}&=a_{n+2}+1=2a_n+3,\\ a_{n+4}&=2a_{n+3}=2(2a_n+3)=4a_n+6. \end{aligned}

$$

したがって、

$$ a_{n+4}=4a_n+6

$$

である。

最後に、$a_n$ を $3$ で割った余りを考える。

上で得た式を $3$ で割った余りについて見ると、$4\equiv 1 \pmod 3$ であるから、$n$ が奇数のとき

$$ a_{n+4}=4a_n+3\equiv a_n \pmod 3

$$

である。

また、$n$ が偶数のときも、

$$ a_{n+4}=4a_n+6\equiv a_n \pmod 3

$$

である。

したがって、すべての $n$ について

$$ a_{n+4}\equiv a_n \pmod 3

$$

が成り立つ。つまり、$a_n$ を $3$ で割った余りは、周期 $4$ で繰り返す。

最初の $4$ 項は、

$$ a_1=0,\quad a_2=0,\quad a_3=1,\quad a_4=2

$$

であるから、$3$ で割った余りは

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

$$

を繰り返す。

よって、

$$ \begin{cases} 0 & (n\equiv 1,2 \pmod 4),\\ 1 & (n\equiv 3 \pmod 4),\\ 2 & (n\equiv 0 \pmod 4) \end{cases}

$$

である。

解説

この問題では、漸化式が $n$ の偶奇で変わるため、$1$ 項ずつではなく $4$ 項ごとに見るのが有効である。

特に、$a_{n+4}$ を $a_n$ で表すと、どちらの場合も

$$ a_{n+4}\equiv a_n \pmod 3

$$

となる。これにより、$3$ で割った余りが周期 $4$ で繰り返すことが分かる。

余りの問題では、一般項を完全に求めなくても、合同式で周期性を見つければ十分である。

答え

**(1)**

$$ a_{10}=30

$$

**(2)**

$$ \begin{cases} a_{n+4}=4a_n+3 & (n\text{ が奇数のとき}),\\ a_{n+4}=4a_n+6 & (n\text{ が偶数のとき}) \end{cases}

$$

**(3)**

$$ \begin{cases} 0 & (n\equiv 1,2 \pmod 4),\\ 1 & (n\equiv 3 \pmod 4),\\ 2 & (n\equiv 0 \pmod 4) \end{cases}

$$