-数学- リュカ多項式の性質 (1) - Maxima で綴る数学の旅

f:id:jurupapa:20150711164916j:plain

リュカ多項式の様々な性質については「数学的帰納法で証明できる」で済ませてきました。リュカ多項式とお友達になるには、この記事で証明を確認してください。この記事の証明はMatt Baker 教授の下記のブログを参考にしました。

まず$LP_{n}(x)$の再帰的定義を与え、いくつかの$n$について$LP_{n}(x)$を具体的に計算してみます。

(%i1) LP[0](x):=2;

$$ \tag{${\it \%o}_{1}$}{\it LP}_{0}(x):=2 $$
(%i2) LP[1](x):=x;

$$ \tag{${\it \%o}_{2}$}{\it LP}_{1}(x):=x $$
(%i3) LP[n](x):=x*LP[n-1](x)+LP[n-2](x);

$$ \tag{${\it \%o}_{3}$}{\it LP}_{n}(x):=x\,{\it LP}_{n-1}(x)+{\it LP}_{n-2}(x) $$
(%i4) for n:1 thru 12 do print(expand('LP[n](x)=LP[n](x)));

${\it LP}_{1}(x)=x$
${\it LP}_{2}(x)=x^2+2$
${\it LP}_{3}(x)=x^3+3\,x$
${\it LP}_{4}(x)=x^4+4\,x^2+2$
${\it LP}_{5}(x)=x^5+5\,x^3+5\,x$
${\it LP}_{6}(x)=x^6+6\,x^4+9\,x^2+2$
${\it LP}_{7}(x)=x^7+7\,x^5+14\,x^3+7\,x$
${\it LP}_{8}(x)=x^8+8\,x^6+20\,x^4+16\,x^2+2$
${\it LP}_{9}(x)=x^9+9\,x^7+27\,x^5+30\,x^3+9\,x$
${\it LP}_{10}(x)=x^{10}+10\,x^8+35\,x^6+50\,x^4+25\,x^2+2$
${\it LP}_{11}(x)=x^{11}+11\,x^9+44\,x^7+77\,x^5+55\,x^3+11\,x$
${\it LP}_{12}(x)=x^{12}+12\,x^{10}+54\,x^8+112\,x^6+105\,x^4+36\,x^2+2$
$$ \tag{${\it \%o}_{4}$}\mathbf{done} $$

命題１：${\it LP}_{n}(x)$の定数項${\it LP}_{n}(0)$は${\it LP}_{n-2}(x)$の定数項${\it LP}_{n-2}(0)$と等しい。

証明：定義式%o3の右辺で$x=0$とすると最初の項が消えるので２番目の項の定数項だけが残る。

命題２：$n$が偶数の時${\it LP}_{n}(0)=2$, $n$が奇数の時${\it LP}_{n}(0)=0$である。

証明：命題１と初期値から明らか。

命題3：$n$が奇数の時、${\it LP}_{n}(x)$の1次の項の係数は$n$である。

証明：$n=1$の時1次の項の係数は1で成立している。$n$が$n\ge3$の奇数の時、$n$未満の全ての奇数$k$で${\it LP}_{k}(x)$の1次の項の係数は$k$とする。${\it LP}_{n}(x)$の1次の項の係数は${\it LP}_{n-1}(x)$の定数項と${\it LP}_{n-2}(x)$の1次の項の係数の和である。前者は$n-1$が偶数であることから2, 後者は$n-2$が奇数であることと帰納法の仮定から$n-2$であり、足すと$n$になる。

命題4：$n$が奇数の時、${\it LP}_{n}(x)$の偶数次数の項の係数は$0$である。$n$が偶数の時、${\it LP}_{n}(x)$の奇数次数の項の係数は$0$である。

証明：${\it LP}_{0}(x)=2,\, {\it LP}_{1}(x)=x$では確かに成立している。$n$が3以上の整数である時、命題が$n$未満の全ての自然数$k$で成立すると仮定する。$n$が奇数の時$n-1$は偶数で、帰納法の仮定より${\it LP}_{n-1}(x)$の奇数次数の項の係数は$0$, 故に$x\,{\it LP}_{n-1}(x)$の偶数次数の項の係数は$0$である。また$n-2$は奇数なので帰納法の仮定より${\it LP}_{n-2}(x)$の偶数次数の項の係数は$0$。従って、${\it LP}_{n}(x):=x\,{\it LP}_{n-1}(x)+{\it LP}_{n-2}(x)$の右辺の偶数次数の項の係数は全て$0$。$n$が偶数の場合も同様である。

命題5: 任意の$n \ge 1$について ${\it GLP}_{n}(x)=n\,\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}{\frac{{{n-k}\choose{k}}\,x^{n-2\,k}}{n-k}}$が成り立つ。以下$k$の範囲は$0 \le k \le {\left \lfloor \frac{n}{2} \right \rfloor}$である。

証明:

まずこの有限級数($x$の多項式)を$GLP_{n}(x)$として定義する。

(%i142) GLP[n](x):=intosum(sum(n/(n-k)*binomial(n-k,k)*x^(n-2*k),k,0,floor(n/2)));

$$ \tag{${\it \%o}_{142}$}{\it GLP}_{n}(x):={\it intosum}\left({\it sum}\left(\frac{n}{n-k}\,{{n-k}\choose{k}}\,x^{n-2\,k} , k , 0 , \left \lfloor \frac{n}{2} \right \rfloor\right)\right) $$

ちょっと見易く表示してみる。
(%i143) 'GLP[n](x)=GLP[n](x);

$$ \tag{${\it \%o}_{143}$}{\it GLP}_{n}(x)=n\,\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}{\frac{{{n-k}\choose{k}}\,x^{n-2\,k}}{n-k}} $$

