漸化式と数学的帰納法 最難関編の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) 漸化式 $a_{n+1}=4a_n(1-a_n)$ は、多項式のまま追うと2乗のたびに次数が倍増して破綻する。

手がかりは初項の形 ${\sin }^2\frac{\pi }{7}$ だ。$a={\sin }^2\phi$ とおいて漸化式に入れると

$$4a(1-a)=4{\sin }^2\phi {\cos }^2\phi =(2\sin \phi \cos \phi {)}^2={\sin }^{2}2\phi$$

この漸化式は倍角の公式の変装で、角を2倍にする操作だった。すると $a_n={\sin }^2\left(2^{n-1}\cdot \frac{\pi }{7}\right)$ と当たりがつき、(1)は帰納法で固定できる。(2)は角の列 $\frac{\pi }{7},\frac{2\pi }{7},\frac{4\pi }{7},\frac{8\pi }{7},\dots$ が、${\sin }^2$ の値としては3歩で一周すること($8\equiv 1$ が決め手)を見ればよい。

① (1) を帰納法で示す。 $n=1$: $a_1={\sin }^2\frac{2^0\pi }{7}$。$n=k$ で $a_k={\sin }^2\frac{2^{k-1}\pi }{7}$ と仮定すると、$\phi =\frac{2^{k-1}\pi }{7}$ として

$$a_{k+1}=4{\sin }^2\phi (1-{\sin }^2\phi )={\sin }^{2}2\phi ={\sin }^2\frac{2^k\pi }{7}$$

よって $n=k+1$ でも成り立ち、すべての $n$ で成立する。

② 角の一周((2)の決め手)。 $\frac{8\pi }{7}=\pi +\frac{\pi }{7}$ だから

$${\sin }^2\frac{8\pi }{7}={\left(-\sin \frac{\pi }{7}\right)}^2={\sin }^2\frac{\pi }{7}$$

③ (2) を示す。 (1)より

$$a_{n+3}={\sin }^2\frac{2^{n+2}\pi }{7}={\sin }^2\left(2^{n-1}\cdot \frac{8\pi }{7}\right)$$

ここで $2^{n-1}\cdot \frac{8\pi }{7}=2^{n-1}\pi +\frac{2^{n-1}\pi }{7}$ で、$2^{n-1}\pi$ は $\pi$ の整数倍だから ${\sin }^2$ の値を変えない。よって

$$a_{n+3}={\sin }^2\frac{2^{n-1}\pi }{7}=a_n$$

すなわち数列は周期3で循環する(実際 $a_1,a_2,a_3$ は相異なるので、周期はちょうど3)。

まとめ: 「初項の形が置き換えを指名する」。${\sin }^2$ で始まる2次の漸化式は倍角の公式を言いかえたものだ、と気づけばよい。倍角=角の2倍化、周期性=$2^3=8\equiv 1$(mod 7)という2つの性質が、ひとつの数列の上で重なっている。

発展。 巡回する3つの値 ${\sin }^2\frac{\pi }{7},{\sin }^2\frac{2\pi }{7},{\sin }^2\frac{4\pi }{7}$ の和はちょうど $\frac{7}{4}$ になる($\cos \frac{2\pi }{7}+\cos \frac{4\pi }{7}+\cos \frac{8\pi }{7}=-\frac{1}{2}$ から)。また、写像 $x\mapsto 4x(1-x)$ はロジスティック写像と呼ばれ、ほんの少し初期値をずらすと軌道が指数的に離れていく「カオス」の代表例。${\sin }^2$ の置き換えを使うと、そのカオスの中にある規則的な軌道(周期3)を見つけられる。

別解

指数を $7$ で割った余りで追う(巡回する理由)。 角の分子だけを見ると、列は $1,2,4,8,16,\cdots =2^{n-1}$ と倍々に進む。ここで ${\sin }^2\frac{m\pi }{7}$ の値は $m$ を $7$ で割った余りだけで決まる($m$ が $7$ 増えると角は $\pi$ 増え、${\sin }^2(\pi +\theta )={\sin }^2\theta$)。

だから見るべきは $2^{n-1}$ を $7$ で割った余りの列:

$$1,2,4,8\equiv 1,2,4,1,\dots (\mathrm{mod}7)$$

$2^3=8\equiv 1(\mathrm{mod}7)$ だから、余りは $1\to 2\to 4\to 1$ の3周期で巡回する。これがそのまま $a_{n+3}=a_n$ だ。

