定数係数斉次線型漸化式は、特性方程式(characteristic equation)を用いることにより、解く事ができます。この場合、解くとは、数列や漸化式（再帰的公式）のような明示的公式(Expl

定数係数斉次線型漸化式(homogeneous recurrence relations)は、特性方程式(characteristic equation)を用いることにより、解く事ができます。 この場合、解くとは、数列や漸化式のような再帰関係式(Recurrence Relation)を、明示的公式(Explicit Formula)、閉形式(Closed-from)に書き換えることを言います。

例えば、g(n) = 3g(n-1) - 2g(n - 2)というような明示的公式を、 g(n)=2**n (2のn乗, Python表記) と言うような、閉形式に変換することを言います。

さて、この作業がどのように行われるのかは、経験的推測に基づいて確立された分けなのです。つまり、やってみたら、こうなる事がわかった、と言う事です。

やり方としては、f(n)と言う関数に対して、x**n (xのn乗)を当てはめると言う事です。 その際、詳細の特定因子を、因数分解によって導きます。 そして、このやり方が、定数係数斉次線型漸化式の場合には有効である事、そして、その算出方法を、特性方程式と言うのです。 では、具体的に、g(n) = 3g(n-1) - 2g(n-2), Base: g(0) = 1, g(1) = 2 と定義された再帰関係式を、特性方程式を用いて解きます。 まず、g(n) = 3g(n - 1) - 2g(n - 2)をザックリと見つめ、 x**n = 3x**(n - 1) - 2x**(n - 2)と決めつけます。この場合、意味をあまり考えてはいけません。 意味は難しいです。経験上、答えは、このようになるものと信じるのです。 次に、x**n = 3x**(n - 1) - 2x**(n - 2)を数学的に簡素化します。 両辺を、x**(n - 2)で割ります。 すると、x**2 = 3x - 2 となります。 因数分解し、(x - 1)(x - 2)=0 となります。<= この方程式を特性方程式(characteristic equation) と言います。 ここで、因数の重根または反復根(multiple roots, またはrepeated roots)と言う概念が必要になります。 ここでは、両因数共々１です。--- 注：重根の概念を下に添えておきます。 ですから、 g(n) = s1**n + t2**n となります。これを、general solutionと言います。

定義から、g(0) = s + t = 1, g(1) = s + 2t = 2となります。 この連立工程式から、t = 1, s = 0 となります。 よって、g(n) = s1**n + t2**n = 2**n が導き出されます。

つまり、閉形式、g(n) = 2**n となります。

注：重(multiplicity) 根(root) の概念

https://ja.wikipedia.org/wiki/多項式の根

例えば、特性方程式で、((x - 2)**4)((x - 3)**2) = 0 の因数が導かれたと仮定します。 この場合、 (x-2)**4　は multiplicity 4 and root 2 で、2**n, n2**n, n**2(2**n), n**3(2**n)と4つの項に分けられ、 a1*2**n + a2*n2**n + a3*n**2(2**n) + a4*n**3(2**n)と、なんと足し算で表記してしまうのです。[(x - 2)から、2が当てはめられます。] 同様に、((x-3)**2)は、multiplicity 2 and root 3で、3**n, n3**nと、2つの項に分けます。[(x - 3)から、3が当てはめられます。] 足し算表記で、a5*3**n + a6*n3**nと表します。 よって、g(n) = a1*2**n + a2*n2**n + a3*n**2(2**n) + a4*n**3(2**n) + a5*3**n + a6*n3**n と表す事ができます。 閉形式を求めるには、ベース(Base case)となる、g(0), g(1), g(2), g(3), g(4), g(5)が必要となります。 このベースをもとに、６連立方程式から、a1, a2, a3, a4, a5 を導きます。 この特性方程式を基に、フィボナッチ数(Fibonacci number)などの再帰的公式を閉形式に変換する事ができます。 https://en.wikipedia.org/wiki/Fibonacci_number

閉形式が見出せない、多々の問題は、プログラムを書くことにより、コンピュータで演算する事ができます。つまり、コンピュータは、明示的公式から解を解くのが、人間より遥かに得意なのです。ヤバミー