この定義が元の$LP_{i}(x)$と同じ多項式を生成することを一旦、目視で見てから証明に取り掛かることにしよう。$n=1,\, 2$で一致することは後の証明で使う。
(%i145) for i:1 thru 12 do print(ev(GLP[i](x),nouns,expand));

$x$
$x^2+2$
$x^3+3\,x$
$x^4+4\,x^2+2$
$x^5+5\,x^3+5\,x$
$x^6+6\,x^4+9\,x^2+2$
$x^7+7\,x^5+14\,x^3+7\,x$
$x^8+8\,x^6+20\,x^4+16\,x^2+2$
$x^9+9\,x^7+27\,x^5+30\,x^3+9\,x$
$x^{10}+10\,x^8+35\,x^6+50\,x^4+25\,x^2+2$
$x^{11}+11\,x^9+44\,x^7+77\,x^5+55\,x^3+11\,x$
$x^{12}+12\,x^{10}+54\,x^8+112\,x^6+105\,x^4+36\,x^2+2$
$$ \tag{${\it \%o}_{145}$}\mathbf{done} $$

では証明。数学的帰納法を使う。上述のように$n=1,\, 2$で一致することは示した。帰納法の仮定として、$n$未満の全ての$m$について$GLP_{m}(x)$が$LP_{m}(x)$の再帰的定義式を満たしていると仮定する。

$GLP_{n}(x)$が$LP_{n}(x)$と同じ再帰的定義を満たすことを示す。それには$LP_{n}(x)$の定義式の右辺と左辺で任意の$k$, $0 \le k \le {\left \lfloor \frac{n}{2} \right \rfloor}$について $ (n-2\,k) $次の係数が一致することを仮定を使って示せば良い。

$GLP_{n}(x)$の$ (n-2\,k) $次の項の係数を取り出すと、
(%i71) C:n/(n-k)*binomial(n-k,k);

$$ \tag{${\it \%o}_{71}$}\frac{n\,{{n-k}\choose{k}}}{n-k} $$

である。再帰的定義から右辺の$ (n-2\,k) $次の項の係数を計算する式は(%i74)で与えられる。これは$LP_{n-1}(x),\,LP_{n-2}(x)$が帰納法の仮定に従うこと、$LP_{n-2}(x)$の$n-2\,k$次の次数は$ n - 2 - 2 \, (k - 1) $と書き換えられることから得られる。
(%i74) subst(n-1,n,C)+subst(k-1,k,subst(n-2,n,C));

$$ \tag{${\it \%o}_{74}$}\frac{\left(n-1\right)\,{{n-k-1}\choose{k}}}{n-k-1}+\frac{\left(n-2\right)\,{{n-k-1}\choose{k-1}}}{n-k-1} $$

%o71と%o74が一致することを示す。引き算して簡易化すると0になることを見る。
(%i78) rec:C-(subst(n-1,n,C)+subst(k-1,k,subst(n-2,n,C)));

$$ \tag{${\it \%o}_{78}$}\frac{n\,{{n-k}\choose{k}}}{n-k}-\frac{\left(n-1\right)\,{{n-k-1}\choose{k}}}{n-k-1}-\frac{\left(n-2\right)\,{{n-k-1}\choose{k-1}}}{n-k-1} $$

(%i79) makefact(rec),factorial_expand:true,factor;

$$ \tag{${\it \%o}_{79}$}0 $$

これで$LP_{n}(x)$と$GLP_{n}(x)$は$n \ge 1$で一致することが示せた。

系1: $\frac{n\,{{n-k}\choose{k}}}{n-k}$は整数である。

証明: $LP_{n}(x)$と$GLP_{n}(x)$は$n \ge 1$で一致するが、再帰的定義から明らかに$LP_{n}(x)$の係数は整数である。

系2: $p$を奇素数として$LP_{p}(x)$の係数$\frac{p\,{{p-k}\choose{k}}}{p-k}$は$k \ge 1$のとき$p$の倍数であり$k=0$のとき1である。

証明: $k \ge 1$のとき$p \gt p-k$なので、$p-k$は$p$を割り切らない。系1より係数$\frac{p\,{{p-k}\choose{k}}}{p-k}$は整数なので、$p-k$は${{p-k}\choose{k}}$を割り切ることとなる。$p$はそのまま残るので、係数は$p$の倍数である。$k=0$のとき$\frac{p\,{{p-k}\choose{k}}}{p-k}=\frac{p\,{{p}\choose{0}}}{p}={{p}\choose{0}}=1$である。

系3: $p$を奇素数として、$LP_{p}(x) \equiv x^p\, mod\, p$ 及び$H_{p}(x) \equiv x^{\frac{p-1}{2}} \, mod\, p$が成り立つ。

証明: 系2より$LP_{p}(x), H_{p}(x)$の各項の係数は$mod\,p$では$k=1$の場合だけ1として残り、あとは0となる。