(2)の「周期3」は、$7$ を法とした $2$ の位数が $3$ だという整数の事実から来ている。三角関数の問題に見えるが、中心にあるのは合同式だ。整数の単元で学ぶ「$2^k$ の余りの周期」と、まったく同じものが動いている。

方針

解答

⓪ 発想(どう考え始めるか) $S_n$ と $a_n$ の混ざった条件は、$S_n-S_{n-1}=a_n$($n\ge 2$)で $S$ を消すのが第一手だ。

整理すると、係数に $n$ の入った漸化式 $(n-1)a_n=(n+1)a_{n-1}$ が現れる。定数係数でないから特性方程式は使えない。だが比の形 $\frac{a_n}{a_{n-1}}=\frac{n+1}{n-1}$ に直せば、$n=2$ から順に掛け連ねて(畳み込んで)間が約分される。階差の「足し込み」の、掛け算版だ。

① 漸化式に落とす。 $n\ge 2$ で

$$a_n=S_n-S_{n-1}=\frac{n+2}{3}{a}_n-\frac{n+1}{3}{a}_{n-1}$$

$$⟺3a_n=(n+2)a_n-(n+1)a_{n-1}⟺(n-1)a_n=(n+1)a_{n-1}$$

② 比を畳み込む。 $a_{n-1}\ne 0$(帰納的に正)として

$$\frac{a_n}{a_{n-1}}=\frac{n+1}{n-1}$$

$n=2,3,\dots ,n$ で掛け連ねると

$$\frac{a_n}{a_1}=\frac{3}{1}\cdot \frac{4}{2}\cdot \frac{5}{3}\cdots \frac{n+1}{n-1}=\frac{n(n+1)}{1\cdot 2}$$

(分子の $3,4,\dots ,n-1$ が分母と約分され、分子の末尾2つ $n,n+1$ と分母の先頭2つ $1,2$ だけが残る。)

③ 一般項と検算。 $a_1=1$ より

$$a_n=\frac{n(n+1)}{2}$$

($n=1$ でも $1$ で成立。)検算: $S_n=\sum \frac{k(k+1)}{2}=\frac{n(n+1)(n+2)}{6}=\frac{n+2}{3}\cdot \frac{n(n+1)}{2}$。たしかに条件を満たす。

まとめ: 「$S$ を消す → 比の形 → 掛けて畳む」。係数に $n$ が入る漸化式では、差(階差)で畳むか比で畳むかの2択がまず頭に浮かぶべきで、両端に何が残るかを丁寧に数えるのが、畳み込みの基本だ。

発展。 漸化式 $(n-1)a_n=(n+1)a_{n-1}$ の両辺を $n(n+1)\times n(n-1)$ 側で見ると、$\frac{a_n}{n(n+1)}=\frac{a_{n-1}}{(n-1)n}$ となる。つまり $\frac{a_n}{n(n+1)}$ が保存量(どの $n$ でも同じ値 $\frac{1}{2}$)になっている。畳み込みで一般項を求めたことは、この保存量を見つけたことと同じである。「掛けて畳む」漸化式はしばしば「何かで割ると一定」の形に言い換えられる。

別解

値を並べて予想し、帰納法で確定する(手を動かすルート)。 関係式から前へ前へと計算できる。$S_{n-1}+a_n=S_n=\frac{n+2}{3}{a}_n$ を $a_n$ について解くと

$$a_n=\frac{3S_{n-1}}{n-1}(n\ge 2)$$

$a_1=1$ から順に: $a_2=\frac{3\cdot 1}{1}=3$、$a_3=\frac{3\cdot 4}{2}=6$、$a_4=\frac{3\cdot 10}{3}=10$。$1,3,6,10$ と並び、三角数だ。そこで $a_n=\frac{n(n+1)}{2}$ と予想し、帰納法で確定する: $a_k=\frac{k(k+1)}{2}$ が $k\le n-1$ で正しければ $S_{n-1}=\frac{(n-1)n(n+1)}{6}$ で、

$$a_n=\frac{3S_{n-1}}{n-1}=\frac{3}{n-1}\cdot \frac{(n-1)n(n+1)}{6}=\frac{n(n+1)}{2}$$

