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

ペラン数列の四項間漸化式の特性方程式は $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$

となる。

多項定理より，

$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つの項をまとめた

$\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}$

が整数であることを証明すればよい（$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$ の基本対称式の多項式（係数は整数）で書けることから分かる（→注）。