三項間漸化式の特性方程式

$a_0=0$、$a_1=4$、$a_{n+2}=2a_{n+1}+3a_n$ で決まる数列の項を、順に計算する。
$$ \begin{aligned} a_2&=2a_1+3a_0=2\cdot4+3\cdot0=8,\\ a_3&=2a_2+3a_1=2\cdot8+3\cdot4=28,\\ a_4&=2a_3+3a_2=2\cdot28+3\cdot8=80,\\ a_5&=2a_4+3a_3=2\cdot80+3\cdot28=244. \end{aligned} $$
$3$ の冪 $1,3,9,27,81,243$ と見比べると、$a_n$ は $3^n$ より $1$ 小さいか $1$ 大きく、$a_n=3^n-(-1)^n$ ではないかと推測できる。

漸化式 $a_{n+2}=2a_{n+1}+3a_n$ で、初期値だけを変えた 3 つの数列を比べる。

1. $a_0=0$、$a_1=4$：$0,\ 4,\ 8,\ 28,\ 80,\ 244,\ \dots$
2. $a_0=0$、$a_1=5$：$0,\ 5,\ 10,\ 35,\ 100,\ 305,\ \dots$（$a_2=2\cdot5+3\cdot0=10$）
3. $a_0=1$、$a_1=4$：$1,\ 4,\ 11,\ 34,\ 101,\ 304,\ \dots$（$a_2=2\cdot4+3\cdot1=11$）
   1 と 2 は $a_0$ が同じでも $a_1$ が違い、$a_1$ から先の項はどれも違う。1 と 3 は $a_1$ が同じでも $a_0$ が違うので、$a_2$ から先も違ってくる。初期値を 2 つとも決めて、はじめて数列が 1 つに決まる。同じ初期値 $0,4$ から計算すれば、誰が計算しても 1 の数列になる。これが prop-cer-unique の内容である。

1. $a_{n+2}=2a_{n+1}+3a_n$：特性方程式は $t^2-2t-3=0$。$t^2-2t-3=(t-3)(t+1)$ なので、解は $3$ と $-1$（異なる 2 解）。
2. $a_{n+2}=4a_{n+1}-4a_n$：特性方程式は $t^2-4t+4=0$。$t^2-4t+4=(t-2)^2$ なので、解は $2$ だけ（重解）。
3. $a_{n+2}=a_{n+1}-a_n$：特性方程式は $t^2-t+1=0$。判別式は $(-1)^2-4\cdot1\cdot1=-3<0$ なので、解は虚数 $\dfrac{1\pm\sqrt3\,i}2$（異なる 2 解）。

漸化式 $a_{n+2}=2a_{n+1}+3a_n$（特性方程式の解は $3,-1$）で確かめる。

1. $a_n=3^n$：左辺 $3^{n+2}=9\cdot3^n$、右辺 $2\cdot3^{n+1}+3\cdot3^n=6\cdot3^n+3\cdot3^n=9\cdot3^n$。等しいので解である。
2. $a_n=(-1)^n$：左辺 $(-1)^{n+2}=(-1)^n$、右辺 $2(-1)^{n+1}+3(-1)^n=-2(-1)^n+3(-1)^n=(-1)^n$。等しいので解である。
3. $a_n=2^n$：左辺 $2^{n+2}=4\cdot2^n$、右辺 $2\cdot2^{n+1}+3\cdot2^n=7\cdot2^n$。等しくないので解ではない。実際 $2^2=4\ne2\cdot2+3=7$ で、$2$ は特性方程式の解でない。

ex-cer-first-terms の数列 $a_0=0$、$a_1=4$、$a_{n+2}=2a_{n+1}+3a_n$ について、$a_n=3^n-(-1)^n$ を示す。
$b_n:=3^n-(-1)^n$ とおく。ex-cer-geometric-check で $3^n$ と $(-1)^n$ は解だったので、prop-cer-superposition（$A=1$、$B=-1$）により $(b_n)$ も解である。さらに
$$ b_0=1-1=0=a_0,\qquad b_1=3-(-1)=4=a_1 $$
なので、prop-cer-unique によりすべての $n$ で $a_n=b_n=3^n-(-1)^n$ である。