予想がそのまま再生産され、帰納が閉じる。比の畳み込み(本解)は一般項を「導出」し、予想+帰納法は「言い当てて検証」する。どちらも答案として完全だが、値を数個計算して形を見る癖は、初手が見えないときの命綱になる。

方針

解答

⓪ 発想(どう考え始めるか) 分数型漸化式の決め手は不動点(その値から動かない $x$)だ。$x=\frac{4x-2}{x+1}$ を解くと $x^2-3x+2=0$、つまり $x=1,2$ の2つ。

不動点が1つなら「ずれの逆数」で等差化する。2つあるときは「2つの不動点からのずれの比」$b_n=\frac{a_n-1}{a_n-2}$ をとると等比数列になる。これがこの型の基本の方法だ。

分子 $a_{n+1}-1$ と分母 $a_{n+1}-2$ を別々に漸化式で計算すれば、共通の分母 $a_n+1$ が約分されて公比が現れる。

① 分子と分母を計算する((1))。

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

辺々割ると($a_n\ne 2$ は $b_n\ne 0$ から帰納的に保たれる)

$$b_{n+1}=\frac{a_{n+1}-1}{a_{n+1}-2}=\frac{3}{2}\cdot \frac{a_n-1}{a_n-2}=\frac{3}{2}{b}_n$$

よって $\{b_n\}$ は公比 $\frac{3}{2}$ の等比数列。

② 一般項((2)前半)。 $b_1=\frac{3-1}{3-2}=2$ だから $b_n=2{\left(\frac{3}{2}\right)}^{n-1}$。$b_n=\frac{a_n-1}{a_n-2}$ を $a_n$ について解くと $a_n=\frac{2b_n-1}{b_n-1}$。分子分母に $2^{n-1}$ を掛けて整理すれば

$$a_n=\frac{2\cdot 2\cdot 3^{n-1}/2^{n-1}-1}{2\cdot 3^{n-1}/2^{n-1}-1}=\frac{4\cdot 3^{n-1}-2^{n-1}}{2\cdot 3^{n-1}-2^{n-1}}$$

③ 極限((2)後半)。 分子分母を $3^{n-1}$ で割ると

$$a_n=\frac{4-{\left(\frac{2}{3}\right)}^{n-1}}{2-{\left(\frac{2}{3}\right)}^{n-1}}⟶\frac{4}{2}=2$$

数列は不動点のうち $2$ に吸い込まれていく($b_n\to \infty$ が $a_n\to 2$ に対応)。

まとめ: 「不動点を先に求めて型を判定する」。2つなら比 $\frac{a_n-\alpha }{a_n-\beta }$、1つなら逆数を使う。極限が不動点の一方に落ちることまで含めて、分数型漸化式の全体像が1問に収まっている。

発展。 公比 $\frac{3}{2}$ は偶然ではない。一般に $a_{n+1}=\frac{p{a}_n+q}{r{a}_n+s}$ の不動点が $\alpha ,\beta$ のとき、$b_n=\frac{a_n-\alpha }{a_n-\beta }$ の公比は $\frac{p-r\alpha }{p-r\beta }$ になる(本問は $\frac{4-1}{4-2}=\frac{3}{2}$)。しかも極限は、公比の絶対値が1より大きければ $\beta$ 側、小さければ $\alpha$ 側の不動点に落ちる。不動点と公比だけで、数列の振る舞いが分かる。

別解

分子と分母を別々の数列にする(線形化の仕組み)。 $a_n=\frac{p_n}{q_n}$ と分数のまま持ち、分子・分母を別々に更新してみる。

$$a_{n+1}=\frac{4a_n-2}{a_n+1}=\frac{4p_n-2q_n}{p_n+q_n}$$

だから $p_{n+1}=4p_n-2q_n,q_{n+1}=p_n+q_n$($p_1=3,q_1=1$)という連立の線形漸化式が取り出せる。和と差の要領でうまい組合せを探すと

$$p_{n+1}-q_{n+1}=3(p_n-q_n),p_{n+1}-2q_{n+1}=2(p_n-2q_n)$$

つまり $p_n-q_n=2\cdot 3^{n-1}$、$p_n-2q_n=2^{n-1}$(初期値 $2,1$ の等比)。この2本から $p_n,q_n$ を復元すれば、本解と同じ一般項に着く。仕組みはここから分かる。本解の $b_n=\frac{a_n-1}{a_n-2}=\frac{p_n-q_n}{p_n-2q_n}$ は、2つの等比数列の比にほかならない。だから公比は $\frac{3}{2}$。分数型漸化式の裏では、いつも連立線形漸化式が回っている。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=2a_n^2$ は2乗のせいで、繰り返すと指数が雪だるま式に増える。多項式的な変形では追えない。

