2次モニック多項式の剰余類と3項間漸化式
$ \boxed{ 問題:なぜ漸化式 a_{n+1} = p a_{n} + q a_{n-1} を解くときに特性方程式 x^2 = p x + q を解くのか? }
答え:第$ N 項$ a_{N} を漸化式$ a_{n+1} = p a_{n} + q a_{n-1} を使って第$ N-1 ,$ N-2 ,...項と「次数を減らす」操作と、$ N 次式$ x^{N} を特性方程式$ x^2 = p x + q を使って次数を減らす操作に対応関係があるから。
例題:漸化式$ a_{n+1} = a_{n} + 2 a_{n-1} ,初項(第0項)$ a_0 ,第1項$ a_1 のとき$ a_4 を求める
$ \begin{array}{|rrrrrrrl|rrrrrrrl|} x^4 & = & x^4 & -x^3 & -2x^2 &&&=0& a_4 & = & a_4 & -a_3 & -2a_2 &&& =0 \\ &&& +x^3 & -x^2 & -2x^1 &&=0&&&& +a_3 & -a_2 & -2a_1 && =0 \\ &&&& +3x^2 & -3x^1 & - 6x^0 &=0&&&&& +3a_2 & -3a_1 & - 6a_0 &=0 \\ &&&&& +5x^1 & +6x^0 &=5x+6&&&&&& +5a_1 & +6a_0 & = 5a_1+6a_0 \end{array}
$ x^4 = (x^2+x+3)(x^2-x^1-2x^0)+5x^1+6x^0 の計算のアナロジーで$ a_4 = 5a_1+6a_0 とわかる。
この考え方を一般化すると、$ x^n = P(x)(x^2-px^1+qx^0) + q_nx^1 + r_nx^0 となることのアナロジーより、漸化式$ a_{n+1}=pa_{n}-qa_{n-1} に対して$ a_{n} = \sum_{k=0}^{n-2}p_k (a_{k+2}-pa_{k+1}+qa_{k}) + r_n a_{1} + s_n a_{0} ($ P(x)=\sum_{k=0}^{n-2} p_{k} x^{k} )となる。ここで$ r_n ,$ s_n は$ x^2-px+q=0 の解$ \alpha ,$ \beta (縮退していなければ)を用いて$ \alpha^n = r_n\alpha + s_n ,$ \beta^n = r_n\beta + s_n から求まる。これは言い換えると、剰余の1次式が$ (\alpha,\alpha^n) ,$ (\beta,\beta^n) を満たすことからLagrange補間を用いて$ x^n \approx \alpha^n\frac{x^1-\beta x^0}{\alpha-\beta} + \beta^n\frac{x^1-\alpha x^0}{\beta-\alpha} であるから、数列の第$ n 項は$ a_n = \alpha^n\frac{a_1-\beta a_0}{\alpha-\beta} + \beta^n\frac{a_1-\alpha a_0}{\beta-\alpha} .
組立除法で例題の係数のみを見る:
$ \begin{array}{rr|rrrrr} && 1 & 0 & 0 & 0 & 0 \\\hline 1 & & & 1 & 1 & 3 & \times \\ & 2 &&& 2 & 2 & 6 \\\hline & & 1 & 1 & 3 & |\ 5 & 6\end{array} より$ a_4=5a_1+6a_0 .