陥没地帯 (238) - ノリの悪い日記

ずっと前 *1 に, 次の問題 ( $2002$ 年東大文理共通) をやったことがあるけれども, 別解に気がついた. この問題は, フィボナッチ数列に関係している.

【問】
$n$ は正の整数とする。 $x^{n+1}$ を $x^2 - x - 1$ で割った余りを $a_{n}x + b_{n}$ とおく。

$\text{(1)}$
数列 $a_{n}, b_{n}, n = 1, 2, 3, \cdots$ は

$a_{n+1} = a_{n} + b_{n}$
$b_{n+1} = a_{n}$

を満たすことを示せ。

$\text{(2)}$
$n = 1, 2, 3, \cdots$ に対して、 $a_{n}, b_{n}$ はともに正の整数で、互いに素であることを証明せよ。

【別解】
$(1)$ たとえば, $n = 7$ として, $x^8$ を $x^2-x -1$ で実際に割ってみると,
商は,

$x^6 +x^5+2x^4+3x^3+5x^2+8x+13$

で, 余りは,

$21x + 13$

となり, 各項の係数は, フィボナッチ数列に関連しているのではないかと予想できる. ここで, フィボナッチ数列 $\{u_n\}$ は, $u_1=1$ , $u_2 = 1$ として,

$u_{n+2} = u_n+ u_{n+1}$

で与えられる数列のことである.

そこで, $x^{n+1}$ を $x^2-x -1$ で割った商を

$\displaystyle{u_1x^{n-1} + u_2x^{n-2} + \cdots +u_{n-1}x+ u_{n} \\= \sum_{k =1}^{n} u_{n-k+1}x^{k-1} }$

余りを

$u_{n+1}x + u_{n}$

と仮定し, これが正しいことを数学的帰納法で証明する.

$n = 1$ のとき,

$(x^2-x-1) + x +1 = x^2$

となって成立する.

$n$ で成立すると仮定すると,

$\displaystyle{ x^{n+2} \\= x\cdot x^{n+1} \\= (x^2 -x -1) \sum_{k =1}^{n} u_{n-k+1}x^{k} \\\quad + u_{n+1}x^2 + u_nx}$
$\displaystyle{ = (x^2 -x -1) \sum_{k =1}^{n} u_{n-k+1}x^k \\+ u_{n+1}(x^2-x-1) + (u_{n+1} +u_n)x +u_{n+1} \\= (x^2 -x -1) \sum_{k =1}^{n+1} u_{(n+1) -k+1}x^{k-1} \\\quad + u_{n+2}x +u_{n+1} }$

したがって, $x^{n+1}$ を $x^2-x -1$ で割った商は,

$\displaystyle{u_1x^{n-1} + u_2x^{n-2} + \cdots +u_{n-1}x+ u_{n} }$

で, 余りは,

$u_{n+1}x + u_{n}$

である *2.

$a_n = u_{n+1}$ , $b_n = u_n$ であるから,

$\begin{align} a_{n + 1} &=& u_{n+2}\\ &=& u_{n+1} + u_n\\ &=& a_n + b_n \end{align}$

$\begin{align} b_{n+1} &=& u_{n +1} \\ &=& a_n \end{align}$

$(2)$
フィボナッチ数列の各項が正の整数であることは当たり前で, フィボナッチ数列の隣接 $2$ 項は互いに素 (最大公約数が $1$ ) であるというのも, よく知られており *3 証明は省略する.
//

*1:記事 (19) 参照.

*2: 余りしか問われていないので, 実際は商の部分まで証明する必要はない.

*3:かりに知っていなくてもユークリッド互除法に関して, 習熟して自由に応用できないといけない非常に重要な証明からすぐ出る. 一般的には, 整数 $m$ , $n$ について, $\mathrm{gcd}(m,n) = \mathrm{gcd}(m-n, n)$ ということである. ただし, $0$ と $m$ の最大公約数を $|m|$ とする.