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

前の記事の相加相乗平均の証明は, もともとはコーシーによるものだそうだが, この数学的帰納法の証明型, “Forward-Backward Induction” *1 を使って, すでに記事 $(26)$ で一度解いたことのある $2009$ 年京大理系の難問を見直してみる. というのも, “Forward-Backward Induction” による方が, はるかに簡潔で, あっけなく証明できてしまうからである. 前の証明のときは, $n= 2^k$ で命題が成立することを使うには使ったが, 背理法の矛盾を導き出すために使ったのであり, 記述が結構ややこしかったのを覚えている. いま考えると, $n= k+1$ で成立するならば $n = k$ で成立するというのは, 対偶をとれば, $n= k$ で成立しないならば $n = k+1$ でも成立しないことをいうのと同じであり, そうすると $k$ から先ではずっと成立しないことになるけれども, もしそうなら, $n = 2^k$ の列で成立することと矛盾する. だから, そもそも $n =k$ では成立しないものが存在するという仮定をおいたことが誤りである. こうして, 前の証明では, “Forward-Backward Induction” でなぜよいかということを結果に過ぎないが証明している. なお, 普通ある帰納法での証明はすぐに諦めた. 出題の構成は “Forward-Backward Induction” による証明を誘導しているのではないかと思う.

【問】
$a$ と $b$ を互いに素, すなわち $1$ 以外の公約数をもたない正の整数とし, さらに $a$ は奇数とする. 正の整数 $n$ に対して整数 $a_{n}$ , $b_{n}$ を

$(a + b\sqrt{2})^n = a_{n}+ b_{n}\sqrt{2}$

を満たすように定めるとき, 次の $(1)$ , $(2)$ を示せ. ただし, $\sqrt{2}$ が無理数であることは証明なしに用いてよい.

$\text{(1)}$ $a_{2}$ は奇数であり, $a_{2}$ と $b_{2}$ は互いに素である.
$\text{(2)}$ すべての $n$ に対して, $a_{n}$ は奇数であり, $a_{n}$ と $b_{n}$ は互いに素である.

【解】
$\text{(1)}$
$a_{2}+ b_{2}\sqrt{2} \\ =(a + b\sqrt{2})^2\\ = a^2 + 2b^2 + 2ab\sqrt{2}$

から、

$a_{2} = a^2 + 2b^2$
$b_{2} = 2ab$

であるが, $a$ は奇数だから $a^2$ は奇数、 $2b^2$ は偶数. したがって, $a_2$ は奇数である.

$a_2$ と $b_2$ が公約数として素数 $p >2$ を持つと仮定する. すると $s, t$ を正の整数として,

$a_2 = a^2 + 2b^2 = ps$
$b_2 = 2ab = pt$

と表すことができる. $b_2$ に注目すると, $p$ は奇素数で, $a, b$ は互いに素だから, $p$ は $a, b$ どちらか一方の素因数である.

そこでまず $a = pa'$ と仮定すると, $a_2$ の式から

$(pa')^2 + 2b^2 = ps$

したがって,

$2b^2 = p(s - pa'^2)$

となり, $p \neq 2$ だから, $b$ は $p$ を素因数として持つ. これは $a$ , $b$ が互いに素であることと矛盾する.

今度は $b = pb'$ と仮定すると、 $a_2$ の式から,

$a^2 + 2(pb')^2 = ps$

したがって,

$a^2 = p(s - 2pb'^2)$

となり, $a$ は $p$ を素因数に持つ.しかし, これは $a$ , $b$ が互いに素であることと矛盾する.

以上より, いずれの場合を仮定しても矛盾するので, $a_2$ , $b_2$ は互いに素である.

$\text{(2)}$

問 $(1)$ から, $n = 2$ で成立.

$n = k$ で成立すると仮定して, $n = 2k$ でも成立することを以下に示す.

$a_{2k}+ b_{2k}\sqrt{2} \\=(a + b\sqrt{2})^{2k} \\ =\{(a + b\sqrt{2})^k\}^2 \\= (a_k + b_k\sqrt{2})^2$

仮定から, $a_{k}$ は奇数であり, $a_{k}$ と $b_{k}$ は互いに素で, したがって, 問 $(1)$ の結果から, $a_{2k}$ は奇数であり, $a_{2k}$ と $b_{2k}$ は互いに素である.

$n = k+1$ で成立すると仮定して, $n = k$ でも成立することを以下に示す.

$a_{k+1}+ b_{k+1}\sqrt{2} \\ = (a + b\sqrt{2})^{k+1}\\ = (a + b\sqrt{2})(a_k + b_k\sqrt{2})\\ = aa_{k} + 2bb_{k}+ (ab_{k}+ a_{k}b)\sqrt{2}$

したがって,

$a_{k+1}= aa_{k}+ 2bb_{k}$
$b_{k+1}= ab_{k} + a_{k}b$

となるが, 最初の式で, $a_{k+1}$ は仮定から奇数, $2bb_{k}$ は偶数なので, $a_{k}$ は奇数である.

次に, $a_k$ と $b_k$ が公約数として素数 $p >2$ を持つと仮定する. すると $s, t$ を正の整数として, $a_k = ps$ , $b_k= pt$ と書けるが,

$a_{k+1} = aps+ 2bpt= p(as+2bt)$
$b_{k+1}= apt + psb = p(at+bs)$

と表すことができる. そうすると, $a_{k+1}$ , $b_{k+1}$ は, 互いに素であることに矛盾する. したがって, $a_k$ と $b_k$ は互いに素である.

以上から, すべての $n$ に対して, $a_{n}$ は奇数であり, $a_{n}$ と $b_{n}$ は互いに素である.
//

*1:ゲーム理論に「前向き後向き推論」という用語がすでにあるので英語で示した. 「双方向帰納法」という用語が使われている場合もある.