漸化式と数学的帰納法 実戦編の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) 3項間漸化式 $F_{n+2}=F_{n+1}+F_n$ の一般項は、等比数列 $x^n$ を試すのが出発点だ。

$x^n$ を代入すると $x^2=x+1$(特性方程式)。この2解 $\phi ,\psi$ が「素材の等比数列」になる。一般項は $F_n=A{\phi }^n+B{\psi }^n$ の形。あとは初期条件 $F_1=F_2=1$ で係数 $A,B$ を決めるだけだ。

① 特性方程式を解く。 $x^2=x+1$、すなわち $x^2-x-1=0$ の解は $$\phi =\frac{1+\sqrt{5}}{2},\psi =\frac{1-\sqrt{5}}{2}.$$ ② 一般項の形。 $F_n=A{\phi }^n+B{\psi }^n$ とおく。$F_1=F_2=1$ を代入(あるいは $F_0=0,F_1=1$ を使う)して $$A\phi +B\psi =1,A{\phi }^2+B{\psi }^2=1.$$ ③ $A,B$ を決める。 $\phi -\psi =\sqrt{5}$ に注意して解くと $A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}}$。よって $$F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}=\frac{1}{\sqrt{5}}\left\{{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right\}.$$

まとめ $3$ 項間漸化式は特性方程式の $2$ 解のべきの線形結合。フィボナッチでは黄金比 $\phi$ とその共役 $\psi$ で $F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}$(ビネの公式)。整数列に無理数が現れるが、${\psi }^n$ の項と合わさって必ず整数になる。漸化式・無理数の融合。

発展。 $\psi =\frac{1-\sqrt{5}}{2}$ は $|\psi |<1$ なので ${\psi }^n\to 0$。だから $F_n$ は $\frac{{\phi }^n}{\sqrt{5}}$ に最も近い整数で表せる。同じ「消える項」の構造は、${\phi }^n=\phi \cdot F_n+F_{n-1}$ のようなフィボナッチ恒等式や、リュカ数列(初期値違い)にも共通する。

別解

別解:「最も近い整数」で捉える(得意な人向けの高い視点)。 ビネの公式 $F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}$ で、$\psi =\frac{1-\sqrt{5}}{2}\approx -0.618$ は絶対値が $1$ 未満。だから ${\psi }^n$ は $n$ が大きいほど $0$ に近づく。

つまり $F_n$ は $\frac{{\phi }^n}{\sqrt{5}}$ にごく近い。実際、両者の差は $\frac{|\psi {|}^n}{\sqrt{5}}<\frac{1}{2}$ なので

$$F_n=\left[\frac{{\phi }^n}{\sqrt{5}}\text{に最も近い整数}\right].$$

たとえば $\frac{{\phi }^{10}}{\sqrt{5}}=55.003\cdots$ を四捨五入して $F_{10}=55$。無理数だらけの式が四捨五入ひとつで整数のフィボナッチ数を返す。${\psi }^n\to 0$ という「消える項」の存在が、この便利な近似を保証している。

方針

解答

⓪ 発想(どう考え始めるか) 比 $r_n=\frac{F_{n+1}}{F_n}$ 自身の漸化式を作りたい。$F_{n+2}=F_{n+1}+F_n$ の両辺を $F_{n+1}$ で割ると、$r_{n+1}=1+\frac{F_n}{F_{n+1}}=1+\frac{1}{r_n}$ が得られる。

比だけの漸化式が立った。極限 $r$ が存在すれば、両辺で $n\to \infty$ として $r=1+\frac{1}{r}$。これを整理すると $r^2=r+1$。正の解が黄金比 $\frac{1+\sqrt{5}}{2}$ だ。

① 比の漸化式。 $F_{n+2}=F_{n+1}+F_n$ の両辺を $F_{n+1}$($>0$)で割ると $$r_{n+1}=\frac{F_{n+2}}{F_{n+1}}=1+\frac{F_n}{F_{n+1}}=1+\frac{1}{r_n}.$$ ② 極限の方程式。 $r_n\to r$ とすると、$r_{n+1}=1+\frac{1}{r_n}$ で $n\to \infty$ として $$r=1+\frac{1}{r}.⟹r^2=r+1.$$ ③ 正の解。 $r^2-r-1=0$ の解は $r=\frac{1\pm \sqrt{5}}{2}$。$r_n=\frac{F_{n+1}}{F_n}>0$ だから $r>0$、よって $$\underset{n\to \infty }{\lim }{r}_n=\frac{1+\sqrt{5}}{2}(=\phi ,\text{黄金比}).$$