$a_0=1$、$a_1=4$、$a_{n+2}=5a_{n+1}-6a_n$ とする。項は $1,4,14,46,146,454,\dots$ である（たとえば $a_2=5\cdot4-6\cdot1=14$、$a_3=5\cdot14-6\cdot4=46$）。特性方程式 $t^2-5t+6=(t-2)(t-3)=0$ の解は $2,3$ である。

• $a_{n+1}-2a_n$ を計算すると $4-2=2$、$14-8=6$、$46-28=18$、$146-92=54$。公比 $3$ の等比数列である。
• $a_{n+1}-3a_n$ を計算すると $4-3=1$、$14-12=2$、$46-42=4$、$146-138=8$。公比 $2$ の等比数列である。

$a_0=0$、$a_1=4$、$a_{n+2}=2a_{n+1}+3a_n$ では $\alpha=3$、$\beta=-1$ とおける。
$$ a_1-\beta a_0=4+0=4,\qquad a_1-\alpha a_0=4-0=4,\qquad \alpha-\beta=4 $$
なので、$a_n=\dfrac{4\cdot3^n-4\cdot(-1)^n}{4}=3^n-(-1)^n$ である。ex-cer-first-proof と同じ答えが、推測なしに出た。

ex-cer-rewrite-numbers の $a_0=1$、$a_1=4$、$a_{n+2}=5a_{n+1}-6a_n$ で $\alpha=3$、$\beta=2$ とおく。
$$ a_1-\beta a_0=4-2=2,\qquad a_1-\alpha a_0=4-3=1,\qquad \alpha-\beta=1 $$
なので $a_n=2\cdot3^n-2^n$ である。確かめ：$n=2$ で $18-4=14$、$n=3$ で $54-8=46$、$n=4$ で $162-16=146$ で、ex-cer-rewrite-numbers の値と一致する。

$a_0=0$、$a_1=1$、$a_{n+2}=a_{n+1}-a_n$ とする。順に計算すると
$$ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ \dots $$
となり、6 項ごとに同じ値がくり返す。特性方程式 $t^2-t+1=0$ の解は $\alpha=\dfrac{1+\sqrt3\,i}2$、$\beta=\dfrac{1-\sqrt3\,i}2$ で、$\alpha-\beta=\sqrt3\,i$ である。$a_0=0$、$a_1=1$ なので thm-cer-distinct の式は
$$ a_n=\frac{\alpha^n-\beta^n}{\sqrt3\,i} $$
となる。$\alpha=\cos\frac\pi3+i\sin\frac\pi3$、$\beta=\cos\frac\pi3-i\sin\frac\pi3$ と書けるので、de Moivre の定理（複素数の極形式）により $\alpha^n=\cos\frac{n\pi}3+i\sin\frac{n\pi}3$、$\beta^n=\cos\frac{n\pi}3-i\sin\frac{n\pi}3$ である。引き算すると $\alpha^n-\beta^n=2i\sin\frac{n\pi}3$ なので、
$$ a_n=\frac{2}{\sqrt3}\sin\frac{n\pi}3 $$
である。$n=1$ で $\frac2{\sqrt3}\cdot\frac{\sqrt3}2=1$、$n=4$ で $\frac2{\sqrt3}\cdot\bigl(-\frac{\sqrt3}2\bigr)=-1$ となり、上の値と一致する。

$a_0=1$、$a_1=4$、$a_{n+2}=4a_{n+1}-4a_n$ とする。特性方程式 $(t-2)^2=0$ の重解は $\alpha=2$ で、
$$ B=\frac{a_1-\alpha a_0}{\alpha}=\frac{4-2}{2}=1 $$
なので $a_n=(1+n)\,2^n$ である。順に計算した値 $a_2=4\cdot4-4\cdot1=12$、$a_3=4\cdot12-4\cdot4=32$、$a_4=4\cdot32-4\cdot12=80$ は、式の値 $3\cdot4=12$、$4\cdot8=32$、$5\cdot16=80$ と一致する。証明の段 4 の $d_n=a_n/2^n$ は $1,2,3,4,5,\dots$ である（図 2）。

