テトラナッチ数列の一般項を求める

2667

テトラナッチ数列とは

テトラナッチ数列の一般項を求めてみましょう。
テトラナッチ数列とは、フィボナッチ数列に類似した数列で、フィボナッチ数列の漸化式が先行2項の和であるのに対し、先行４項の和で定義されるものです。この記事では以下のとおり定義します。

テトラナッチ数列

{T_{n}}

の漸化式

$\begin{array}{r} {\begin{cases} T_{0} = T_{1} = T_{2} = 0, \\ T_{3} = 1, \\ T_{n + 4} = T_{n} + T_{n + 1} + T_{n + 2} + T_{n + 3} (n \geq 0) . \end{cases} \end{array}$

初項を $T_{0}$ として初めの方を書き下すとこんなかんじになります。

テトラナッチ数列

${T_{n}} = {0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, \dots} (n \geq 0)$

母関数を閉じた式で表す

テトラナッチ数列の一般項を求めるために、まずその母関数を考えます。
母関数とは、数列に対応づけられた関数で、次のようなものです。

テトラナッチ数列の母関数

$\begin{aligned} T (x) & = T_{0} x^{0} + T_{1} x^{1} + T_{2} x^{2} + T_{3} x^{3} + T_{4} x^{4} + T_{5} x^{5} + T_{6} x^{6} + T_{7} x^{7} + T_{8} x^{8} + \dots \\ = 0 + 0 x + 0 x^{2} + 1 x^{3} + 1 x^{4} + 2 x^{5} + 4 x^{6} + 8 x^{7} + 15 x^{8} + \dots \\ = x^{3} + x^{4} + 2 x^{5} + 4 x^{6} + 8 x^{7} + 15 x^{8} + \dots \end{aligned}$

この式を次のように操作すると閉じた式が得られます。
　　　　 $\begin{matrix} T (x) & = & x^{3} + & x^{4} + & 2 x^{5} + & 4 x^{6} + & 8 x^{7} + & 15 x^{8} + \dots \\ x T (x) & = & x^{4} + & x^{5} + & 2 x^{6} + & 4 x^{7} + & 8 x^{8} + \dots \\ x^{2} T (x) & = & x^{5} + & x^{6} + & 2 x^{7} + & 4 x^{8} + \dots \\ x^{3} T (x) & = & x^{6} + & x^{7} + & 2 x^{8} \dots \\ x^{4} T (x) & = & x^{7} + & x^{8} \dots \end{matrix}$

　　　　 $(1 - x - x^{2} - x^{3} - x^{4}) T (x) = x^{3}$
　　　　 $∴ T (x) = \frac{x^{3}}{1 - x - x^{2} - x^{3} - x^{4}}$

母関数の式を部分分数分解する

母関数の式は次のように部分分数分解できます。
参考:「 1/((x-a)(x-b)(x-c)(x-d))を部分分数分解する」

　　 $x$ の方程式 $1 - x - x^{2} - x^{3} - x^{4} = 0$ の4つの解を $α, β, γ, δ$ として、
　　　　 $\begin{aligned} T (x) & = \frac{x^{3}}{1 - x - x^{2} - x^{3} - x^{4}} \\ = \frac{- x^{3}}{(x - α) (x - β) (x - γ) (x - δ)} \\ = \frac{- x^{3}}{x - α} \cdot \frac{1}{(α - β) (α - γ) (α - δ)} \\ + \frac{- x^{3}}{x - β} \cdot \frac{1}{(β - α) (β - γ) (β - δ)} \\ + \frac{- x^{3}}{x - γ} \cdot \frac{1}{(γ - α) (γ - β) (γ - δ)} \\ + \frac{- x^{3}}{x - δ} \cdot \frac{1}{(δ - α) (δ - β) (δ - γ)} \\ = \frac{x^{3}}{1 - \frac{x}{α}} \cdot \frac{1}{α (α - β) (α - γ) (α - δ)} \\ + \frac{x^{3}}{1 - \frac{x}{β}} \cdot \frac{1}{β (β - α) (β - γ) (β - δ)} \\ + \frac{x^{3}}{1 - \frac{x}{γ}} \cdot \frac{1}{γ (γ - α) (γ - β) (γ - δ)} \\ + \frac{x^{3}}{1 - \frac{x}{δ}} \cdot \frac{1}{δ (δ - α) (δ - β) (δ - γ)} \end{aligned}$

さらに、 $\frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \dots$ と無限級数化する方法を使えば

　　　　 $\begin{aligned} T (x) & = \sum_{n = 0}^{\infty} x^{n + 3} (\frac{1}{α^{n + 1} (α - β) (α - γ) (α - δ)} \\ + \frac{1}{β^{n + 1} (β - α) (β - γ) (β - δ)} \\ + \frac{1}{γ^{n + 1} (γ - α) (γ - β) (γ - δ)} \\ + \frac{1}{δ^{n + 1} (δ - α) (δ - β) (δ - γ)}) \end{aligned}$

テトラナッチ数列の一般項を求める

ここで　 $T (x) = \sum_{n = 0}^{\infty} T_{n} x^{n}$ 　だったことを思い出して上記の式と係数比較すると、テトラナッチ数列の一般項を表す式が得られます。

テトラナッチ数列の一般項

$x$ の方程式 $1 - x - x^{2} - x^{3} - x^{4} = 0$ の4つの解を $α, β, γ, δ$ として、
$\begin{aligned} T_{n} & = (\frac{1}{α^{n - 2} (α - β) (α - γ) (α - δ)} \\ + \frac{1}{β^{n - 2} (β - α) (β - γ) (β - δ)} \\ + \frac{1}{γ^{n - 2} (γ - α) (γ - β) (γ - δ)} \\ + \frac{1}{δ^{n - 2} (δ - α) (δ - β) (δ - γ)}) (n \geq 3) \end{aligned}$

ところで、ここまで $x$ の方程式 $1 - x - x^{2} - x^{3} - x^{4} = 0$ の4つの解を $α, β, γ, δ$ として計算してきましたが、 $x = \frac{1}{t}$ と置換すると

　　　　 $1 - \frac{1}{t} - \frac{1}{t^{2}} - \frac{1}{t^{3}} - \frac{1}{t^{4}} = 0$

両辺に $t^{4}$ をかけると

　　　　 $t^{4} - t^{3} - t^{2} - t - 1 = 0$

となることから、 $t$ の方程式　 $t^{4} - t^{3} - t^{2} - t - 1 = 0$ の解は $\frac{1}{α}, \frac{1}{β}, \frac{1}{γ}, \frac{1}{δ}$ と、逆数になります。
これを使って先ほどの式を書き換えると

テトラナッチ数列の一般項の書き換え

$x$ の方程式 $x^{4} - x^{3} - x^{2} - x - 1 = 0$ の4つの解を $α, β, γ, δ$ として、
$\begin{aligned} T_{n} & = (\frac{α^{n - 2}}{(\frac{1}{α} - \frac{1}{β}) (\frac{1}{α} - \frac{1}{γ}) (\frac{1}{α} - \frac{1}{δ})} \\ + \frac{β^{n - 2}}{(\frac{1}{β} - \frac{1}{α}) (\frac{1}{β} - \frac{1}{γ}) (\frac{1}{β} - \frac{1}{δ})} \\ + \frac{γ^{n - 2}}{(\frac{1}{γ} - \frac{1}{α}) (\frac{1}{γ} - \frac{1}{β}) (\frac{1}{γ} - \frac{1}{δ})} \\ + \frac{δ^{n - 2}}{(\frac{1}{δ} - \frac{1}{α}) (\frac{1}{δ} - \frac{1}{β}) (\frac{1}{δ} - \frac{1}{γ})}) (n \geq 3) \end{aligned}$

テトラナッチ数列の一般項ができました!
同じ方法で、任意のk-ナッチ数列の一般項を求めることができるはずです。

(2020/11/12 追記)
もう少しシンプルにできることに気がついたので追記します。

解と係数の関係より $α β γ δ = - 1$ となりますから、先程の式の分母について、例えば第1項の分母は

$\begin{aligned} (\frac{1}{α} - \frac{1}{β}) (\frac{1}{α} - \frac{1}{γ}) (\frac{1}{α} - \frac{1}{δ}) & = \frac{(β - α) (γ - α) (δ - α)}{α^{3} β γ δ} \\ = \frac{(α - β) (α - γ) (α - δ)}{α^{2}} \end{aligned}$

と変形できますので、先程の式をさらに書き換えると

テトラナッチ数列の一般項の書き換え(その2)

$x$ の方程式 $x^{4} - x^{3} - x^{2} - x - 1 = 0$ の4つの解を $α, β, γ, δ$ として、
$\begin{aligned} T_{n} & = (\frac{α^{n}}{(α - β) (α - γ) (α - δ)} \\ + \frac{β^{n}}{(β - α) (β - γ) (β - δ)} \\ + \frac{γ^{n}}{(γ - α) (γ - β) (γ - δ)} \\ + \frac{δ^{n}}{(δ - α) (δ - β) (δ - γ)}) (n \geq 3) \end{aligned}$

いい感じになりました。

kナッチ数列の一般項についての予想との関係

最後の式を観察すると、
フィボナッチ数列を拡張したk-ナッチ数列の一般項についての予想

が、テトラナッチ数列(4-ナッチ数列)の場合、少なくともnが大きいときは成り立っていることがわかりました。
$x$ の方程式 $x^{4} - x^{3} - x^{2} - x - 1 = 0$ の4つの解(近似解)は次のようになります。
　　 $α \approx 1.92756$
　　 $β \approx - 0.77480$
　　 $γ \approx - 0.07637 + 0.81470 i$
　　 $δ \approx - 0.07637 - 0.81470 i$