漸化式と数学的帰納法 ★★ 標準の問題 全12問

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=3a_n-2$ は、「$3$ 倍して $2$ 引く」の繰り返しだ。$-2$ さえなければ、ただの等比数列なのに。

そこで、ずらして等比にするのがこの型の定跡だ。うまい数 $\alpha$ を見つけて $a_{n+1}-\alpha =3(a_n-\alpha )$ の形に書き直せれば、$\{a_n-\alpha \}$ が公比 $3$ の等比数列になる。その $\alpha$ は $\alpha =3\alpha -2$(特性方程式)の解 $\alpha =1$。「引いてから等比、最後に足し戻す」の三段で進む。

① 特性方程式を解く。 $\alpha =3\alpha -2$ より $2\alpha =2$、$\alpha =1$。

② $\alpha$ を引いて等比の形に。

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

③ 置きかえる。 $b_n=a_n-1$ とおくと $b_{n+1}=3b_n$。初項 $b_1=a_1-1=1$。

$$b_n=1\cdot 3^{n-1}=3^{n-1}$$

④ $a_n$ に戻す。

$$a_n=3^{n-1}+1$$

まとめ:$p{a}_n+q$ 型は「特性方程式で $\alpha$ → $a_n-\alpha$ が等比」の一本道。$\alpha$ を求めたら、必ず $a_{n+1}-\alpha =p(a_n-\alpha )$ の形に書き直してから置きかえるとミスが減る。

発展。 不動点の目で見ると、この数列の行き先も分かる。公比 $3$ は $1$ より大きいから、ずれ $a_n-1=3^{n-1}$ はどんどん膨らむ。数列は不動点から離れていく。もし漸化式が $a_{n+1}=\frac{1}{3}{a}_n+2$ のように公比の絶対値が $1$ 未満なら、ずれは縮んで数列は不動点に吸い寄せられる(数IIIの極限でよく使う見方だ)。

「$1$ 次の漸化式は、不動点とそこからのずれ(等比)に分解できる」。この $1$ 行に、この型の解き方がすべて入っている。

別解

特性方程式からなぜ「$1$ を引け」と分かるのか。先に数列を書き出すと、その理由が目で確かめられる。

$$a_1=2,a_2=4,a_3=10,a_4=28,\dots$$

このままでは規則が見えにくい。ところが各項から $1$ を引くと

$$1,3,9,27,\dots$$

きれいな $3$ のべき($3^{n-1}$)が現れる。つまり $a_n=3^{n-1}+1$。

なぜ「$1$」だったのか。$1$ は $a_{n+1}=3a_n-2$ に入れても動かない値($1=3\cdot 1-2$)で、数列の不動点だ。不動点からのずれだけを見れば、$-2$ の効果が消えて純粋な $3$ 倍が残る。特性方程式はこの不動点を機械的に探す道具にすぎない。

「書き出す → 何かを引いてそろえてみる」は、特性方程式を忘れたときの復元手段にも、答えの検算にもなる。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=a_n+(2n-1)$ は、前の項に「$n$ で変わる量」を足していく形だ。これは階差数列の型だ。

差を積み上げれば任意の項に着く。$n\geqq 2$ で

$$a_n=a_1+\sum _{k=1}^{n-1}(2k-1)$$

足すのは奇数 $1,3,5,\dots$ だ。奇数の和は平方数になるから、$\Sigma$ の計算は軽い。上端が $n-1$ であることと、最後の $n=1$ の確認だけ丁寧に。

① 階差を確かめる。 $a_{n+1}-a_n=2n-1$。

② 和で一般項を出す($n\geqq 2$)。 階差 $2k-1$ は奇数。$n-1$ 個の奇数の和は $(n-1{)}^2$。

$$a_n=2+\sum _{k=1}^{n-1}(2k-1)=2+(n-1{)}^2$$

③ 展開して整理する。

$$a_n=2+(n^2-2n+1)=n^2-2n+3$$

