2015/12/28

ペラン数列の一般項および素数との関係

分野: 数列  レベル: マニアック

$p_0=3,p_1=0,p_2=2$,
$p_n=p_{n-2}+p_{n-3}\:(n\geq 3)$
によって定まる数列 $p_n$ をペラン数列と言う。


ペラン数列の最初の方の項は
$3,0,2,3,2,5,5,7,10,12,17,22,29,39$
という感じです。この記事ではペラン数列の美しい性質を紹介します!

ペラン数列の一般項

三次方程式 $x^3-x-1=0$ の解を $x_1,x_2,x_3$ とおくと,
$p_n=x_1^n+x_2^n+x_3^n$

なお,$x_1,x_2,x_3$ のうち1つは実数で残りの2つは複素数です。一般項の導出は漸化式の特性方程式の意味とうまくいく理由の冒頭の定理を使います。

証明

ペラン数列の四項間漸化式の特性方程式は $x^3-x-1=0$ であるので,ある定数 $C_1,C_2,C_3$ を用いて
$p_n=C_1x_1^n+C_2x_2^n+C_3x_3^n$
と表せる。

$p_0,p_1,p_2$ から $C_1,C_2,C_3$ が定まる。実は $C_1=C_2=C_3=1$ とすればうまくいくことを以下で示す。 $C_1=C_2=C_3=1$ とすると,解と係数の関係より
$p_0=C_1+C_2+C_3=3$
$p_1=x_1+x_2+x_3=0$
$p_2=x_1^2+x_2^2+x_3^2\\
=(x_1+x_2+x_3)^2-2(x_1x_2+x_2x_3+x_3x_1)\\
=0^2-2\cdot (-1)\\
=2$
となる。

ペラン数列と素数

任意の素数 $q$ に対して $p_q$ は $q$ の倍数。

$p_2=2,p_3=3,p_5=5,p_7=7,p_{11}=22,p_{13}=39$
という感じです!証明はけっこう難しいです。

証明

多項定理より,
$0=(x_1+x_2+x_3)^q=\displaystyle\sum_{k_1,k_2,k_3\geq 0,\:k_1+k_2+k_3=q}\dfrac{q!}{k_1!k_2!k_3!}x_1^{k_1}x_2^{k_2}x_3^{k_3}$

右辺の和において,$k_1,k_2,k_3$ のいずれも $q$ でない部分を集めたものは $q$ の倍数である(※)
ので,$x_1^q+x_2^q+x_3^q=p_q$ は $q$ の倍数となる。

以下(※)を証明する。まず,$k_1,k_2,k_3$ のいずれも $q$ でないとき,$q$ は素数なので $\dfrac{q!}{k_1!k_2!k_3!}$ は $q$ の倍数である。
よって,あとは $k_1,k_2,k_3$ が全て異なる場合,6つの項をまとめた
$\begin{eqnarray}\displaystyle\sum_{\mathrm{sym}}x_1^{k_1}x_2^{k_2}x_3^{k_3}&=&x_1^{k_1}x_2^{k_2}x_3^{k_3}+x_1^{k_1}x_2^{k_3}x_3^{k_2}+x_1^{k_2}x_2^{k_1}x_3^{k_3}\\&+&x_1^{k_2}x_2^{k_3}x_3^{k_1}+x_1^{k_3}x_2^{k_1}x_3^{k_2}+x_1^{k_3}x_2^{k_2}x_3^{k_1}\end{eqnarray}$
が整数であることを証明すればよい($k_1,k_2,k_3$ の中に等しいものがある部分は別に考える必要があるが,同様なので省略)。

これは,$\displaystyle\sum_{\mathrm{sym}}x_1^{k_1}x_2^{k_2}x_3^{k_3}$ が $x_1,x_2,x_3$ の基本対称式の多項式(係数は整数)で書けることから分かる(→注)。

注:対称式の基本定理の証明を参照して下さい。なお,リンク先では係数が整数であることは説明していませんが,証明から分かります。

読者の方に教えてもらったネタです,感謝!
分野: 数列  レベル: マニアック