だが右辺は積と累乗だけでできている。積・累乗を和・積に変える道具は対数だ。全項が正($a_1=2>0$ から帰納的に明らか)だから、$b_n={\log }_2{a}_n$ とおけて

$$b_{n+1}={\log }_2(2a_n^2)=1+2{\log }_2{a}_n=2b_n+1$$

見慣れた特性方程式型に変わった。あとはいつもの手順で解いて、最後に指数の形へ戻せばよい。

① 正であることと対数化。 $a_1=2>0$ で、$a_n>0$ なら $a_{n+1}=2a_n^2>0$ となるので、帰納的に全項正。$b_n={\log }_2{a}_n$ とおくと

$$b_{n+1}=2b_n+1,b_1={\log }_{2}2=1$$

② 特性方程式型を解く。 $x=2x+1$ より $x=-1$。$b_{n+1}+1=2(b_n+1)$ だから $\{b_n+1\}$ は初項 $b_1+1=2$、公比2の等比数列:

$$b_n+1=2\cdot 2^{n-1}=2^n⟹b_n=2^n-1$$

③ 指数に戻す。

$$a_n=2^{b_n}=2^{2^n-1}$$

検算: $a_1=2^1=2$、$a_2=2\cdot 4=8=2^3=2^{2^2-1}$、$a_3=2\cdot 64=128=2^7$。

まとめ: 「積・累乗の漸化式は対数で開く」。変換すれば教科書の特性方程式型になり、戻せば $2^{2^n-1}$ という二重指数になる。増え方の桁が違う数列($a_4=2^{15}=32768$、$a_5=2^{31}$…)でも、対数をとれば一度に説明できる。

発展。 $a_n=2^{2^n-1}$ は二重指数で、桁数そのものが毎回ほぼ倍になる($a_{10}$ は約 $308$ 桁)。「2乗する漸化式は情報量(桁数)を倍にする」。この増え方は、方程式の数値解法(ニュートン法)が1回の反復で正しい桁数を倍にしていく「2次収束」と同じリズムだ。

別解

指数だけを追って帰納法(対数を使わないルート)。 数項を計算して、$2$ の指数に注目する:

$$a_1=2^1,a_2=2\cdot (2^1{)}^2=2^3,a_3=2\cdot (2^3{)}^2=2^7,a_4=2\cdot (2^7{)}^2=2^{15}$$

指数は $1,3,7,15$ と並び、どれも「$2$ のべき $-1$」だ。そこで $a_n=2^{2^n-1}$ と予想して帰納法にかける:

$$a_{n+1}=2{\left(2^{2^n-1}\right)}^2=2^{1+2(2^n-1)}=2^{2^{n+1}-1}$$

指数の計算 $1+2(2^n-1)=2^{n+1}-1$ だけで帰納が閉じる。対数化(本解)は「なぜ特性方程式型になるのか」まで説明できる基本の方法、指数の帰納法は予想さえ立てば最も短い別の道だ。$b_n=2^n-1$ という本解の中間結果が、こちらでは指数の列としてじかに見えている。

方針

解答

⓪ 発想(どう考え始めるか) $F_{n+2}=F_{n+1}+F_n$ は2項前までを使う漸化式。だから帰納法も「$n=k,k+1$ の両方を仮定して $n=k+2$ を示す」2段仮定型が噛み合う(出発点の確認も $n=1,2$ の2つ必要)。

仮定を漸化式に入れると ${\left(\frac{7}{4}\right)}^{k+1}+{\left(\frac{7}{4}\right)}^k$。共通因数 ${\left(\frac{7}{4}\right)}^k$ をくくれば、示すべきことは

$$\frac{7}{4}+1\le {\left(\frac{7}{4}\right)}^2$$

というただの数の比較1つにまとまる。$\frac{44}{16}\le \frac{49}{16}$。この1点の余裕が帰納の歯車を回す。

① 出発点。 $F_1=1<\frac{7}{4}$、$F_2=1<{\left(\frac{7}{4}\right)}^2=\frac{49}{16}$。

