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

p0=3,p1=0,p2=2p_0=3,p_1=0,p_2=2,

pn=pn2+pn3(n3)p_n=p_{n-2}+p_{n-3}\:(n\geq 3)

によって定まる数列 pnp_nペラン数列と言う。

ペラン数列の最初の方の項は

3,0,2,3,2,5,5,7,10,12,17,22,29,393,0,2,3,2,5,5,7,10,12,17,22,29,39

という感じです。この記事ではペラン数列の美しい性質を紹介します!

ペラン数列の一般項

ペラン数列の一般項

三次方程式 x3x1=0x^3-x-1=0 の解を x1,x2,x3x_1,x_2,x_3 とおくと,

pn=x1n+x2n+x3np_n=x_1^n+x_2^n+x_3^n

一般項の導出は漸化式の特性方程式の意味とうまくいく理由の冒頭の定理を使います。

証明

ペラン数列の四項間漸化式の特性方程式は x3x1=0x^3-x-1=0 であるので,ある定数 C1,C2,C3C_1,C_2,C_3 を用いて

pn=C1x1n+C2x2n+C3x3np_n=C_1x_1^n+C_2x_2^n+C_3x_3^n

と表せる。

p0,p1,p2p_0,p_1,p_2 から C1,C2,C3C_1,C_2,C_3 が定まる。実は C1=C2=C3=1C_1=C_2=C_3=1 とすればうまくいくことを以下で示す。 C1=C2=C3=1C_1=C_2=C_3=1 とすると,解と係数の関係より

p0=C1+C2+C3=3p_0=C_1+C_2+C_3=3

p1=x1+x2+x3=0p_1=x_1+x_2+x_3=0

p2=x12+x22+x32=(x1+x2+x3)22(x1x2+x2x3+x3x1)=022(1)=2p_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

となる。

なお,x1,x2,x3x_1,x_2,x_3 のうち1つは実数で残りの2つは複素数です。カルダノの公式を使って3次方程式を解くと,実数解は 12+162333+12162333\sqrt[3]{\dfrac{1}{2}+\dfrac{1}{6}\sqrt{\dfrac{23}{3}}}+\sqrt[3]{\dfrac{1}{2}-\dfrac{1}{6}\sqrt{\dfrac{23}{3}}} となります。実は,この数はプラスチック数と呼ばれます。おもしろい名前ですね。

ペラン数列と素数

ペラン数列の性質

任意の素数 qq に対して pqp_qqq の倍数。

p2=2,p3=3,p5=5,p7=7,p11=22,p13=39p_2=2,p_3=3,p_5=5,p_7=7,p_{11}=22,p_{13}=39

という感じです!証明はけっこう難しいです。

証明

多項定理より,

0=(x1+x2+x3)q=k1,k2,k30,k1+k2+k3=qq!k1!k2!k3!x1k1x2k2x3k30=(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}

右辺の和において,k1,k2,k3k_1,k_2,k_3 のいずれも qq でない部分を集めたものは qq の倍数である(※)
ので,x1q+x2q+x3q=pqx_1^q+x_2^q+x_3^q=p_qqq の倍数となる。

以下(※)を証明する。まず,k1,k2,k3k_1,k_2,k_3 のいずれも qq でないとき,qq は素数なので q!k1!k2!k3!\dfrac{q!}{k_1!k_2!k_3!}qq の倍数である。

よって,あとは k1,k2,k3k_1,k_2,k_3 が全て異なる場合,6つの項をまとめた

symx1k1x2k2x3k3=x1k1x2k2x3k3+x1k1x2k3x3k2+x1k2x2k1x3k3+x1k2x2k3x3k1+x1k3x2k1x3k2+x1k3x2k2x3k1\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}

が整数であることを証明すればよい(k1,k2,k3k_1,k_2,k_3 の中に等しいものがある部分は別に考える必要があるが,同様なので省略)。

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

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

似たような数列

  • ペラン数列は,
    pn=pn2+pn3(n3)p_n=p_{n-2}+p_{n-3}\:(n\geq 3)
    p0=3,p1=0,p2=2p_0=3,p_1=0,p_2=2
    でした。

  • パトヴァン数列
    pn=pn2+pn3(n3)p_n=p_{n-2}+p_{n-3}\:(n\geq 3)
    p0=1,p1=1,p2=1p_0=1,p_1=1,p_2=1
    はペラン数列と漸化式が同じで,初期条件だけ異なります。

  • フィボナッチ数列
    pn=pn1+pn2(n2)p_n=p_{n-1}+p_{n-2}\:(n\geq 2)
    p0=0,p1=1p_0=0,p_1=1
    も似ています。→フィボナッチ数列の7つの性質(一般項・黄金比・互いに素)

  • リュカ数列
    pn=pn1+pn2(n2)p_n=p_{n-1}+p_{n-2}\:(n\geq 2)
    p0=2,p1=1p_0=2,p_1=1
    も似ています。

読者の方に教えてもらったネタです,感謝!