④ $n=1$ を確認する。 $a_1=1-2+3=2$ で一致。

$$a_n=n^2-2n+3$$

まとめ:階差が奇数 $2k-1$ なら、和が平方数 $(n-1{)}^2$ になって計算が楽。$\Sigma$ 公式で地道に出しても同じだが、奇数の和 = 平方 を知っていると速い。

発展。 階差が $n$ の $1$ 次式なら、一般項は $n$ の $2$ 次式になる。差をとると次数が $1$ 下がる(逆に積むと $1$ 上がる)という、微分・積分の関係の離散版だ。階差が $2$ 次なら一般項は $3$ 次、と次数の見積もりが先にできる。

逆向きの目も役立つ。「一般項が $2$ 次式の数列」を見たら、階差は必ず等差数列になっている。数列の型あては、階差を $1$ 回とってみるのが最初の診察になる。

別解

答え $n^2-2n+3$ は、形を変えると意味が読める。

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

書き出して確かめると $a_1=0+2=2$、$a_2=1+2=3$、$a_3=4+2=6$、$a_4=9+2=11$ となり、逐次計算($2,3,6,11,18$)と一致する。

この形から分かること: スタートの $2$ に、奇数 $1,3,5,\dots$ を $n-1$ 個積むと、奇数の和の分 $=(n-1{)}^2$ だけ増える。「初項 $+$ 奇数の和 $=$ 初項 $+$ 平方数」という問題の構造が、式の見た目にそのまま残っている。

平方完成した形で答えを持っておくと、検算($n$ に小さい値を代入)も速いし、展開ミスがあれば $(n-1{)}^2+2$ との照合ですぐ気づける。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=2a_n+3^n$ は、邪魔者が定数でなく $3^n$ と、$n$ とともに育つ型だ。定数の特性方程式はそのままでは使えない。

こういうときは、解の形を先読みする。$2$ 倍する部分からは $2^n$ の系統、$3^n$ を足す部分からは $3^n$ の系統が育つはず。そこで

$$a_n=A\cdot 2^n+B\cdot 3^n$$

の形を予想し、$B$(特殊解の係数)を漸化式に合うように、$A$ を初項に合うように決める。「型を予想して係数を決める」二段構えである。

① 解の形を予想して代入する。 $a_n=A\cdot 2^n+B\cdot 3^n$ とおき、漸化式 $a_{n+1}=2a_n+3^n$ に入れる。

$$A\cdot 2^{n+1}+B\cdot 3^{n+1}=2(A\cdot 2^n+B\cdot 3^n)+3^n$$

② $3^n$ の係数を比べる。 $2^n$ の項は両辺で自動的に一致するので、$3^n$ の項だけ見る。左辺 $3B\cdot 3^n$、右辺 $(2B+1)3^n$。

$$3B=2B+1\Rightarrow B=1$$

③ 初項で $A$ を決める。 $a_1=1$。$a_n=A\cdot 2^n+3^n$ に $n=1$ を入れる。

$$2A+3=1\Rightarrow A=-1$$

④ 一般項を書く。

$$a_n=-2^n+3^n=3^n-2^n$$

まとめ:$p{a}_n+q^n$ 型は「$a_n=A{p}^n+B{q}^n$ とおいて係数決定」が速い。$q^n$ の項から $B$ が、初項から $A$ が決まる。($3^{n+1}$ で割って階差型にする別解もある。)

発展。 答え $3^n-2^n$ の中で、$n$ が大きくなると勝つのは $3^n$。「足される $3^n$」が「$2$ 倍の成長」を追い越す。$2$ つの増え方の競争が答えの $2$ 項にそのまま表れている。

もし係数と底が同じ($a_{n+1}=3a_n+3^n$)だったら、予想 $B\cdot 3^n$ は左右で打ち消されて決められない。そのときは $Bn\cdot 3^n$ と $n$ を掛けた形に格上げする(共鳴と呼ばれる現象)。「予想が失敗したら $n$ 倍して再挑戦」というのが、型の予想ルートの、もう一歩先の作法だ。