まとめ比の漸化式 $r_{n+1}=1+\frac{1}{r_n}$ の不動点が極限。$r=1+\frac{1}{r}$ を解いて黄金比 $\frac{1+\sqrt{5}}{2}$。フィボナッチ数の隣接比は黄金比に近づく。漸化式と極限の融合。

発展。 黄金比 $\phi$ は、無限連分数がすべて $1$ という「最も単純な」形をもつ。この単純さゆえに $\phi$ は有理数で最も近似しにくい無理数(最も無理数らしい数)とされ、ヒマワリの種の配置や葉序が $\phi$ に関係する黄金角 $\frac{360^{\circ }}{{\phi }^2}\approx 137.5^{\circ }$ を選ぶ理由にもなっている。

別解

別解:無限連分数として読む(得意な人向けの高い視点)。 漸化式 $r_{n+1}=1+\frac{1}{r_n}$ を、代入し続けてみる。

$$r=1+\frac{1}{r}=1+\frac{1}{1+\frac{1}{r}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{\ddots }}}.$$

$1$ だけが並ぶ無限連分数だ。この値 $r$ は自分自身を含む方程式 $r=1+\frac{1}{r}$、すなわち $r^2-r-1=0$ を満たし、正の解 $\frac{1+\sqrt{5}}{2}=\phi$。

しかも $r_n$ は $\phi$ を上と下から交互にはさみながら近づく($r_1=1<\phi$、$r_2=2>\phi$、$r_3=1.5<\phi$、$\dots$)。連分数を途中で打ち切った近似値がフィボナッチ比 $\frac{F_{n+1}}{F_n}$ そのものだから、比の収束と連分数は同じ現象を見ている。

方針

解答

⓪ 発想(どう考え始めるか) 非線形漸化式 $a_{n+1}=a_n^2-2$ は、$a_n$ を $x^k+x^{-k}$ の形で表せると見通しがよくなる。なぜなら $${\left(x^k+x^{-k}\right)}^2-2=x^{2k}+2+x^{-2k}-2=x^{2k}+x^{-2k}$$ で、$2$ 乗して $2$ を引くと指数が $2$ 倍になるだけ。だから最初に $a_1=x+\frac{1}{x}$ となる $x$ を見つければ、$a_n$ は $x$ の指数が $2$ のべきで増えていく形になる。$a_1=\frac{5}{2}=2+\frac{1}{2}$ だから $x=2$。漸化式と指数の融合。

① $a_1$ を $x+\frac{1}{x}$ の形に。 $a_1=\frac{5}{2}=2+\frac{1}{2}=2+2^{-1}$。よって $x=2$ とすれば $a_1=2^1+2^{-1}$。

② 指数の変化を追う。 $a_n=2^k+2^{-k}$ とすると、①の変形で $$a_{n+1}=a_n^2-2=2^{2k}+2^{-2k}.$$ つまり指数 $k$ は毎回 $2$ 倍になる。$a_1$ で $k=1$ だから、$a_n$ では $k=2^{n-1}$。

③ 一般項。 $$a_n=2^{2^{n-1}}+2^{-2^{n-1}}=2^{2^{n-1}}+\frac{1}{2^{2^{n-1}}}.$$ (検算:$a_2=2^2+2^{-2}=4+\frac{1}{4}=\frac{17}{4}={\left(\frac{5}{2}\right)}^2-2$。)

まとめ $2$ 乗して $2$ を引く漸化式は、$x^k+x^{-k}$ の形で指数が $2$ 倍になる性質を使う。$a_1=2+\frac{1}{2}$ から $x=2,k=2^{n-1}$ で $a_n=2^{2^{n-1}}+2^{-2^{n-1}}$。漸化式と指数の融合。

発展。 $a_{n+1}=a_n^2-2$ は $a_n=x^{2^{n-1}}+x^{-2^{n-1}}$ で解けたが、$|a_1|<2$ なら $a_1=2\cos \theta$ とおけて $a_n=2\cos (2^{n-1}\theta )$ という三角関数の姿になる。$x+\frac{1}{x}$(双曲線側)と $2\cos \theta$(円側)の使い分けは、$a_1$ が $2$ より大きいか小さいかで決まる。

別解