$a_0=1$、$a_1=1$、$a_{n+2}=-2a_{n+1}-a_n$ とする。特性方程式 $t^2+2t+1=(t+1)^2=0$ の重解は $\alpha=-1$ で、
$$ B=\frac{a_1-\alpha a_0}{\alpha}=\frac{1+1}{-1}=-2 $$
なので $a_n=(1-2n)(-1)^n$ である。順に計算すると $a_2=-2\cdot1-1=-3$、$a_3=-2\cdot(-3)-1=5$、$a_4=-2\cdot5-(-3)=-7$ で、式の値 $(1-4)\cdot1=-3$、$(1-6)\cdot(-1)=5$、$(1-8)\cdot1=-7$ と一致する。

$a_0=1$、$a_1=4$、$a_{n+2}=4a_{n+1}-4a_n$ は、thm-cer-distinct の仮定のうち「特性方程式が異なる 2 解をもつ」だけを満たさない（重解 $2$）。このとき「解は特性方程式の解の冪の 1 次結合で書ける」という結論が破れる。使える冪は $2^n$ だけなので $a_n=A\cdot2^n$ としてみると、$a_0=1$ から $A=1$ となり、すると $a_1=2\ne4$ である。正しい一般項は ex-cer-double-1 の $(n+1)2^n$ で、欠けていたのは $n2^n$ の項である。

$a_0=a_1=1$、$a_{n+2}=a_{n+1}+(n+1)a_n$ は 3 つの項の間の 1 次の関係だが、「係数が定数」という仮定を満たさない。値は $1,1,2,4,10,26,76,232,\dots$ である（$a_2=1+1\cdot1=2$、$a_3=2+2\cdot1=4$、$a_4=4+3\cdot2=10$）。
この漸化式を満たす等比数列 $a_n=cr^n$（$c\ne0$）は存在しない。$r=0$ なら $a_1=a_2=0$ のはずだが、漸化式から $a_2=a_1+1\cdot a_0=c\ne0$ となり矛盾する。$r\ne0$ なら、漸化式を $cr^n$ で割ると $r^2=r+(n+1)$ がすべての $n$ で成り立つことになるが、$n=0$ では $r^2=r+1$、$n=1$ では $r^2=r+2$ で、両立しない。係数が変わると「特性方程式」が $n$ ごとに変わってしまい、1 つに決まらない。

$p=q=0$、すなわち $a_{n+2}=0$ とし、$a_0=5$、$a_1=7$ とする。数列は $5,7,0,0,0,\dots$ である。特性方程式 $t^2=0$ は重解 $0$ をもつが、$(A+Bn)\cdot0^n$（$0^0=1$ とする）は $n\ge1$ で $0$ なので、$a_1=7$ にならない。thm-cer-double の証明の段 3 で $\alpha^{n+1}$ で割る所が、$\alpha=0$ では使えない。$q\ne0$ の仮定はここで効いている。

数列 $\{u_n\}$ を $u_0=2$、$u_1=\frac52$、$u_{n+1}=u_n(u_{n-1}^2-2)-u_1$（$n=1,2,\dots$）で定める。正の整数 $n$ について
$$ [u_n]=2^{\frac{2^n-(-1)^n}3} $$
を示せ。ここで $[x]$ は $x$ 以下の最大の整数を表す。
出典：国際数学オリンピック（1976 年）第 6 問（Oly76）。和訳は本記事による。

$u_2=u_1(u_0^2-2)-u_1=\frac52\cdot2-\frac52=\frac52$、$u_3=u_2(u_1^2-2)-u_1=\frac52\cdot\frac{17}4-\frac52=\frac{85}8-\frac{20}8=\frac{65}8=8.125$ である。一方、指数 $\frac{2^n-(-1)^n}3$ は $n=1,2,3$ で $\frac{2+1}3=1$、$\frac{4-1}3=1$、$\frac{8+1}3=3$ なので、右辺は $2,2,8$ である。左辺 $[u_1]=[2.5]=2$、$[u_2]=2$、$[u_3]=8$ と一致する。さらに $u_3=8+\frac18=2^3+2^{-3}$ となっていることに注目する。