別解

邪魔者 $3^n$ を「割り算」で退治する道もある。両辺を $3^{n+1}$ で割る。

$$\frac{a_{n+1}}{3^{n+1}}=\frac{2}{3}\cdot \frac{a_n}{3^n}+\frac{1}{3}$$

$b_n=\frac{a_n}{3^n}$ とおくと $b_{n+1}=\frac{2}{3}{b}_n+\frac{1}{3}$ となり、見慣れた「定数を足す型」になった。特性方程式 $\beta =\frac{2}{3}\beta +\frac{1}{3}$ から $\beta =1$。$b_1=\frac{1}{3}$ だから

$$b_n-1={\left(\frac{2}{3}\right)}^{n-1}(b_1-1)=-{\left(\frac{2}{3}\right)}^n\text{つまり}{b}_n=1-{\left(\frac{2}{3}\right)}^n$$

$a_n=3^n{b}_n=3^n-2^n$。予想ルートと同じ答えだ。「増えていく余分な項は、その増え方($3^n$)で全体を割って大きさをそろえる」のは、指数型の漸化式に広く使える正規化の発想である。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=2a_n+n$ は、足される邪魔者が $n$($1$ 次式)の型だ。

定数なら「定数の不動点」を引けばよかった。$1$ 次式なら、引くべきものも $1$ 次式。特殊解 $pn+q$ を探す。$a_n=pn+q$ が漸化式をずっと満たすように $p,q$ を決めると、そこからのずれが純粋な等比数列になる。

$p(n+1)+q=2(pn+q)+n$ を $n$ について整理し、係数比較で $p,q$ を決める。「邪魔者と同じ形の解を仕込む」のがこの型の解き方だ。

① 1次式の特殊解を求める。 $a_n=pn+q$ が漸化式を満たすとして代入。

$$p(n+1)+q=2(pn+q)+n$$

左辺 $pn+p+q$、右辺 $(2p+1)n+2q$。係数を比べる。

$$p=2p+1\Rightarrow p=-1,p+q=2q\Rightarrow q=p=-1$$

特殊解は $-n-1$。

② 残りを等比数列にする。 $a_n=A\cdot 2^n+(-n-1)$ とおく(等比部分 + 特殊解)。$a_1=1$ を代入。

$$2A-1-1=1\Rightarrow 2A=3\Rightarrow A=\frac{3}{2}$$

③ 一般項を書く。 $\frac{3}{2}\cdot 2^n=3\cdot 2^{n-1}$。

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

まとめ:右辺に $n$ の1次式があるときは、「答えにも1次式が混じる」と読んで特殊解 $pn+q$ を先に決める。残りは等比数列。指数型($q^n$)のときと同じ「特殊解 + 等比」の発想だ。

発展。 特殊解ルート(本解)と階差ルート(別解)は、同じ結果に別の道筋でたどり着く方法だ。特殊解 $-n-1$ を先に見抜けるなら最短、思いつかなければ差をとって機械的に次数を下げる。試験では「予想できたら特殊解、できなければ階差」と使い分ければよい。

この構造(一般解 $=$ 等比の部分 $+$ 邪魔者と同型の特殊解)は、大学で学ぶ微分方程式とまったく同じ設計になっている。漸化式は微分方程式の離散版であり、数Bのこの単元はその基礎にもなる。

別解

邪魔者の $n$ を、差をとって消す方法もある。となり合う $2$ つの漸化式を並べて引く。

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

差 $c_n=a_{n+1}-a_n$ をとると、$n$ と $n+1$ の差は $1$ だから

$$c_{n+1}=2c_n+1$$

$1$ 次式の邪魔者がただの定数 $1$ に格下げされた。あとは基本の特性方程式型だ。$c_1=a_2-a_1=3-1=2$ で、$c_n+1$ が公比 $2$ の等比になるから $c_n=3\cdot 2^{n-1}-1$。