② 帰納の段。 ある $k$ で $F_k<{\left(\frac{7}{4}\right)}^k$ と $F_{k+1}<{\left(\frac{7}{4}\right)}^{k+1}$ をともに仮定する。漸化式より

$$F_{k+2}=F_{k+1}+F_k<{\left(\frac{7}{4}\right)}^{k+1}+{\left(\frac{7}{4}\right)}^k={\left(\frac{7}{4}\right)}^k\left(\frac{7}{4}+1\right)={\left(\frac{7}{4}\right)}^k\cdot \frac{11}{4}$$

③ 定数の比較で締める。 $\frac{11}{4}=\frac{44}{16}\le \frac{49}{16}={\left(\frac{7}{4}\right)}^2$ だから

$$F_{k+2}<{\left(\frac{7}{4}\right)}^k\cdot {\left(\frac{7}{4}\right)}^2={\left(\frac{7}{4}\right)}^{k+2}$$

よって $n=k+2$ でも成立。①②③より、すべての自然数 $n$ で $F_n<{\left(\frac{7}{4}\right)}^n$。

まとめ: 「漸化式が2項使うなら、仮定も2つ・出発点も2つ」。帰納法の設計は漸化式の形が決める。締めの比較 $r+1\le r^2$ は $r\ge \frac{1+\sqrt{5}}{2}$(黄金比)で成り立つ。$\frac{7}{4}$ がぎりぎりではなく少し余裕のある定数であること、そして黄金比がフィボナッチの真の成長率であることが、この1行から分かる。

発展。 同じ設計図を逆向きに使うと、下からの評価も作れる。$r=\frac{3}{2}$ は $r+1>r^2$($\frac{5}{2}>\frac{9}{4}$)を満たすから、$F_{k+2}\ge {\left(\frac{3}{2}\right)}^{k-1}+{\left(\frac{3}{2}\right)}^{k-2}>{\left(\frac{3}{2}\right)}^k$ が回り、$F_n\ge {\left(\frac{3}{2}\right)}^{n-2}$。フィボナッチ数列は ${\left(\frac{3}{2}\right)}^n$ と ${\left(\frac{7}{4}\right)}^n$ の指数関数ではさまれ、真の成長率はその間の黄金比 $\phi =1.618\cdots$($F_{n+1}/F_n\to \phi$)になっている。

別解

黄金比で「ぴったり回る」評価を作る(なぜ $\frac{7}{4}$ で通るかの理由)。 もっと強い不等式も同じ方針で証明できる。$\phi =\frac{1+\sqrt{5}}{2}$(黄金比、${\phi }^2=\phi +1$)として

$$F_n\le {\phi }^{n-1}$$

出発点: $F_1=1={\phi }^0$、$F_2=1\le \phi$。帰納の段:

$$F_{k+2}\le {\phi }^k+{\phi }^{k-1}={\phi }^{k-1}(\phi +1)={\phi }^{k-1}\cdot {\phi }^2={\phi }^{k+1}$$

${\phi }^2=\phi +1$ が等号で成り立つから、評価が一切緩まずに回る。これが黄金比の特別さだ。あとは $\phi <\frac{7}{4}$ から $F_n\le {\phi }^{n-1}<{\left(\frac{7}{4}\right)}^{n-1}<{\left(\frac{7}{4}\right)}^n$ で、元の不等式が従う。

本解の比較 $r+1\le r^2$ が成り立つ境目こそ $r=\phi$。$\frac{7}{4}$ という定数は「黄金比より少し大きいから通る」。問題の裏にある本当の境界線が、この別解で分かる。

方針

解答

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

(2)は互除法の精神だ。隣接2項の公約数 $d$ は漸化式を $a_n=4a_{n+1}-a_{n+2}$ と逆向きに読むと、1つ前のペア $(a_{n+1},a_n)$ の公約数でもある。つまり公約数は階段を1段ずつ降りる。最後に $\gcd (a_2,a_1)=\gcd (3,1)=1$ に突き当たって、$d=1$ が確定する。

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

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

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

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

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

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

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

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

発展。 別解の恒等式 $a_{n+1}^2-4a_{n+1}{a}_n+a_n^2=-2$ は、隣接2項のペア $(a_n,a_{n+1})$ が双曲線 $x^2-4xy+y^2=-2$ の上の格子点を渡り歩いていることを意味する。$(1,3)\to (3,11)\to (11,41)\to \cdots$ のように、漸化式は「曲線上の格子点を次々生む機械」でもある。ペル方程式(整数の単元)で、同じ形をもう一度見ることになる。

