数学B / 漸化式と数学的帰納法

漸化式が保つ性質(奇数・互いに素)

最難関編数学的帰納法不変性

問題

数列 ${a_{n}}$ を $a_{1} = 1$ 、 $a_{2} = 3$ 、 $a_{n + 2} = 4 a_{n + 1} - a_{n}$ で定める。

(1) すべての項が奇数であることを示せ。

(2) 隣り合う2項 $a_{n + 1}, a_{n}$ は互いに素であることを示せ。

ヒントを見る

(1) 漸化式を偶奇(2で割った余り)の世界で読むと、各項の偶奇はどう決まっていくか。(2) 隣接2項の公約数 $d$ は、漸化式を逆向きに使うと、1つ前のペアについて何を割り切るか — 降りていった先に何があるか。

解答・解説

方針

(1)は偶奇だけ追う帰納法: 4a_{n+1} は偶数だから a_{n+2} の偶奇は a_n の偶奇の反対…ではなく「偶−奇=奇」で決まる。(2)は互除法の精神: d が a_{n+2} と a_{n+1} を割るなら a_n=4a_{n+1}−a_{n+2} も割る — 公約数が階段を1段ずつ降りて、最後は gcd(a₂,a₁)=1 に突き当たる。

解答

⓪ 発想 — どう考え始めるか。 (1)は値でなく偶奇だけを追えばよい。 $4 a_{n + 1}$ はつねに偶数だから、 $a_{n + 2} = 4 a_{n + 1} - a_{n}$ の偶奇は $a_{n}$ の偶奇だけで決まる(偶−奇=奇)。出発点の2つが奇数なら、奇数であることが遺伝していく。

(2)は互除法の精神だ。隣接2項の公約数 $d$ は、漸化式を $a_{n} = 4 a_{n + 1} - a_{n + 2}$ と逆向きに読むと、1つ前のペア $(a_{n + 1}, a_{n})$ の公約数でもある。

つまり公約数は階段を1段ずつ降りる。最後に $g cd (a_{2}, a_{1}) = g cd (3, 1) = 1$ に突き当たって、 $d = 1$ が確定する。

重要漸化式の性質証明は「性質が漸化式で遺伝するか」を見る。公約数は漸化式を遡っても保たれる(整数係数の線形漸化式の互除法)

① (1) 偶奇の帰納法。 $a_{1} = 1, a_{2} = 3$ はともに奇数。 $a_{k}, a_{k + 1}$ が奇数と仮定すると

$a_{k + 2} = 4 a_{k + 1} - a_{k} = (偶数) - (奇数) = 奇数$

よって2段仮定の帰納法により、すべての項が奇数である。

② (2) 公約数を降ろす。 $d$ を $a_{n + 2}$ と $a_{n + 1}$ の正の公約数とする。漸化式から

$a_{n} = 4 a_{n + 1} - a_{n + 2}$

で、右辺は $d$ の倍数の差だから $d ∣ a_{n}$ 。つまり $d$ は $(a_{n + 1}, a_{n})$ の公約数でもある。

③ 底に突き当てる。 ②を繰り返すと、 $d$ は $(a_{2}, a_{1}) = (3, 1)$ の公約数まで降りる。 $g cd (3, 1) = 1$ だから $d = 1$ — すなわち、どの隣り合う2項も互いに素である。

まとめ: 帰納法は「性質の遺伝」を確かめる道具 — (1)は偶奇が、(2)は公約数が、漸化式の階段をどう伝わるかを見た。とくに(2)の「公約数を漸化式で1段ずつ降ろして初期値に突き当てる」論法は、整数係数の漸化式全般で使える強力な型だ。

発展 — 一歩先へ。 別解の恒等式 $a_{n + 1}^{2} - 4 a_{n + 1} a_{n} + a_{n}^{2} = - 2$ は、隣接2項のペア $(a_{n}, a_{n + 1})$ が双曲線 $x^{2} - 4 x y + y^{2} = - 2$ の上の格子点を渡り歩いていることを意味する。 $(1, 3) \to (3, 11) \to (11, 41) \to \dots$ — 漸化式とは「曲線上の格子点を次々生む機械」でもある。ペル方程式(整数の単元)で同じ構図に再会するはずだ。

答

(1) 2段仮定の帰納法(偶奇) (2) 公約数が漸化式を遡って $g cd (a_{2}, a_{1}) = 1$ に到達する(証明)

別解

不変量で一撃(2つの小問がつながる)。 この漸化式には、変わらない量が隠れている。 $Q_{n} = a_{n + 1}^{2} - 4 a_{n + 1} a_{n} + a_{n}^{2}$ とおいて、1歩進めてみる:

$Q_{n + 1} = (4 a_{n + 1} - a_{n})^{2} - 4 (4 a_{n + 1} - a_{n}) a_{n + 1} + a_{n + 1}^{2} = a_{n + 1}^{2} - 4 a_{n + 1} a_{n} + a_{n}^{2} = Q_{n}$

(展開すると $16 a_{n + 1}^{2}$ と $- 16 a_{n + 1}^{2}$ などが打ち消し合う。)つまり $Q_{n}$ は不変量で、 $Q_{1} = 9 - 12 + 1 = - 2$ から

$a_{n + 1}^{2} - 4 a_{n + 1} a_{n} + a_{n}^{2} = - 2 (すべての n)$

ここから(2)が一撃で出る。 $d$ が $a_{n + 1}$ と $a_{n}$ をともに割るなら、左辺は $d^{2}$ の倍数、よって $d^{2} ∣ 2$ 、 $d = 1$ 。

……と言いたいところだが、 $d^{2} ∣ 2$ から言えるのは $d = 1$ (整数の平方で2を割るのは1だけ)。さらに(1)の「全項奇数」を使えば $d ∣ 2$ かつ $d$ 奇数からも $d = 1$ が出る。(1)の偶奇と(2)の互いに素が、1本の恒等式の上で握手する構図だ。

漸化式で「変わらない量」を探す目は、この単元の最終兵器のひとつ。カッシーニの恒等式(フィボナッチの $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ )と同じ血筋の議論だ。

ポイント

偶奇: 偶(4a)−奇(a)=奇が2段仮定で遺伝。
$d ∣ a_{n + 2}, a_{n + 1}$ なら $d ∣ a_{n} = 4 a_{n + 1} - a_{n + 2}$ 。
降りた先 $g cd (3, 1) = 1$ で $d = 1$ 。

よくある間違い

(1)で「偶数 $4 a_{n + 1}$ から奇数 $a_{n}$ を引くと偶数」と符号の錯覚をする(偶 $-$ 奇 $=$ 奇)。2で割った余りの表で確かめれば一瞬。
(2)の降下の向きを取り違える。必要なのは「 $d ∣ a_{n + 2}, a_{n + 1} \Rightarrow d ∣ a_{n}$ 」(遡る向き)で、根拠は $a_{n} = 4 a_{n + 1} - a_{n + 2}$ 。
(1)の偶奇の帰納で、出発点を $a_{1}$ だけにする( $a_{k + 2}$ の偶奇は $a_{k}$ に依存するので、奇数番と偶数番の2系列とも出発点が要る)。