別解:積を望遠鏡にして一般項を確かめる(得意な人向けの高い視点)。 $x=2$ として $a_n=x^{2^{n-1}}+x^{-2^{n-1}}$ が答え。この形は積の望遠鏡でも裏づけられる。

$x-\frac{1}{x}$ を各項に掛けると、$\left(x^k-x^{-k}\right)\left(x^k+x^{-k}\right)=x^{2k}-x^{-2k}$ という「差が2倍角になる」関係が使える。これを $a_1,a_2,\dots ,a_{n-1}$ に順に適用すると

$$\left(x-\frac{1}{x}\right)a_1{a}_2\cdots a_{n-1}=x^{2^{n-1}}-x^{-2^{n-1}}.$$

左辺の積が次々に折りたたまれ、右辺だけが残る(望遠鏡)。$x=2$ を入れると、部分積 $a_1\cdots a_{n-1}$ の値まですぐに分かる。

「$2$ 乗して $2$ を引くと指数が倍」(本解)を和の側から見たのに対し、この望遠鏡は積の側から同じ構造を照らす。$a_n=x^{2^{n-1}}+x^{-2^{n-1}}$ が確かに漸化式と初期値に合うことの、独立な検算にもなっている。

方針

解答

⓪ 発想(どう考え始めるか) 領域の数を直接数えるのは難しい。「$1$ 個増やすと領域がいくつ増えるか」を追うのが漸化式の発想だ。

$n$ 個目の円は既存の $n-1$ 個の円それぞれと $2$ 点で交わる。つまり円周上に $2(n-1)$ 個の交点ができる。交点は円周を $2(n-1)$ 本の弧に分け、各弧が既存の領域を1つずつ2分割する。だから領域は $2(n-1)$ 個増える。この増分の漸化式を $a_1=2$ から解く。

① 漸化式を立てる。 $1$ 個目の円は平面を内・外の $2$ 領域に分けるので $a_1=2$。$n$ 個目($n\ge 2$)を足すと領域が $2(n-1)$ 増えるから $$a_n=a_{n-1}+2(n-1).$$

② 漸化式を解く。 $a_n=a_1+\sum _{k=2}^{n}2(k-1)=2+2(1+2+\cdots +(n-1))=2+2\cdot \frac{(n-1)n}{2}.$

③ 整理する。 $$a_n=2+n(n-1)=n^2-n+2.$$ (検算:$a_1=2,a_2=4,a_3=8$。$3$ 個の円で $8$ 領域。)

まとめ新しい円が既存と $2(n-1)$ 点で交わり領域を $2(n-1)$ 増やす、という増分から漸化式 $a_n=a_{n-1}+2(n-1)$。解いて $a_n=n^2-n+2$。漸化式と数え上げ・幾何の融合。

発展。 同じ「増分を数える」発想で、一般の位置にある $n$ 本の直線は平面を $\frac{n^2+n+2}{2}$ 個に分ける($k$ 本目が既存の $k-1$ 本と交わり領域を $k$ 個増やす)。円は「閉じている」分だけ増分が $2$ 倍で、領域数も速く増える。図形が空間を何分割するかは、交わり方の数え上げに帰着する。

別解

別解:オイラーの多面体公式で数える(得意な人向けの高い視点)。 円の配置を「平面のグラフ(頂点と辺)」とみて、オイラーの公式 $V-E+F=2$ で領域数 $F$ を出す。

• 頂点 $V$: 円は2つずつ $2$ 点で交わるから $V=2\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)$。
• 辺 $E$: 各円は他の $n-1$ 個と交わって $2(n-1)$ 個の交点をもち、円周が $2(n-1)$ 本の弧(辺)に分かれる。全部で $E=2n(n-1)$。

オイラーの公式から

$$F=E-V+2=2n(n-1)-n(n-1)+2=n(n-1)+2=n^2-n+2.$$

($F$ は無限に広がる外側の領域も1つと数えている。)増分を1つずつ足す漸化式(本解)に対し、こちらは頂点・辺・面の総数をまとめて数える。同じ $n^2-n+2$ に、まったく別の道から着く。

方針

解答

⓪ 発想(どう考え始めるか) $\gcd (2^m-1,2^n-1)$ を、指数についての互除法に置き換えたい。

決め手は割り算の恒等式 $M_m=2^{m-n}{M}_n+M_{m-n}$ だ。$2^m-1$ を $2^n-1$ で割ると、余りがちょうど $M_{m-n}=2^{m-n}-1$ になる。つまりユークリッドの互除法で指数の引き算 $m-n$ が起こる。指数について互除法を回すと $\gcd (m,n)$ に落ち、$\gcd (M_m,M_n)=2^{\gcd (m,n)}-1$ が出る。

