x^n+1/x^n を x + 1/x で表す式

背景

円分多項式 $x^n -1 = 0$ を考え、その因数として$x^{2k} + x^{2k-1} + .. + 1$ などの形の式がでてきます。これを$x+1/x = u$ と置いて簡単にしようとしました。すると$x^n + 1/x^n$ を$ u $ で表す問題が生じます。この問題からチェビシェフ多項式がでてきました。

ニュートンの恒等式

$$ u = x + 1/x $$
とし、
$$ u_n = x^n + 1/x^n $$
のときを$u$で表すことを考えます。これはニュートンの恒等式の方法で解けます。

$x,1/x$は
$$ x^2 - u x + 1 = 0 $$
の解です。よって

\begin{eqnarray} x^2 - u x + 1 &=& 0 \\ 1/x^2 - u/x + 1 &=& 0 \end{eqnarray}
これを足すと
\begin{eqnarray} x^2 + 1/x^2 - u (x + 1/x ) + 2 &=& 0 \\ u_2 - u u_1 +2 &=& 0 \\ \end{eqnarray}
また元の２つの式に$x,1/x$をかけたものを足すと
\begin{eqnarray} x^3 + 1/x^3 - u (x^2 + 1/x^2 ) + x + 1/x &=& 0 \\ u_3 - u u_2 + u_1 &=& 0 \\ \end{eqnarray}
同様に
$$ u_{n+2} - u_{n+1} u + u_n = 0 $$
という漸化式が得られます。

$u_0 = 2$ とすればすべての場合について成り立ちます。実際
$x^0 + 1/x^0 = 1 + 1 = 2$ と考えれます。

この式は $u = 2t$ とおけばチェビシェフ多項式の漸化式になります。実際
$x + 1/x = 2t$ とおき、$x = e^{i \theta} $ とおけば $t = \cos \theta$ $t_n = (x^n + 1/x^n)/2 = \cos n \theta$ となります。

以下はこの漸化式を解いた多項式の係数を表にしたものです。
\begin{array}{c|ccccccc} n & u^n & u^{n-2} & u^{n-4} & u^{n-6} & u^{n-8} & u^{n-10} & u^{n-12} & \\\hline 0 & 2 & & & & & & & \\ 1 & 1 & & & & & & & \\ 2 & 1 & -2 & & & & & & \\ 3 & 1 & -3 & & & & & & \\ 4 & 1 & -4 & 2 & & & & & \\ 5 & 1 & -5 & 5 & & & & & \\ 6 & 1 & -6 & 9 & -2 & & & & \\ 7 & 1 & -7 & 14 & -7 & & & & \\ 8 & 1 & -8 & 20 & -16 & 2 & & & \\ 9 & 1 & -9 & 27 & -30 & 9 & & & \\ 10 & 1 & -10 & 35 & -50 & 25 & -2 & & \\ 11 & 1 & -11 & 44 & -77 & 55 & -11 & & \\ 12 & 1 & -12 & 54 & -112 & 105 & -36 & 2 & \\ \end{array}
これより$u_n = u^n - a_n u^{n-2} + b_n u^{n-4} - c_n u^{n-6} + .. $　という形で表されることが分かります。ただし$n=0$のときだけ別で$u_0=2$です。

漸化式から$a_n,b_n,c_n,..$が満たす関係式を求めます。
\begin{eqnarray} u_{n} &=& u^{n} &-& a_{n}u^n &+& b_{n} u^{n-2} &-& c_{n} u^{n-4} &+& .. \\ - u u_{n-1} &=& - u^{n+2} &+& a_{n-1}u^n &-& b_{n-1} u^{n-2} &+& c_{n-1} u^{n-4} &-& .. \\ u_{n-2} &=& && u^n &-& a_{n-2} u^{n-2} &+& b_{n-2} u^{n-4} &-& .. \\ \end{eqnarray}
これを足すと0になるので係数比較より
\begin{eqnarray} a_{n} - a_{n-1} &=& 1 \\ b_{n} - b_{n-1} &=& a_{n-2} \\ c_{n} - c_{n-1} &=& b_{n-2} \\ .. \end{eqnarray}
という関係が成り立ちます。この関係式はパスカルの三角形を表す式とほぼ同じです。先ほどの表の二段ずれている部分を一段にすると

