平野塾@吉祥寺

一般項から漸化式を作って最大公約数を求める / 2017 東京大学・理系第4問

大学入試（日本）東京大学

問題
解答・解説

問題

$p=2+\sqrt{5}$ とおき，自然数 $n=1,\, 2,\, 3,\, \cdots$ に対して
$a_n=p^n+\left(-\dfrac{1}{p}\right)^n$
と定める。以下の問いに答えよ。
ただし設問(1)は結論のみを書けばよい。
(1)　 $a_1$ , $a_2$ の値を求めよ．
(2)　 $n\geqq 2$ とする。積 $a_1 a_n$ を， $a_{n+1}$ と $a_{n-1}$ を用いて表せ。
(3)　 $a_n$ は自然数であることを示せ。
(4)　 $a_{n+1}$ と $a_n$ の最大公約数を求めよ。

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

解答・解説

(1)は $\frac{1}{p}=\cdots=\sqrt{5}-2$ を使って計算するだけです。

\begin{align*}
&a_1 =p-\frac{1}{p}=(2+\sqrt{5})-(\sqrt{5}-2)=4\\
&a_2=p^2+\frac{1}{p^2}=\left(p-\frac{1}{p}\right)^2+2=18
\end{align*}

(2)は実質的に「漸化式を導け」という設問だと思います。
簡単のため $\frac{1}{p}=q$ とおきます。

知っている人も多いと思いますが， $a_n=p^n+q^n$ の特性方程式の解は $p$ と $q$ です。
解と係数の関係を使いましょう。

$p+q=a_1(=4)$ , $pq=-1$ から特性方程式は $x^2-a_1 x-1=0$ で，対応する漸化式は次のようになります。

$a_{n+1}-a_1 a_n-a_{n-1}=0\quad \therefore a_1 a_n=a_{n+1}-a_{n-1}$

(3)も漸化式です。
(2)の答えに $a_1=4$ を代入したものを使ってもいいのですが，特性方程式から導くことにします。

$a_1=4$ を使ったバージョンの特性方程式は $x^2-4 x-1=0$ で， $\{a_n\}$ の条件式は次のようになります。

$a_{n+2}=4a_{n+1}+a_{n}$
$a_1=4,\, a_2=18$

この漸化式で定まる $\{a_n\}$ はすべて自然数です。証明終わり。

(4)はユークリッドの互除法を使います。
$x$ と $y$ の最大公約数を $x,\, y)$ であらわします。

$(a_{n+1},\, a_n) = (4a_n+a_{n-1},\, a_n)=(a_{n-1},\, a_n)$

これを繰り返し使うと $(a_{n+1},\, a_n) =(a_2,\, a_1)=(18,\, 4)=2$ が言えて，答えは「2」です。

variee.hatenablog.com