① 割り算の恒等式。 $2^{m-n}(2^n-1)=2^m-2^{m-n}$ だから $$2^m-1=(2^m-2^{m-n})+(2^{m-n}-1)=2^{m-n}{M}_n+M_{m-n}.$$ よって $M_m$ を $M_n$ で割った余りは $M_{m-n}$($0\le M_{m-n}<M_n$、$m>n$ より)。ゆえに $$\gcd (M_m,M_n)=\gcd (M_n,M_{m-n})=\gcd (M_{m-n},M_n).$$ ② 互除法が指数に対応。 この操作は指数について $(m,n)\to (m-n,n)$ となり、ユークリッドの互除法(引き算版)そのものだ。互除法を繰り返すと、指数は最終的に $\gcd (m,n)$ に落ちる。

③ 結論。 よって $$\gcd (M_m,M_n)=M_{\gcd (m,n)}=2^{\gcd (m,n)}-1.$$ (例:$\gcd (M_6,M_4)=\gcd (63,15)=3=2^2-1=M_{\gcd (6,4)}$。)

まとめ $M_m$ を $M_n$ で割った余りが $M_{m-n}$、という恒等式で互除法が指数の引き算になる。回し切ると $\gcd (M_m,M_n)=2^{\gcd (m,n)}-1$。漸化式(互除法)と整数の融合。

発展。 $M_p=2^p-1$ が素数(メルセンヌ素数)になるには $p$ 自身が素数であることが必要だ($p=ab$ なら $M_a\mid M_p$ で分解してしまう)。逆は成り立たず、$M_{11}=2047=23\times 89$ は合成数。知られている最大の素数の多くがメルセンヌ数の形なのは、この構造と高速判定法(リュカ・レーマー法)があるからだ。

別解

別解:「$d\mid n⟺M_d\mid M_n$」を先に押さえる(得意な人向けの高い視点)。 割り切れる関係を直接使うルートもある。

$2^n-1$ を等比数列の和とみると、$d\mid n$ のとき

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

と因数分解できる。つまり $d\mid n\Rightarrow M_d\mid M_n$。逆に $d\nmid n$ なら割り切れない(余りが $M_{n\mathrm{mod}d}\ne 0$)。まとめると

$$M_d\mid M_n⟺d\mid n.$$

すると $\gcd (M_m,M_n)$ が何になるかが分かる。$M_m$ と $M_n$ をともに割る最大の $M_d$ は、$d\mid m$ かつ $d\mid n$ を満たす最大の $d$、すなわち $d=\gcd (m,n)$ に対応する。よって

$$\gcd (M_m,M_n)=2^{\gcd (m,n)}-1.$$

互除法を回す本解と、「割り切れる条件」を先に確立するこの解。どちらも「指数の整除が、メルセンヌ数の整除に写る」という一点に支えられている。

方針

解答

⓪ 発想(どう考え始めるか) 漸化式 $a_{n+1}=\sqrt{2+a_n}$ がもし収束すれば、極限 $\alpha$ は $\alpha =\sqrt{2+\alpha }$ を満たす。${\alpha }^2=2+\alpha$ を解くと $\alpha =2$(正の解)。

だが「収束すれば」を保証しないと極限は語れない。そこで単調性と有界性を示す。帰納法で各項が $2$ 未満(上に有界)、かつ $a_{n+1}>a_n$(単調増加)を示す。上に有界で単調増加な列は必ず収束するので、この2つを示せばよい。

① 上に有界($a_n<2$)。 帰納法。$a_1=\sqrt{2}<2$。$a_n<2$ を仮定すると $$a_{n+1}=\sqrt{2+a_n}<\sqrt{2+2}=2.$$ よってすべての $n$ で $a_n<2$。

② 単調増加。 $a_n<2$ のとき $a_{n+1}^2-a_n^2=(2+a_n)-a_n^2=-(a_n-2)(a_n+1)$。$a_n<2,a_n>0$ より $(a_n-2)<0,(a_n+1)>0$ だから $a_{n+1}^2-a_n^2>0$、すなわち $a_{n+1}>a_n$。

