数列の一般項の推定と帰納法

$a_1=1$、$a_{n+1}=\dfrac{a_n}{1+a_n}$ とする。項を計算すると
$$ a_2=\frac{1}{1+1}=\frac12,\qquad a_3=\frac{1/2}{1+1/2}=\frac{1/2}{3/2}=\frac13,\qquad a_4=\frac{1/3}{1+1/3}=\frac{1/3}{4/3}=\frac14 $$
となる。$a_n=\dfrac1n$ と推定できる。
推定を帰納法で確かめる。$n=1$ では $a_1=1=\frac11$ である。$a_k=\frac1k$ と仮定すると
$$ a_{k+1}=\frac{1/k}{1+1/k}=\frac{1/k}{(k+1)/k}=\frac1{k+1} $$
である（分子と分母に $k$ を掛けた）。よってすべての $n\ge1$ で $a_n=\frac1n$ である。

数列 $\{a_n\}$ が $a_1=1$ と、すべての $n\ge1$ で
$$ a_1+a_2+\dots+a_n=n^2a_n $$
を満たすとする。$n=2$ では $1+a_2=4a_2$ から $a_2=\frac13$ である。$n=3$ では $1+\frac13+a_3=9a_3$ から $8a_3=\frac43$、$a_3=\frac16$ である。$n=4$ では $1+\frac13+\frac16+a_4=16a_4$ から $15a_4=\frac32$、$a_4=\frac1{10}$ である。
$1,\frac13,\frac16,\frac1{10}$ の分母 $1,3,6,10$ は $\frac{n(n+1)}2$（$1$ から $n$ までの和）なので、$a_n=\dfrac{2}{n(n+1)}$ と推定できる。この推定の証明には、1 つ前の項だけでなく、それまでのすべての項を使う（ex-ggt-sum-proof）。

円周上に $n$ 個の点をとり、すべての 2 点を線分（弦）で結ぶ。どの 3 本の弦も円の内部の同じ 1 点を通らないように点を置くとき、円の内部がいくつの部分（領域）に分かれるかを数える。点が $1,2,3,4,5$ 個のとき、領域は
$$ 1,\ 2,\ 4,\ 8,\ 16 $$
個である（図1）。$2^{n-1}$ と推定したくなるが、$6$ 個の点では $32$ ではなく $31$ 個になる。

1. 例 1 は $m=1$、$F_n(a_n)=\frac{a_n}{1+a_n}$ で、1 つ前の項だけで決まる。
2. $a_1=1$、$a_{n+1}=a_n+2n+1$ は $m=1$、$F_n(a_n)=a_n+2n+1$ で、規則が $n$ にもよる。項は $1,4,9,16,25$ である。
3. 例 2 は、$n+1$ の式 $a_1+\dots+a_{n+1}=(n+1)^2a_{n+1}$ から $a_{n+1}$ を解くと $\bigl((n+1)^2-1\bigr)a_{n+1}=a_1+\dots+a_n$、すなわち
   $$ a_{n+1}=\frac{a_1+a_2+\dots+a_n}{n(n+2)} $$
   で、それまでのすべての項を使う（$(n+1)^2-1=n(n+2)$ を使った）。
4. $a_1=1$、$a_2=2$、$a_{n+2}=2a_{n+1}-a_n+2$ は $m=2$ で、2 つ前までの項を使う。項は $1,2,5,10,17$ である。

1. $a_1=1$、$a_{n+1}=a_n+2n+1$：項 $1,4,9,16,25$ から $g(n)=n^2$ と推定する。$g(1)=1$ で、$g(n)+2n+1=n^2+2n+1=(n+1)^2=g(n+1)$ なので、thm-ggt-unique から $a_n=n^2$ である。
2. $a_1=1$、$a_2=2$、$a_{n+2}=2a_{n+1}-a_n+2$：項 $1,2,5,10,17$ は平方数に $1$ を足したもの $0+1,\ 1+1,\ 4+1,\ 9+1,\ 16+1$ なので、$g(n)=(n-1)^2+1$ と推定する。出発点は $g(1)=1$、$g(2)=2$ である。進み方は、$n\ge1$ について
   $$ 2g(n+1)-g(n)+2=2(n^2+1)-\bigl((n-1)^2+1\bigr)+2=n^2+2n+2=g(n+2) $$
   である（$g(n+2)=(n+1)^2+1=n^2+2n+2$）。よって $a_n=(n-1)^2+1$ である。