別解

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

$$Q_{n+1}=(4a_{n+1}-a_n{)}^2-4(4a_{n+1}-a_n)a_{n+1}+a_{n+1}^2=a_{n+1}^2-4a_{n+1}{a}_n+a_n^2=Q_n$$

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

$$a_{n+1}^2-4a_{n+1}{a}_n+a_n^2=-2(\text{すべての }n)$$

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

ここで $d^2\mid 2$ から言えるのは $d=1$ だけだ(2を割り切る平方数は1だけ)。さらに(1)の「全項奇数」を使えば、$d\mid 2$ かつ $d$ が奇数であることからも $d=1$ が出る。(1)の偶奇と(2)の互いに素が1本の恒等式で結びついている。

漸化式で「変わらない量」を探す見方は、この単元でよく使う考え方のひとつだ。カッシーニの恒等式(フィボナッチの $F_{n+1}{F}_{n-1}-F_n^2=(-1{)}^n$)と同じ種類の議論である。

方針

解答

⓪ 発想(どう考え始めるか) 操作列を正面から数えるのは不可能だ。最大の円盤の動きを軸に全体を分解するのが、漸化式を立てる基本になる。

隣接制限があるから、最大円盤は $A\to C$ と一足飛びには動けず、$A\to B\to C$ と最低2回動く。そして最大円盤が動く瞬間には、残り $n-1$ 枚がすべて「今いる杭でも行き先でもない杭」に退避していなければならない。

追いかけると、$n-1$ 枚は $A\to C$、$C\to A$、$A\to C$ と3回の完全な引っ越しを強いられる。これが $3a_{n-1}+2$ となる理由だ。

① 下からの評価(必要性)。 どんな最短手順でも、最大円盤が $A\to B$ と動く直前、上の $n-1$ 枚はすべて杭 C にある(A は最大円盤の下、B は行き先だから空でなければならない)。ここまでに $n-1$ 枚の A→C の引っ越し(最小 $a_{n-1}$ 手)が済んでいる。次に最大円盤が $B\to C$ と動く直前、$n-1$ 枚はすべて杭 A に戻っている必要がある(C→A の引っ越し、最小 $a_{n-1}$ 手)。最後に $n-1$ 枚を A→C へ($a_{n-1}$ 手)。最大円盤自身の2手とあわせて

$$a_n\ge 3a_{n-1}+2$$

② 上からの評価(実現可能性)。 逆に、「$n-1$ 枚を A→C → 最大を A→B → $n-1$ 枚を C→A → 最大を B→C → $n-1$ 枚を A→C」という手順は制約をすべて守り、ちょうど $3a_{n-1}+2$ 手。よって $a_n\le 3a_{n-1}+2$。①②から

$$a_n=3a_{n-1}+2$$

③ 解く((2))。 $a_1=2$(A→B→C)。特性方程式 $x=3x+2$ より $x=-1$: $a_n+1=3(a_{n-1}+1)$ で $\{a_n+1\}$ は初項 $a_1+1=3$、公比3の等比数列。

$$a_n+1=3\cdot 3^{n-1}=3^n⟹a_n=3^n-1$$

まとめ: 「最大の円盤がどう動くか」で操作全体が3つの子問題+2手に割れる。漸化式は数式でなく操作の構造から立てるものだ。この最小手数 $3^n-1$ は、実は全円盤配置 $3^n$ 通りをすべて1回ずつ通る手順になっている(だから1手も無駄にできない)。

発展。 $3^n$ 個の配置を頂点、合法手を辺としたグラフを描くと、シェルピンスキーの三角形(自己相似のフラクタル)が現れることが知られている。隣接制限ハノイの最短手順はその三角形の一辺を端から端までなぞる道にあたる。ちなみに通常ルール(どの杭へも動かせる)なら最小手数は $2^n-1$ で、制限によって手数が $2^n$ 型から $3^n$ 型へ増える。

別解

「全部の配置を通る」ことから直接数える(状態の視点)。 円盤 $n$ 枚の置き方は、各円盤がどの杭にいるかで決まり(同じ杭の中では大きい順が強制される)、全部で $3^n$ 通り。1手動かすごとに配置は1つ変わる。

そこで次を帰納法で示す: 最短手順は $3^n$ 通りの配置をすべてちょうど1回ずつ通る(だから手数は $3^n-1$)。