③ 極限。 上に有界で単調増加だから収束する。極限を $\alpha$ とすると $\alpha =\sqrt{2+\alpha }$、$2$ 乗して ${\alpha }^2=2+\alpha$、${\alpha }^2-\alpha -2=0$、$(\alpha -2)(\alpha +1)=0$。$\alpha >0$ だから $$\underset{n\to \infty }{\lim }{a}_n=2.$$

まとめ漸化式の極限は「有界＋単調で存在を保証→不動点で値を確定」。$a_n<2$・単調増加から収束し、極限は $\alpha =\sqrt{2+\alpha }$ の正の解 $2$。漸化式と極限の融合。

発展。 一般項 $a_n=2\cos \frac{\pi }{2^{n+1}}$ は、入れ子の根号 $\sqrt{2+\sqrt{2+\sqrt{2}}}$ が三角関数で書けることを示す。同じ道具でヴィエタの公式 $\frac{2}{\pi }=\frac{\sqrt{2}}{2}\cdot \frac{\sqrt{2+\sqrt{2}}}{2}\cdots$ が導け、円周率を根号の入れ子で表す歴史的な無限積につながる。

別解

別解:三角関数で一般項を書く(得意な人向けの高い視点)。 $2+2\cos \theta =4{\cos }^2\frac{\theta }{2}$(半角)から、$\sqrt{2+2\cos \theta }=2\cos \frac{\theta }{2}$。これは漸化式 $a_{n+1}=\sqrt{2+a_n}$ と同じ形をしている。

そこで $a_n=2\cos {\theta }_n$ とおくと、$a_{n+1}=2\cos \frac{{\theta }_n}{2}$、つまり角が毎回半分になる。$a_1=\sqrt{2}=2\cos \frac{\pi }{4}$ から出発すると ${\theta }_n=\frac{\pi }{2^{n+1}}$、すなわち

$$a_n=2\cos \frac{\pi }{2^{n+1}}.$$

$n\to \infty$ で角 $\frac{\pi }{2^{n+1}}\to 0$、$\cos 0=1$ だから $a_n\to 2\cos 0=2$。単調有界で極限の存在を示す本解に対し、こちらは一般項そのものを閉じた式で書き、収束を $\cos$ の連続性で言い切る。入れ子の根号 $\sqrt{2+\sqrt{2+\sqrt{2}}}$ が $2\cos$ で表せる、有名な変身だ。

方針

解答

⓪ 発想(どう考え始めるか) $n$ 段の上り方を、最後の1歩で場合分けするのが漸化式の常道だ。

最後の1歩が $1$ 段なら、その前は $n-1$ 段を上っている。$2$ 段なら $n-2$ 段、$3$ 段なら $n-3$ 段。この3つは重ならず、全体を覆い尽くす。だから $a_n=a_{n-1}+a_{n-2}+a_{n-3}$(トリボナッチ数列)。初期値 $a_1=1,a_2=2,a_3=4$ から順に計算する。

① 漸化式を立てる。 最後の $1$ 歩で分けると $$a_n=\underset{\text{最後1段}}{\underbrace{a_{n-1}}}+\underset{\text{最後2段}}{\underbrace{a_{n-2}}}+\underset{\text{最後3段}}{\underbrace{a_{n-3}}}(n\ge 4).$$ ② 初期値。 $a_1=1$($1$)、$a_2=2$($1+1,2$)、$a_3=4$($1+1+1,1+2,2+1,3$)。

③ 順に計算。 $$a_4=a_3+a_2+a_1=4+2+1=7,$$ $$a_5=a_4+a_3+a_2=7+4+2=13,$$ $$a_6=a_5+a_4+a_3=13+7+4=24.$$ よって $a_6=24$。

まとめ最後の $1$ 歩($1\cdot 2\cdot 3$ 段)で場合分けすると $a_n=a_{n-1}+a_{n-2}+a_{n-3}$(トリボナッチ)。$a_1=1,a_2=2,a_3=4$ から $a_6=24$。漸化式と数え上げの融合。

発展。 上れる歩幅を $1,2$ に限るとフィボナッチ、$1,2,3$ でトリボナッチ、$1,2,3,4$ でテトラナッチと、$k$ 種類なら「直前 $k$ 項の和」の漸化式になる。歩幅の種類が増えるほど場合分けの項が増え、数列の増え方も速くなる。カウント問題は「最後の1手」で場合分けする、が共通の型だ。

別解

別解:直接「$1,2,3$ の順序つき和」を数える(苦手な人向け)。 $6$ 段の上り方は「$1,2,3$ を並べて合計 $6$ にする並べ方」の数だ。使う段数の組(何を何回使うか)で分類して数える。