最後に差を積み上げて復元する。

$$a_n=a_1+\sum _{k=1}^{n-1}{c}_k=1+3(2^{n-1}-1)-(n-1)=3\cdot 2^{n-1}-n-1$$

「差をとるたびに邪魔者の次数が $1$ 下がる」ので、$n^2$ が足される型なら $2$ 回差をとればよい。特殊解の形を予想しにくいときの、確実な迂回路である。

方針

解答

⓪ 発想(どう考え始めるか) $a$ と $b$ が互いを参照し合っていて、単独では解けない。ならば、組み合わせて $1$ 本の数列を作る。

$2$ つの式をよく見ると、係数が対称($a$ の式は $2,1$、$b$ の式は $1,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$ 式を足す。

$$a_{n+1}+b_{n+1}=3a_n+3b_n=3(a_n+b_n)$$

公比 $3$ の等比数列。初項 $a_1+b_1=1$。よって $a_n+b_n=3^{n-1}$。

② 差の漸化式を作る。 $2$ 式を引く。

$$a_{n+1}-b_{n+1}=a_n-b_n$$

一定(公比 $1$)。初項 $a_1-b_1=1$。よって $a_n-b_n=1$。

③ $a_n$、$b_n$ を復元する。 和と差から

$$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_n=\frac{和+差}{2}$ で復元する。

発展。 和と差がうまくいったのは係数が対称だったから。対称でない連立漸化式では、$a_n+\alpha b_n$ が等比になるような $\alpha$ を探す(今回の和と差は $\alpha =1,-1$ の場合にあたる)。この $\alpha$ 探しを機械化したものが、大学で学ぶ行列の固有値・固有ベクトルだ。

「$2$ 本の絡んだ数列を、独立に育つ $2$ 方向(今回は和と差)に組み替える」のは、座標軸を取り替えて問題を単純化する線形代数の中心思想で、この問題がその最初の体験になる。

別解

「和と差を作る」と言われても唐突に感じるなら、先に数列を書き出してみるとよい。

$$a:1,2,5,14,\dots b:0,1,4,13,\dots$$

$2$ つの列を見比べると、気づくことが $2$ つある。

• 和 $a_n+b_n$: $1,3,9,27$ で、$3$ のべきだ
• 差 $a_n-b_n$: $1,1,1,1$ で、ずっと $1$ のまま

つまり $a_n+b_n=3^{n-1}$、$a_n-b_n=1$。この $2$ 本を連立して

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

実験が先、証明が後である。見つけた法則は和の漸化式($3$ 倍)と差の漸化式(不変)を作れば正当化できる。「$2$ 本の数列を見たら、まず和と差を計算してみる」を実験の習慣にしておくと、この型は怖くない。

方針

解答

⓪ 発想(どう考え始めるか) $a_{n+1}=\frac{a_n}{a_n+2}$ は、分数の形のままでは等差・等比のどの型にも見えない。

分数型の定跡は逆数をとること。分子が $a_n$ 単独(定数項なし)のときは特に役に立つ。

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

$b_n=\frac{1}{a_n}$ とおけば $b_{n+1}=2b_n+1$ となり、見慣れた特性方程式型に変わる。「扱いにくい形は、変換して既知の型に持ち込む」の代表例だ。

① 両辺の逆数をとる。

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

② 置きかえる。 $b_n=\frac{1}{a_n}$ とおくと

$$b_{n+1}=2b_n+1$$

これは特性方程式型。初項 $b_1=\frac{1}{a_1}=1$。

③ 特性方程式で解く。 $\alpha =2\alpha +1$ より $\alpha =-1$。$b_{n+1}+1=2(b_n+1)$。$b_n+1$ は初項 $2$、公比 $2$。

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

④ $a_n$ に戻す。 $a_n=\frac{1}{b_n}$。

$$a_n=\frac{1}{2^n-1}$$

まとめ:分数型は「逆数をとる」が最初の一手。$\frac{1}{a_{n+1}}$ を計算すると $b_n=\frac{1}{a_n}$ のやさしい漸化式になる。あとは特性方程式型として処理し、最後に逆数で $a_n$ に戻す。

発展。 分母の列 $1,3,7,15,\dots$($2^n-1$)はメルセンヌ数と呼ばれ、素数研究(巨大素数の探索は今もこの形で行われている)やハノイの塔の最少手数として、あちこちに現れる。

分子にも定数が付く一般の分数型 $a_{n+1}=\frac{p{a}_n+q}{r{a}_n+s}$ では、単純な逆数では割れない。そこでは不動点 $\alpha$ を求めて $\frac{1}{a_n-\alpha }$ や $\frac{a_n-\alpha }{a_n-\beta }$ を新数列にとる。「変換して既知の型へ」という今回の考え方が、そのまま発展した形で使われる。

別解

「逆数をとれ」の一言がなぜ出てくるのか。まず数列を分数のまま書き出してみる。

$$a_1=1,a_2=\frac{1}{3},a_3=\frac{1/3}{1/3+2}=\frac{1}{7},a_4=\frac{1}{15},\dots$$

分子はずっと $1$、分母は $1,3,7,15$。この分母の列は $1$ 足すと $2,4,8,16$ と倍々になる。つまり分母は $2^n-1$ で、

$$a_n=\frac{1}{2^n-1}$$

と予想できる。「分子が $1$ のまま、分母だけが規則的に育つ」ことに気づくと、逆数に変換しようと思える。分母 $=\frac{1}{a_n}$ を中心に考えれば、それは $b_{n+1}=2b_n+1$ という素直な数列(だから $+1$ で倍々になった)。実験で見えた法則を、変換によって証明できる。

方針

解答

⓪ 発想(どう考え始めるか) 「すべての自然数 $n$ で成り立つ」という無限個の主張を、有限の手続きで証明したい。そこで数学的帰納法を使う。

部品は $2$ つ。(I) 最初の $1$ 枚($n=1$)が成り立つこと。(II) $n=k$ で成り立つと仮定すれば $n=k+1$ でも成り立つこと。

この $2$ つが揃うと、$1\to 2\to 3\to \cdots$ とドミノ式にすべての $n$ へ伝わる。等式の帰納法では、(II)は「仮定の式の両辺に次の項 $(k+1{)}^2$ を足して、$k+1$ 版の右辺になるか」を確かめる計算になる。

(I) $n=1$ のとき。 左辺 $=1$、右辺 $=\frac{1\cdot 2\cdot 3}{6}=1$。成り立つ。

(II) $n=k$ を仮定する。 $1^2+\cdots +k^2=\frac{k(k+1)(2k+1)}{6}$ とする。両辺に次の項 $(k+1{)}^2$ を足す。

$$1^2+\cdots +k^2+(k+1{)}^2=\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2$$

右辺を $(k+1)$ でくくる。

$$=(k+1)\{\frac{k(2k+1)}{6}+(k+1)\}=(k+1)\cdot \frac{k(2k+1)+6(k+1)}{6}$$

中カッコの分子を整理する。$k(2k+1)+6(k+1)=2k^2+7k+6=(k+2)(2k+3)$。

$$=\frac{(k+1)(k+2)(2k+3)}{6}$$

これは $n=k+1$ の右辺 $\frac{(k+1)\{(k+1)+1\}\{2(k+1)+1\}}{6}$ に一致。

結論。 (I)(II) より、すべての自然数 $n$ で成り立つ。

まとめ:等式の帰納法は「仮定の右辺 + 次の項」を計算し、$k+1$ の右辺に一致させるのがヤマ。$(k+1)$ でくくり、残りの分子を因数分解 $(k+2)(2k+3)$ できるかで決まる。

発展。 (II)の計算の芯は $\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2$ で $(k+1)$ をくくること。展開してから因数分解し直すのではなく、共通因数を先にくくると計算量が数分の一になる。目標の式 $\frac{(k+1)(k+2)(2k+3)}{6}$ を横に書いておき、そこへ向けて式を整える意識が役に立つ。

帰納法が証明するのは等式だけではなく、不等式・倍数性・図形の性質なども、「$n$ で成り立てば $n+1$ でも」の橋さえ架かれば証明できる。この単元の後半で、その橋の架け方のバリエーションを学ぶ。

別解

帰納法は「与えられた式が正しいことの確認」だが、そもそもこの公式を自力で作り出す方法も知っておく価値がある。$3$ 乗の差を並べて足す。恒等式 $(k+1{)}^3-k^3=3k^2+3k+1$ を $k=1$ から $n$ まで足すと、左辺は途中が打ち消し合って

$$(n+1{)}^3-1=3\sum _{k=1}^n{k}^2+3\sum _{k=1}^{n}k+n$$

$\sum k=\frac{n(n+1)}{2}$ は既知だから、$\sum k^2$ について解けば

$$\sum _{k=1}^n{k}^2=\frac{1}{3}\left\{(n+1{)}^3-1-\frac{3n(n+1)}{2}-n\right\}=\frac{n(n+1)(2n+1)}{6}$$

公式そのものが導出できた。帰納法は「答えを知ってから確かめる」道具、望遠鏡和は「答えを知らずに作る」道具。$2$ つセットで持つと、$\sum k^3$ でも($4$ 乗の差から)同じように公式を自作できる。

方針

解答

⓪ 発想(どう考え始めるか) 不等式の帰納法で、まず確かめるのは出発点。$n=1$ では $2>2$ が偽、$n=2$ でも $4>4$ が偽なので、主張は $n\geqq 3$ から。だから (I) は $n=3$($8>6$)で確認する。

(II) では $2^{k+1}=2\cdot 2^k$ と分解して仮定 $2^k>2k$ を使う。

$$2^{k+1}=2\cdot 2^k>2\cdot 2k=4k$$

あとは $4k\geqq 2(k+1)$、つまり $2k\geqq k+1$ を言えばよい。ここで $k\geqq 3$ という前提条件を使う。不等式の帰納法は「仮定でジャンプ → 残りの差は $k$ の範囲で埋める」の二段跳びだ。

(I) $n=3$ のとき。 左辺 $2^3=8$、右辺 $2\cdot 3=6$。$8>6$ で成り立つ。

(II) $n=k$($k\geqq 3$)を仮定する。 $2^k>2k$ とする。$n=k+1$ を調べる。

$$2^{k+1}=2\cdot 2^k>2\cdot 2k=4k$$

(ここで仮定 $2^k>2k$ を使った。)あとは $4k$ が $2(k+1)$ より大きいことを示せばよい。

$$4k-2(k+1)=2k-2=2(k-1)>0(k\geqq 3\text{ より})$$

よって $4k>2(k+1)$。したがって

$$2^{k+1}>4k>2(k+1)$$

となり、$n=k+1$ でも成り立つ。

結論。 (I)(II) より、$n\geqq 3$ のすべての自然数で $2^n>2n$。

まとめ:不等式の帰納法は「$2^{k+1}=2\cdot 2^k$ に仮定を使って評価を下げ、さらに条件で押し切る」。等号でつなぐ等式とちがい、不等号を $2$ 段($>4k>2(k+1)$)つなぐのがコツだ。

発展。 $2^n$ と $2n$ の比較は指数と $1$ 次式の比較だ。出だしこそ競るが、指数は倍々で伸びるので必ず突き放す。実は $2^n>n^2$($n\geqq 5$)、$2^n>n^{10}$(十分大きな $n$)も成り立ち、指数関数はどんな多項式よりも最終的に大きくなる。この事実は数IIIの極限($\frac{n^k}{2^n}\to 0$)で定理として整備される。

「小さい $n$ で反例、大きい $n$ で成立」という主張の証明には、出発点つき帰納法がぴったりはまる。出発点を探す作業($n=1,2$ を実際に試す)自体が、問題の構造の理解になっている。

別解

帰納法を使わず、$2^n$ を二項定理で下から見積もる直接証明もできる。$2^n=(1+1{)}^n$ を展開すると、$n\geqq 2$ では最初の $3$ 項だけでも

$$2^n=\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\cdots \geqq 1+n+\frac{n(n-1)}{2}$$

これが $2n$ を超える条件を整理すると

$$1+n+\frac{n(n-1)}{2}>2n⟺n^2-3n+2>0⟺(n-1)(n-2)>0$$

$n\geqq 3$ なら両因数が正で成立。証明終わり。

境界の様子も因数分解から分かる。$n=2$ では $(n-1)(n-2)=0$ で、ちょうど等号($4=4$)になる。主張が $n\geqq 3$ から始まる理由が式に現れている。指数の不等式は「二項展開の頭数項で押さえる」のも、帰納法と並ぶもうひとつの標準的な方法だ。

方針

解答

⓪ 発想(どう考え始めるか) 与えられたのは項と和の混ざった式 $S_n=2a_n-n$。このままではどちらも分からない。

橋渡しは $a_n=S_n-S_{n-1}$($n\geqq 2$)。$S_n=2a_n-n$ と $S_{n-1}=2a_{n-1}-(n-1)$ を辺々引くと、$S$ が消えて

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

$a_n$ だけの漸化式に変わる。初項は $S_1=a_1$ から $a_1=2a_1-1$、つまり $a_1=1$。「$S$ 入りの式は、$1$ つ前と引き算して $S$ を消す」が定跡だ。

① 初項を求める。 $S_1=a_1$ なので $a_1=2a_1-1$、よって $a_1=1$。

② 漸化式を作る($n\geqq 2$)。 $a_n=S_n-S_{n-1}$ に代入。

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

③ 整理する。

$$a_n-2a_n=-2a_{n-1}-1\Rightarrow -a_n=-2a_{n-1}-1\Rightarrow a_n=2a_{n-1}+1$$

④ 特性方程式型を解く。 $\alpha =2\alpha +1$ より $\alpha =-1$。$a_n+1=2(a_{n-1}+1)$。初項 $a_1+1=2$。

$$a_n+1=2\cdot 2^{n-1}=2^n\Rightarrow a_n=2^n-1$$

まとめ:$S_n$ の関係式は「$a_n=S_n-S_{n-1}$」で $a$ の漸化式に直す。ここでは特性方程式型 $a_n=2a_{n-1}+1$ が出た。初項 $a_1=S_1$ を別に求めるのを忘れずに。

発展。 答えの検算は条件式で。$a_n=2^n-1$ なら $S_n=(2+4+\cdots +2^n)-n=2^{n+1}-2-n$、一方 $2a_n-n=2^{n+1}-2-n$ で、確かに一致する。「$S$ と $a$ の関係式が条件の問題は、最後に条件式へ戻して確かめる」と安心だ。

$1,3,7,15,\dots$($2^n-1$)は、分数型の漸化式の分母にも、ハノイの塔にも現れた顔なじみ。同じ数列が違う問題の答えとして再登場するのは、背後の構造(倍々 $+1$)が同じだからだ。数列の学習が進むほど、こうした例が増えていく。

別解

条件式から具体の項を順に絞り出して、答えの形を先に見てしまう手がある。

• $n=1$: $S_1=a_1=2a_1-1$ より $a_1=1$
• $n=2$: $a_1+a_2=2a_2-2$ より $1=a_2-2$、$a_2=3$
• $n=3$: $1+3+a_3=2a_3-3$ より $a_3=7$
• $n=4$: 同様に $a_4=15$

$1,3,7,15$ のそれぞれに $1$ を足すと $2,4,8,16$。$1$ 足すと倍々だ。$a_n=2^n-1$ と予想できる。

この観察は漸化式 $a_n=2a_{n-1}+1$ を変形した $a_n+1=2(a_{n-1}+1)$ の姿そのもの。$\{a_n+1\}$ が公比 $2$ の等比数列(初項 $2$)だから $a_n+1=2^n$。予想 → 構造($+1$ で等比)の発見 → 証明、という流れは、特性方程式の答え($\alpha =-1$)を実験が先取りしている形だ。

方針

解答

⓪ 発想(どう考え始めるか) 「$5$ の倍数である」ことを全部の $n$ で示す。倍数性も帰納法で証明できる。

(I) $n=1$: $6^1-1=5$。確かに $5$ の倍数。(II) $n=k$ で $6^k-1=5m$($m$ は整数)と書けると仮定する。$6^{k+1}-1$ を、仮定が使える形(つまり $6^k-1$ が見える形)にわざと崩すのがいちばん大事なところだ。$6^{k+1}=6\cdot 6^k$ から

$$6^{k+1}-1=6(6^k-1)+5$$

と変形すれば、$6\cdot 5m+5=5(6m+1)$ で $5$ の倍数。「仮定のかたまりを作り出す変形」が倍数性の帰納法の要点である。

(I) $n=1$ のとき。 $6^1-1=5$ で、$5$ の倍数。成り立つ。

(II) $n=k$ を仮定する。 $6^k-1$ が $5$ の倍数、すなわち整数 $m$ で $6^k-1=5m$ と書けるとする。$n=k+1$ を調べる。

$$6^{k+1}-1=6\cdot 6^k-1=6(6^k-1)+5$$

(ここで $6\cdot 6^k=6(6^k-1)+6$ を使い、$-1$ と合わせて $+5$ にした。)仮定 $6^k-1=5m$ を代入する。

$$=6\cdot 5m+5=5(6m+1)$$

$6m+1$ は整数なので、$6^{k+1}-1$ は $5$ の倍数。

結論。 (I)(II) より、すべての自然数 $n$ で $6^n-1$ は $5$ の倍数。

まとめ:整除の帰納法は「$6^{k+1}-1$ を $6^k-1$ でくくり出す」変形が決め手だ。$6^{k+1}-1=6(6^k-1)+5$ とすれば、仮定($5$ の倍数)と残り($+5$)が両方 $5$ の倍数になる。

発展。 本解の変形 $6^{k+1}-1=6(6^k-1)+5$ は、「余りだけ見れば $6\equiv 1$ だから $6^n\equiv 1^n=1$」という合同式(数A)の考えを、帰納法の言葉で書いたものだ。合同式を学んだ人なら $6^n-1\equiv 0(\mathrm{mod}5)$ の $1$ 行で済む。同じ事実に、帰納法・因数分解・合同式の $3$ つの道がある。

「$a^n-b^n$ は $a-b$ の倍数」という一般形も、別解と同じ因数分解で証明できる。整数の倍数性の問題では、この恒等式が裏で使われていることが多い。

別解

帰納法を使わない短い証明が、因数分解でできる。等比数列の和の公式を因数分解の形で読むと

$$6^n-1=(6-1)(6^{n-1}+6^{n-2}+\cdots +6+1)=5\times (\text{整数})$$

カッコの中は $6$ のべきの和なので、明らかに整数だ。よって $6^n-1$ は $5$ の倍数。これで終わり。

$x^n-1=(x-1)(x^{n-1}+\cdots +1)$ という恒等式に $x=6$ を入れただけである。同じ理屈で「$7^n-1$ は $6$ の倍数」「$10^n-1$($99\cdots 9$)は $9$ の倍数」もすぐに出る。

直感的に言えば、$6$ 進法で $6^n-1$ は $55\cdots 5$($5$ が $n$ 個)となる。$10$ 進法の $99\cdots 9$ が $9$ の倍数であるのと同じことだ。帰納法はどんな場合にも使える方法、因数分解は特定の形に使える方法で、両方持っていると証明の選択肢が広がる。