\begin{array}{cccccccccccccccc} 2 & & & & & & & & & & & & & & & \\ 1 & 2 & & & & & & & & & & & & & & \\ 1 & 3 & 2 & & & & & & & & & & & & & \\ 1 & 4 & 5 & 2 & & & & & & & & & & & & \\ 1 & 5 & 9 & 7 & 2 & & & & & & & & & & & \\ 1 & 6 & 14 & 16 & 9 & 2 & & & & & & & & & & \\ 1 & 7 & 20 & 30 & 25 & 11 & 2 & & & & & & & & & \\ 1 & 8 & 27 & 50 & 55 & 36 & 13 & 2 & & & & & & & & \\ 1 & 9 & 35 & 77 & 105 & 91 & 49 & 15 & 2 & & & & & & & \\ 1 & 10 & 44 & 112 & 182 & 196 & 140 & 64 & 17 & 2 & & & & & & \\ \end{array}
となり、右端を2にしたパスカルの三角形になります。これは以下のパスカルの三角形に、一段上の行を右にずらして足すという操作をしたものになります。
\begin{array}{cccccccccccccccc} 1 & & & & & & & & & & & & & & & \\ 1 & 1 & & & & & & & & & & & & & & \\ 1 & 2 & 1 & & & & & & & & & & & & & \\ 1 & 3 & 3 & 1 & & & & & & & & & & & & \\ 1 & 4 & 6 & 4 & 1 & & & & & & & & & & & \\ 1 & 5 & 10 & 10 & 5 & 1 & & & & & & & & & & \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & & & & & & & & & \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & & & & & & & & \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & & & & & & & \\ 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & & & & & & \\ 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 & & & & \ & \\ \end{array}

なので一つ前の表の n 行 k 列目の数字は
$$ \dbinom{n}{k} + \dbinom{n-1}{k-1} $$
となります。これを一段ずつずらしたものが、$a_n,b_n,...$で

$$ \dbinom{n-k}{k} + \dbinom{n-k-1}{k-1} $$

となります。よって$u_n$ の一般項は
$$ u_n = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \left(\dbinom{n-k}{k} + \dbinom{n-k-1}{k-1} \right) u^{n-2k} $$
となります。この表現では$n=0$のとき$u_0=2$となることもカバーしています。これを書き下すと
$$ u_n = u^n - n u^{n-2} + \frac{1}{2} n (n-3) u^{n-4} - \frac{1}{6} n (n-4) (n-5) u^{n-6} + \frac{1}{24} n (n-5) (n-6) (n-7) u^{n-8} - ... $$
となります。ただし $n=0$ のとき $u_0 =2 $ となります。この式をみるとまた別の表現
$$ u_n = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \frac{n}{n-2k} \dbinom{n-k-1}{k-1} u^{n-2k} $$
が見えます。これも$n=0$のときだけ例外となります。

指数表現

漸化式を特性方程式を使ってときます。
並進演算子$T$を次のように定義します。
$T u_n = u_{n+1}$
これを用いると漸化式 $u_{n+2} - u_{n+1} u + u_n = 0$ は
$$ (T^2 - u T + 1) u_n = 0 $$
と表せます。この問題は固有値問題の考え方でとけます。ここである実数$\lambda$を用いて$T u_n = \lambda u_n$となるような固有関数$u_n$ を考えます。$T u_n = \lambda u_n$の解は$u_n = \lambda^n u_0$ なので $\lambda^n u_0 $ が$T$の固有関数です。$(T^2 - u T + 1) u_n = 0$
の解は$\lambda^2 - u\lambda + 1 = 0$を満たす$\lambda$を固有値として持つ固有関数の線形結合で表されます。
$\lambda^2 - u\lambda + 1 = 0$ の解は
$$ \lambda = \frac{u \pm \sqrt{u^2-4}}{2} $$
なので$\lambda^n$の線形結合を初期値が一致するように作ると$u_n$が求まり
$$ u_n = \left(\frac{u + \sqrt{u^2-4}}{2}\right)^n + \left(\frac{u - \sqrt{u^2-4}}{2}\right)^n $$
となります。
単に$x,1/x$を$u$で表すと$\frac{u + \sqrt{u^2-4}}{2},\frac{u - \sqrt{u^2-4}}{2}$になるので$x^n + 1/x^n$ が上の式になるとも考えられます。

もう一つの表現

チェビシェフ多項式のwikiページにはまた別の表現がのっています。今回の$u$で表すと
$$ u_n = \frac{1}{2^{n-1}}\sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n}{2k} (u^2-4)^k u^{n-2k} $$
となります。この表現は以下のようにして導けます。
$$ v = x - 1/x $$
とおきます。すると
\begin{eqnarray} x &=& \frac{u+v}{2} \\ \frac{1}{x} &=& \frac{u-v}{2} \\ \end{eqnarray}
よって
\begin{eqnarray} x^n + \frac{1}{x^n} &=& \left(\frac{u+v}{2}\right)^n + \left(\frac{u-v}{2}\right)^n \\ &=& \frac{1}{2^n}\left((u+v)^n + (u-v)^n\right) \end{eqnarray}
２つの項を二項展開すると、一つ飛ばしで足されるので
\begin{eqnarray} x^n + \frac{1}{x^n} &=& \frac{1}{2^{n-1}}\sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n}{2k} u^{n-2k} v^{2k} \\ &=& \frac{1}{2^{n-1}}\sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n}{2k} (u^2-4)^k u^{n-2k} \end{eqnarray}
となります。

結果