例 2 の漸化式 $a_{n+1}=\dfrac{a_1+\dots+a_n}{n(n+2)}$（$m=1$、$a_1=1$）に対して、$g(n)=\dfrac2{n(n+1)}$ が（進み方）を満たすことを確かめる。
段 1（和の計算）。$\dfrac2{k(k+1)}=2\Bigl(\dfrac1k-\dfrac1{k+1}\Bigr)$ なので、$k=1$ から $n$ まで足すと中の項が打ち消し合い
$$ g(1)+g(2)+\dots+g(n)=2\Bigl(1-\frac1{n+1}\Bigr)=\frac{2n}{n+1} $$
である（この和の求め方は 数列の和と差分 で扱う）。
段 2（進み方）。段 1 から
$$ F_n\bigl(g(1),\dots,g(n)\bigr)=\frac{2n/(n+1)}{n(n+2)}=\frac2{(n+1)(n+2)}=g(n+1) $$
である。$g(1)=\frac2{2}=1=a_1$ なので、thm-ggt-unique から $a_n=\dfrac2{n(n+1)}$ である。このとき和は $a_1+\dots+a_n=\frac{2n}{n+1}$ で、実際 $n^2a_n=\frac{2n}{n+1}$ と一致する。

1. $1,2,3$ の次：$g(n)=n+(n-1)(n-2)(n-3)$ は $n=1,2,3$ で $1,2,3$ だが、$g(4)=4+3\cdot2\cdot1=10$、$g(5)=5+4\cdot3\cdot2=29$ である。「$1,2,3$ の次は $4$」は、$g(n)=n$ という推定を選んだときの答えにすぎない。
2. $1,2,4,8$ の次：証明の手順どおりに作る。$P_1=1$。$P_2=1+t(n-1)$ で $P_2(2)=1+t=2$ から $t=1$、$P_2=n$。$P_3=n+t(n-1)(n-2)$ で $P_3(3)=3+2t=4$ から $t=\frac12$。$P_3(4)=4+\frac12\cdot3\cdot2=7$ なので、$P_4=P_3+t(n-1)(n-2)(n-3)$ で $7+6t=8$ から $t=\frac16$ である。できた 3 次式
   $$ P_4(n)=n+\frac{(n-1)(n-2)}2+\frac{(n-1)(n-2)(n-3)}6 $$
   は $n=1,2,3,4$ で $1,2,4,8$ となり、$P_4(5)=5+6+4=15$ である。$1,2,4,8$ の次は $16$（$2^{n-1}$）とも $15$（この 3 次式）とも言える。

1. $S_n=1^2+2^2+\dots+n^2$ は $n$ の 3 次式で表せることが分かっている（数列の和と差分）。$S_1,S_2,S_3,S_4=1,5,14,30$ と、$\frac{n(n+1)(2n+1)}6$ の $n=1,2,3,4$ での値 $\frac{1\cdot2\cdot3}6=1$、$\frac{2\cdot3\cdot5}6=5$、$\frac{3\cdot4\cdot7}6=14$、$\frac{4\cdot5\cdot9}6=30$ が一致するので、prop-ggt-poly-unique（$d=3$）により、すべての $n$ で $S_n=\frac{n(n+1)(2n+1)}6$ である。
2. ex-ggt-interpolation の 2 の 3 次式 $P_4$ と $2^{n-1}$ は、$n=1,2,3,4$ で一致するが $n=5$ で異なる。$2^{n-1}$ は 3 次以下の多項式ではない。もしそうなら、$2^{n-1}$ と $P_4$ はどちらも 3 次以下の多項式で、$n=1,2,3,4$ で一致するので、prop-ggt-poly-unique（$d=3$）によりすべての $n$ で一致するはずだが、$n=5$ で $2^4=16\ne15=P_4(5)$ となって矛盾する。したがって、4 つの値が一致していても prop-ggt-poly-unique は使えない（3 次以下の多項式どうしでないと結論は出ない）。

1. 値を計算すると、$R(1),\dots,R(8)$ は
   $$ 1,\ 2,\ 4,\ 8,\ 16,\ 31,\ 57,\ 99 $$
   である。たとえば $R(6)=\binom64+\binom62+1=15+15+1=31$、$R(7)=35+21+1=57$ である。
2. Pascal の三角形の関係 $\binom n4=\binom{n-1}4+\binom{n-1}3$、$\binom n2=\binom{n-1}2+\binom{n-1}1$ と $1=\binom{n-1}0$ を使うと
   $$ R(n)=\binom{n-1}0+\binom{n-1}1+\binom{n-1}2+\binom{n-1}3+\binom{n-1}4 $$
   と書き直せる。一方、二項定理から $2^{n-1}=\binom{n-1}0+\binom{n-1}1+\dots+\binom{n-1}{n-1}$ である（二項定理と組合せの恒等式）。$n\le5$ では $n-1\le4$ なので、2 つの和は同じ項からなり、$R(n)=2^{n-1}$ である。$n=6$ では $2^5$ の和にある最後の項 $\binom55=1$ が $R(6)$ にはないので、$R(6)=32-1=31$ である（図2）。