• $1$ を $6$ 回: $\frac{6!}{6!}=1$ 通り
• $1$ を $4$ 回・$2$ を $1$ 回: $\frac{5!}{4!1!}=5$ 通り
• $1$ を $2$ 回・$2$ を $2$ 回: $\frac{4!}{2!2!}=6$ 通り
• $2$ を $3$ 回: $\frac{3!}{3!}=1$ 通り
• $1$ を $3$ 回・$3$ を $1$ 回: $\frac{4!}{3!1!}=4$ 通り
• $1$ を $1$ 回・$2$ を $1$ 回・$3$ を $1$ 回: $3!=6$ 通り
• $3$ を $2$ 回: $\frac{2!}{2!}=1$ 通り

合計 $1+5+6+1+4+6+1=24$ 通り。漸化式(本解)の $a_6=24$ と一致する。漸化式は速いが、この直接数え上げは「なぜ $24$ か」を具体的に見せてくれる。組の数え落としがないか、漸化式の答えと突き合わせて確かめられるのも利点だ。

方針

解答

⓪ 発想(どう考え始めるか) 2つの漸化式が $a_n,b_n$ を混ぜ合っている。混ざった2つの数列を分けるときによく使うのが「和」と「差」だ。

2式を足すと $a_{n+1}+b_{n+1}=3(a_n+b_n)$ となり、和は公比 $3$ の等比数列になる。引くと $a_{n+1}-b_{n+1}=a_n-b_n$ となり、差は一定である。和と差が別々に解ければ、$a_n=\frac{(\text{和})+(\text{差})}{2}$ で復元できる。連立を「独立な2つ」に分離すれば解ける。

① 和と差の漸化式。 $2$ 式を足すと $$a_{n+1}+b_{n+1}=(2a_n+b_n)+(a_n+2b_n)=3(a_n+b_n).$$ 引くと $$a_{n+1}-b_{n+1}=(2a_n+b_n)-(a_n+2b_n)=a_n-b_n.$$ ② それぞれ解く。 $a_1+b_1=1,a_1-b_1=1$。よって $$a_n+b_n=1\cdot 3^{n-1}=3^{n-1},a_n-b_n=1.$$ ③ 復元する。 和と差から $$a_n=\frac{(a_n+b_n)+(a_n-b_n)}{2}=\frac{3^{n-1}+1}{2},b_n=\frac{3^{n-1}-1}{2}.$$ (検算:$a_2=\frac{3+1}{2}=2=2\cdot 1+0$、$b_2=\frac{3-1}{2}=1=1+0$。)

まとめ連立漸化式は和と差を作ると等比数列に分離する。$a+b$ は公比 $3$、$a-b$ は一定。復元して $a_n=\frac{3^{n-1}+1}{2},b_n=\frac{3^{n-1}-1}{2}$。漸化式(連立)と対称性の融合。

発展。 差 $a_n-b_n=1$ が一定なのは、行列 $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ が固有値 $1$ をもつから。固有値 $1$ の方向(ここでは差)は「保存量」になる。物理でも、時間発展の行列が固有値 $1$ をもつと保存則(エネルギーや運動量の保存)が生じる。連立漸化式の保存量はその数学的な原型である。

別解

別解:行列の固有値で対角化する(得意な人向けの高い視点)。 漸化式は行列で

$$\left(\begin{array}{c}{a}_{n+1}\\ b_{n+1}\end{array}\right)=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right)$$

と書ける。この行列の固有値は $\det \left(\begin{array}{cc}2-\lambda & 1\\ 1& 2-\lambda \end{array}\right)=0$ から $\lambda =3,1$。固有ベクトルは、$\lambda =3$ に $(1,1)$、$\lambda =1$ に $(1,-1)$。つまり「和 $a_n+b_n$」は $3$ 倍ずつ($\lambda =3$)、「差 $a_n-b_n$」は変わらず($\lambda =1$)。

$$a_n+b_n=3^{n-1},a_n-b_n=1⟹a_n=\frac{3^{n-1}+1}{2},b_n=\frac{3^{n-1}-1}{2}.$$

「和と差で解く」(本解)がうまくいったのは、この行列の固有ベクトルが $(1,1)$ と $(1,-1)$ だったからだ。連立漸化式を対角化の目で見ると、なぜ和と差がうまくいくのかが分かる。