$$u = x + 1/x $$
とおき
$$u_n = x^n + 1/x^n$$
を$u$の多項式で表すと

$$ u_n = \left(\frac{u + \sqrt{u^2-4}}{2}\right)^n + \left(\frac{u - \sqrt{u^2-4}}{2}\right)^n $$

$$ u_n = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \left(\dbinom{n-k}{k} + \dbinom{n-k-1}{k-1} \right) u^{n-2k} $$
$$ u_n = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \frac{n}{n-2k} \dbinom{n-k-1}{k-1} u^{n-2k} $$
$$ u_n = \frac{1}{2^{n-1}}\sum_{k=0}^{\lfloor n/2 \rfloor} \dbinom{n}{2k} (u^2-4)^k u^{n-2k} $$
といろいろな表現ができる。

$1+u+u_2+..+u_n$を$u$の多項式で表す

円分多項式で$u=x+1/x$とおくと、$1+u+u_2+..+u_n$や$1-u+u_2-u_3+..$という式がでてきます。これを$u$の多項式で表すことを考えます。$u_n$の係数を次数が低いほうから並べると以下の表のようになります。ただし$u_0$の位置を2ではなく1としています。これは$1+u+u_2+..$のはじめの1を表しています。

\begin{array}{ccccccccccc} 1 & u & u^2 & u^3 & u^4 & u^5 & u^6 & u^7 & u^8 & u^9 & u^{10} \\\hline 1 & & & & & & & & & & \\ 0 & 1 & & & & & & & & & \\ -2 & 0 & 1 & & & & & & & & \\ 0 & -3 & 0 & 1 & & & & & & & \\ 2 & 0 & -4 & 0 & 1 & & & & & & \\ 0 & 5 & 0 & -5 & 0 & 1 & & & & & \\ -2 & 0 & 9 & 0 & -6 & 0 & 1 & & & & \\ 0 & -7 & 0 & 14 & 0 & -7 & 0 & 1 & & & \\ 2 & 0 & -16 & 0 & 20 & 0 & -8 & 0 & 1 & & \\ 0 & 9 & 0 & -30 & 0 & 27 & 0 & -9 & 0 & 1 & \\ -2 & 0 & 25 & 0 & -50 & 0 & 35 & 0 & -10 & 0 & 1 \\ \end{array}
この表を上から足していった表が$1+u+u_2+..$の係数になります。
\begin{array}{cccccccccc} 1 & u & u^2 & u^3 & u^4 & u^5 & u^6 & u^7 & u^8 & u^9 & u^{10} \\\hline 1 & & & & & & & & & \\ 1 & 1 & & & & & & & & \\ -1 & 1 & 1 & & & & & & & \\ -1 & -2 & 1 & 1 & & & & & & \\ 1 & -2 & -3 & 1 & 1 & & & & & \\ 1 & 3 & -3 & -4 & 1 & 1 & & & & \\ -1 & 3 & 6 & -4 & -5 & 1 & 1 & & & \\ -1 & -4 & 6 & 1 & -5 & -6 & 1 & 1 & & \\ 1 & -4 & -1 & 1 & 15 & -6 & -7 & 1 & 1 & \\ 1 & 5 & -1 & -2 & 15 & 21 & -7 & -8 & 1 & 1 \\ \end{array}
このようにパスカルの三角形がダブってるような数列になります。これを数式で表すと
$$ m=\lfloor \frac{n-k}{2}\rfloor $$
とおき
$$ 1 + \sum_{k=1}^n u_k = \sum_{k=0}^n \dbinom{m+k}{m}u^k (-1)^{m} $$
となります。$u_n$の$u$の次数は偶数のみか奇数のみなので、
もう一つよく出てくる項
$1-u+u_2- u_3 +..$
も係数の数字は変わらず奇数次の項にマイナスをつけるだけです。

感想

表と表記法

今回の研究で思ったのは、表をみて考えたほうが速いし分かりやすいということです。シグマ、二項係数、$(-1)^n$、床関数など標準の数学表記を使った表現の式変形を考えるのは大変です。

使われている数学の表記法が最適ではないという気もします。例えば$0,0,1,1,2,2,..$という数列が$\lfloor k/2\rfloor $と表現されたり、$1,0,1,0,..$という数列が$\frac{1+(-1)^n}{2}$と表現されるのは、言いたいことと別の情報が含まれてる感じがします。

初項だけ半分で足すというパターン

今回$1 + u_1 + u_2 + .. $という式で$u_0=2$だけど初項だけ$u_0/2$ということにするという扱いをすれば、統一的に表現できるという経験をしました。このようなパターンはフーリエ級数や$\frac{1}{1+x^n}$の部分分数分解でもでてきます。これは円のn分割の分割線がちょうど実軸上にあるとき、複素共役がそれ自身になるため、二重カウントの防止のために1/2がでてきます。複素数の世界で対称なものを実数で表そうとしたことにより、対称性が崩れたと言えるでしょうか。