$a_1=3$、$a_{n+1}=2a_n-n$ とする。項は $3,5,8,13,22,39,\dots$ で、形が見えにくい。隣り合う項の差（階差）をとると $2,3,5,9,17$、さらにその差をとると $1,2,4,8$ で、$2$ の冪が現れる。そこで $a_n$ から $2^{n-1}$ を引いてみると、$3-1,\ 5-2,\ 8-4,\ 13-8,\ 22-16$ はそれぞれ $2,3,4,5,6$ となり、$n+1$ である。候補は $g(n)=2^{n-1}+n+1$ である。
確かめる。$g(1)=1+1+1=3=a_1$ である。進み方は
$$ 2g(n)-n=2\bigl(2^{n-1}+n+1\bigr)-n=2^n+n+2=g(n+1) $$
である（$g(n+1)=2^{n}+(n+1)+1$）。thm-ggt-unique から $a_n=2^{n-1}+n+1$ である。差をとる方法は 数列の和と差分 で詳しく扱う。

1. 例 2 の $1,\frac13,\frac16,\frac1{10}$ は、分子を $2$ にそろえると $\frac22,\frac26,\frac2{12},\frac2{20}$ となる。分母 $2,6,12,20$ は $1\cdot2,\ 2\cdot3,\ 3\cdot4,\ 4\cdot5$ なので、$\frac2{n(n+1)}$ が見える。
2. 同じ数列で、隣り合う項の比 $\frac{a_{n}}{a_{n-1}}$ をとると $\frac13,\ \frac12,\ \frac35$ で、$\frac12=\frac24$ と書き直して $\frac13,\ \frac24,\ \frac35$ と並べると $\frac{n-1}{n+1}$（$n=2,3,4$）と読める。実際、例 2 の条件で $n$ の式から $n-1$ の式を引くと $a_n=n^2a_n-(n-1)^2a_{n-1}$、すなわち $(n^2-1)a_n=(n-1)^2a_{n-1}$ で、$n\ge2$ で両辺を $(n-1)(n+1)$ で割ると $a_n=\frac{n-1}{n+1}a_{n-1}$ となる。この 1 つ前の項だけの漸化式からも、thm-ggt-unique で同じ結論が得られる。

例 1 の $1,\frac12,\frac13,\frac14$ は、逆数をとると $1,2,3,4$ になる。実際、漸化式の逆数をとると $\frac1{a_{n+1}}=\frac1{a_n}+1$ で、逆数は公差 $1$ の等差数列である。このように、うまく変換すると推定を経ずに一般項が求まることがある。分数の形の漸化式を変換で解く方法は 分数型の漸化式と1次分数変換 で扱う。

$f(n)=n^2+n+41$ は、$n=0,1,2,\dots,39$ の 40 個の値 $41,43,47,53,\dots,1601$ がすべて素数である。しかし $n=40$ では $f(40)=1600+40+41=1681=41^2$ で素数ではない。$n=41$ でも $f(41)=41\cdot43$ である。この例は Euler による（Cri24 §6.1.2）。
満たす性質：最初の 40 個で「素数である」が成り立つ。満たさない性質：$n$ から $n+1$ へ性質が受け継がれることの証明（進み方）。破る主張：「数項で成り立てば、すべての $n$ で成り立つ」。

例 1 の漸化式 $a_{n+1}=\frac{a_n}{1+a_n}$（$a_1=1$）に対して、$h(n)=\frac1{n+1}$ も進み方を満たす：$\frac{h(n)}{1+h(n)}=\frac{1/(n+1)}{(n+2)/(n+1)}=\frac1{n+2}=h(n+1)$。しかし $h(1)=\frac12\ne a_1$ で、$h(n)$ は $a_n=\frac1n$ と一致しない（$h$ は $a_1=\frac12$ から始めた数列である）。
満たす性質：thm-ggt-unique の（進み方）。満たさない性質：（出発点）。破る主張：thm-ggt-unique の結論 $a_n=h(n)$。崩れるのは証明の段 1 である。

$a_1=1$、$a_2=2$、$a_{n+2}=2a_{n+1}-a_n+2$（$m=2$）に対して、$h(n)=n^2$ も進み方を満たす：$2(n+1)^2-n^2+2=n^2+4n+4=(n+2)^2$。$h(1)=1=a_1$ も合っている。しかし $h(2)=4\ne a_2=2$ で、実際の $a_n=(n-1)^2+1$（ex-ggt-apply の 2）とは $n\ge2$ で一致しない。
満たす性質：（進み方）と、1 項目の一致。満たさない性質：2 項目の一致。破る主張：thm-ggt-unique の結論。漸化式が 2 つ前までの項を使うなら、出発点も 2 つ確かめる必要がある（数学的帰納法と整列性 の、出発点が足りない強い帰納法の反例と同じ）。