https://spherical-harmonics.hateblo.jp/entry/Todai/1993/Rika

2024.01.07記

[2] 整数からなる数列 $\{a_n\}$ を漸化式
$a_1=1$ ， $a_2=3$ ， $a_{n+2}=3a_{n+1}-7a_n$ （ $n=1$ ， $2$ ，…）
によって定める．

(1) $a_n$ が偶数となることと， $n$ が $3$ の倍数となることは同値であることを示せ．

(2) $a_n$ が $10$ の倍数となるための条件を(1)と同様の形式で求めよ．

2024.01.08記

[解答]
(1) mod 2 で考える．
$a_1\equiv 1$ ， $a_2\equiv 1$ ， $a_{n+2}\equiv a_{n+1}+a_n$ （ $n=1$ ， $2$ ，…）
であるから，
$a_3\equiv 0$ ， $a_4\equiv 1$ ， $a_5\equiv 1$
となり， $a_1=a_4$ ， $a_2=a_5$ が成立する．与えられた漸化式は連続2項が同じであれば次も同じとなるので， $a_n$ を2で割った余りは周期3で繰り返す．よって $a_n$ が偶数となることと， $n$ が $3$ の倍数となることは同値である．

(2) mod 10 で考える．
$a_1\equiv 1$ ， $a_2\equiv 3$ ， $a_{n+2}\equiv 3(a_{n+1}+a_n)$ （ $n=1$ ， $2$ ，…）
であるから，
$a_3\equiv 2$ ， $a_4\equiv 5$ ， $a_5\equiv 1$ ， $a_6\equiv 8$ ， $a_7\equiv 7$ ， $a_8\equiv 5$ ， $a_9\equiv 6$ ， $a_{10}\equiv 3$ ， $a_{11}\equiv 7$ ， $a_{12}\equiv 0$ ， $a_{13}\equiv 1$ ，， $a_{13}\equiv 3$ ，
となり， $a_1=a_{13}$ ， $a_2=a_{14}$ が成立する．与えられた漸化式は連続2項が同じであれば次も同じとなるので， $a_n$ を10で割った余りは周期12で繰り返す．よって $a_n$ が10の倍数となることと， $n$ が $12$ の倍数となることは同値である．

ちょっとした工夫であるが， $a_{n+2}\equiv 3a_{n+1}-7a_n$ よりも $a_{n+2}\equiv 3(a_{n+1}+a_n)$ の方が計算は段違いに早い（足して3倍するだけなので）．