[math]1979年東京大学文理共通問題文系問題4理系問題3

問題
方針
解答
解説
関連問題

問題

$a$を正の整数とし、数列$\{u_n\}$を次のように定める。$$\begin{cases}u_1 = 2, u_2=a^2+2\\ u_n = au_{n-2}-u_{n-1}, \ n=3, 4, 5, \cdots \end{cases}$$このとき数列$\{u_n\}$の項に$4$の倍数が現れないために、$a$の満たすべき必要十分条件を求めよ。

方針

$a$を$4$で割った余りで場合分けする。合同式を用いるのが便利である。

解答

以後$4$を法とする。

$(i)$ $a\equiv 0$のとき
$u_1 = 2, u_2 \equiv 2$であり、与えられた漸化式より$u_n \equiv -u_{n-1}$となるので、帰納的にすべての自然数$n$に対して$u_n \equiv 2$となる。

$(ii)$ $a\equiv 1$のとき
$u_1 \equiv 2, u_2 \equiv 3$であり、与えられた漸化式より$u_n \equiv u_{n-2}-u_{n-1}$となる。したがって、$u_3\equiv -1 \equiv 3, u_4 \equiv 0$となり、$4$の倍数が現れる。

$(iii)$ $a\equiv 2$のとき
$u_1 \equiv 2, u_2 \equiv 2$であり、与えられた漸化式より$u_n \equiv 2u_{n-2}-u_{n-1}$となる。したがって$u_3 \equiv 2, u_4\equiv 2$となり、帰納的にすべての自然数$n$に対して$u_n \equiv 2$となる。

$(iv)$ $a\equiv 3$のとき
$u_1 \equiv 2, u_2 \equiv 3$であり、与えられた漸化式より$u_n\equiv 3u_{n-2}-u_{n-1}$となる。したがって$u_3 \equiv 3, u_4 \equiv 2, u_5 \equiv 3$となり、帰納的にすべての自然数$n$に対して$u_n \equiv 2$あるいは$u_n \equiv 3$となる。

よって、求める必要十分条件は$a$を$4$で割った余りが$1$でないこと、となる。

解説

解答に出てきた記号から説明する。整数$n$に対して、$n$を$p$で割った余りが$a$であるとき、$n \equiv a \pmod{p}$と書く。「$n$もど（もっど）$a$、もど$p$」とか、「$p$を法として、$n$もど$a$である」と読む。例えば、$13$を$4$で割った余りは$1$だから、$13 \equiv 1 \pmod{4}$と書く。この当たり前の記号が整数の問題で非常に大きな威力を発揮する。

合同式については、以下の事項が使えれば十分である。

$a\equiv c \pmod{p}$かつ$b\equiv d \pmod{p}$ならば、$a+b\equiv c+d \pmod{p}$
$a-b \equiv b-c \pmod{p}$
$ab \equiv cd \pmod{p}$
$p$と$q$が互いに素（共通の約数を持たない）とき、$qa\equiv qc \pmod{p}$ならば$a\equiv c \pmod{p}$

合同式は簡単に扱える割には、応用が利く。$10$分程度もあれば、記号の意味も飲み込めて、使えるようになる。この東大の問題の場合普通に解くのとでは記述の時間が$10$分は違うだろう。試験場での$10$分は想像以上に大きい。また、よく大学入試で合同式を使ってもいいのかと質問されるが、全く問題ない。なお、$93$年度前期にも文理共通で、全く同様の内容でこれよりも易しいものが出題されている。