$n-1$ 枚で正しいとする。$n$ 枚の最短手順は本解の3幕構成で、第1幕(最大が A にいる間)は上の $n-1$ 枚が全 $3^{n-1}$ 配置を1回ずつ通り、第2幕(最大が B)、第3幕(最大が C)も同様。最大円盤の位置が3幕を区別するから、全体で $3\times 3^{n-1}=3^n$ 配置をちょうど1回ずつ通る。手数は配置数より1少ない $3^n-1$。

漸化式を解く(本解)代わりに、「手数=通る配置の数 $-1$」という対応で答えが直接出た。1手も無駄にできない(同じ配置に二度戻れない)ことまで、おまけで証明されている。

方針

解答

⓪ 発想(どう考え始めるか) 数列は $2,3,7,43,1807,\dots$ と急激に増える。一般項は望めない。だが問われているのは逆数の和だ。

漸化式の両辺から1を引いてみる:

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

「次の項 $-1$」が「今の項 × (今の項 $-1$)」に因数分解された。積の逆数は部分分数で差に割れる。$\frac{1}{a_n}$ が「隣り合う量の差」にほどけて、和が望遠鏡式に消える寸法だ。

① (1) を示す。 上の変形から

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

($a_n\ge 2$ が帰納的に成り立つので分母は0にならない: $a_n\ge 2$ なら $a_{n+1}=a_n(a_n-1)+1\ge 2\cdot 1+1=3$。)

② (2) 望遠鏡和。 (1)を $k=1$ から $n$ まで足すと、間が消えて

$$\sum _{k=1}^n\frac{1}{a_k}=\frac{1}{a_1-1}-\frac{1}{a_{n+1}-1}=1-\frac{1}{a_{n+1}-1}$$

($a_1-1=1$。)

③ 1未満であること。 $a_{n+1}\ge 3$ より $\frac{1}{a_{n+1}-1}>0$ だから

$$\sum _{k=1}^n\frac{1}{a_k}=1-\frac{1}{a_{n+1}-1}<1$$

実際 $\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}=1-\frac{1}{1806}$ となり、和は1にどこまでも近づくが決して届かない。

まとめ: 「漸化式を引き算して因数分解 → 逆数を部分分数に → 望遠鏡」。この数列(2, 3, 7, 43, …)は「逆数の和が最速で1に迫る」ことで知られる有名な数列で、各項が『それまでの積+1』になっている($a_{n+1}-1=a_n{a}_{n-1}\cdots a_1$ も同じ変形から示せる)。

発展。 この数列(シルベスター数列)は「単位分数の和で1に迫る最速の列」として知られる。残りの隙間は $1-\sum =\frac{1}{a_{n+1}-1}$ で、$a_n$ が2乗のオーダーで増えるため、正しい桁数が毎回ほぼ倍増しながら1へ収束する。しかも各ステップで選んでいるのは「足しても1を超えない最大の単位分数」で、貪欲法そのものだ。

別解

「それまでの積 $+1$」を中心に考える(積の恒等式ルート)。 決め手の変形 $a_{n+1}-1=a_n(a_n-1)$ を繰り返し使うと、$a_n-1$ がさらに割れていく:

$$a_{n+1}-1=a_n(a_n-1)=a_n{a}_{n-1}(a_{n-1}-1)=\cdots =a_n{a}_{n-1}\cdots a_1(a_1-1)=a_1{a}_2\cdots a_n$$

($a_1-1=1$。)つまりこの数列は「次の項 $=$ それまでの積 $+1$」で成長している($2\cdot 3+1=7$、$2\cdot 3\cdot 7+1=43$)。すると逆数の和は、帰納法で

$$\sum _{k=1}^n\frac{1}{a_k}=1-\frac{1}{a_1{a}_2\cdots a_n}$$

と書ける($n=1$: $\frac{1}{2}=1-\frac{1}{2}$。$\frac{1}{a_{n+1}}=\frac{1}{\text{積}+1}$ を足すと分母が更新される)。$a_1\cdots a_n=a_{n+1}-1$ だから、本解の式と完全に一致する。

部分分数(本解)は機械的に強く、積の恒等式は数列の設計思想(積 $+1$)まで見せてくれる。$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\cdots$ が1へ非常に速く近づく理由は、分母が毎回「それまでの積」で膨らむからだ。