トリボナッチ数列の一般項を導く

以前の記事でフィボナッチ数列の一般項を求めましたが、この記事では、フィボナッチ数列の眷属であるトリボナッチ数列 (tribonacci series)の一般項を求めてみます。

トリボナッチ数列の定義

トリボナッチ数列 ${ T_n }$ は以下の初項と漸化式で定義されます：

　　 ${ \displaystyle \begin{align*} \begin{cases} T_0 = T_1 = 0 \\ T_2 = 1 \\ T_{n+3} = T_{n+2} + T_{n+1} + T_n \end{cases} \end{align*} }$

例によって ${ n = 0,\,1,\,2,\,3\,\cdots }$ とします。　フィボナッチ数列が「前2項の和」によって次の項を定義するのに対して、トリボナッチ数列は「前3項の和」によって次の項を定義します。　漸化式が隣接4項間の関係になっているので、高校数学では出てきませんが、一般項の導出に使う数学は高校生でも充分理解可能です。

一般項の導出

ではトリボナッチ数列 ${ T_n }$ の一般項を求めましょう。

特性方程式

隣接4項間の漸化式から一般項を求めるにも特性方程式 (characteristic equation) が重要になってくるので、まずはその解を求めましょう。　まぁ、正直なところ解の具体的な形はいらないんですけどね（ただし、重解を持たないことは重要ですね）。　特性方程式は隣接3項間の場合と同じです。　トリボナッチ数列の漸化式より

　　 ${ \displaystyle \begin{align*} T_{n+3} - T_{n+2} - T_{n+1} - T_n = 0 \end{align*} }$

なので、特性方程式は

　　 ${ \displaystyle \begin{align*} t^3 - t^2 - t - 1 = 0 \end{align*} }$

となります。　この3次方程式の解を ${ \alpha,\,\beta,\,\gamma }$ とすると、「高校数学で導く3次方程式の解の公式」より

　　 ${ \displaystyle \begin{align*} &\begin{cases} \alpha = \frac{1}{3}\left(1 + \mu_+ + \mu_- \right) \\ \beta = \frac{1}{3}\left(1 + \omega\mu_+ + \omega^2\mu_- \right) \\ \gamma = \frac{1}{3}\left(1 + \omega^2\mu_+ + \omega^4\mu_- \right) \end{cases} & \left(\mu_\pm = \sqrt[3]{19 \pm 3\sqrt{33}} \qquad \omega = \frac{-1+\sqrt{3}i}{2} \right) \end{align*} }$

${\omega }$ は1の3乗根のうち1でないものの1つであれば OK です。　また、3次方程式の解と係数の関係より

　　 ${ \displaystyle \begin{align*} \begin{cases} \alpha + \beta + \gamma &= 1 \\ \alpha\beta + \beta\gamma + \gamma\alpha &= -1 \\ \alpha\beta\gamma &= 1 \end{cases} \end{align*} }$

も成り立ちます。

数列 ${ U_n }$ と隣接3項間の漸化式

上記の特性方程式の解を用いて、 ${ T_n }$ の漸化式は

　　 ${ \displaystyle \begin{align*} &T_{n+3} - (\alpha +\beta + \gamma)T_{n+2} + (\alpha\beta + \beta\gamma + \gamma\alpha)T_{n+1} - \alpha\beta\gamma T_n = 0 &\cdots(1) \end{align*} }$

と書けます。　これは以下のように書き換えることができます：

　　 ${ \displaystyle \begin{align*} T_{n+3} - \alpha T_{n+2} = \beta(T_{n+2} - \alpha T_{n+1}) + \gamma(T_{n+2} - \alpha T_{n+1}) - \beta\gamma (T_{n+1} - \alpha T_n) \end{align*} }$

ここで、数列 ${ U_n }$ を以下で定義しましょう：

　　 $U_n = T_{n+1} - \alpha T_n$

${ T_n }$ の漸化式をこの ${ U_n }$ を使って書き換えると

　　 ${ \displaystyle U_{n+2} = \beta U_{n+1} + \gamma U_{n+1} - \beta\gamma U_n \qquad \cdots (2) }$

となります。　また、 ${ U_0,\,U_1 }$ は計算できて

　　 ${ \displaystyle \begin{align*} U_0 = T_1 - \alpha T_0 = 0 \\ U_1 = T_2 - \alpha T_1 = 1 \end{align*} }$

を得ます。

${ U_n }$ の一般項を求める

${ U_n }$ は隣接3項間の漸化式なので、フィボナッチ数列の場合と同じように一般項を求めることができます。　まず (2) 式を以下のように変形して

　　 ${ \displaystyle \begin{align*} U_{n+2} - \beta U_{n+1} = \gamma(U_{n+1} - \beta U_n) \end{align*} }$

数列 ${ V_n }$ を

　　 ${ \displaystyle \begin{align*} V_n = U_{n+1} - \beta U_n \end{align*} }$

によって定義します。　このとき ${ V_n }$ の初項と漸化式は

　　 ${ \displaystyle \begin{align*} \begin{cases} V_0 = U_1 - \beta U_0 = 1 \\ V_{n+1} = \gamma V_n \end{cases} \end{align*} }$

となります。　よって数列 ${ V_n }$ は初項1、公比 ${ \gamma }$ の等比数列で、その一般項は

　　 ${ \displaystyle \begin{align*} V_n &= \gamma^n & \cdots (3) \end{align*} }$

となります（ ${ n = 0,\,1,\,2,\,3\,\cdots }$ に注意）。　同様にして、今度は (2) 式を

　　 ${ \displaystyle \begin{align*} U_{n+2} - \gamma U_{n+1} = \beta(U_{n+1} - \gamma U_n) \end{align*} }$

の様に変形して、数列

　　 ${ \displaystyle \begin{align*} W_n = U_{n+1} - \gamma U_n \end{align*} }$

を導入すると

　　 ${ \displaystyle \begin{align*} \begin{cases} W_0 = U_1 - \gamma U_0 = 1 \\ W_{n+1} = \beta W_n \end{cases} \end{align*} }$

となり、 ${ W_n }$ も等比数列であることが分かって

　　 ${ \displaystyle \begin{align*} W_n &= \beta^n & \cdots (4) \end{align*} }$

を得ます。　(3), (4) 式より

　　 ${ \displaystyle \begin{align*} U_{n+1} - \beta U_n = \gamma^n \\ U_{n+1} - \gamma U_n = \beta^n \end{align*} }$

辺々をそれぞれ引いて

　　 ${ \displaystyle \begin{align*} &(\gamma - \beta) U_n = \gamma^n - \beta^n \\ \therefore \quad & U_n = \frac{\gamma^n - \beta^n}{\gamma - \beta} \end{align*} }$

${ U_n }$ に ${ T_n }$ による定義式を代入すると

　　 ${ \displaystyle \begin{align*} T_{n+1} - \alpha T_n &= \frac{\gamma^n - \beta^n}{\gamma - \beta} & \cdots(5) \end{align*} }$

となります。

${ T_n }$ の一般項を求める

さて、(1) 式は

　　 ${ \displaystyle \begin{align*} T_{n+3} - \beta T_{n+2} = \gamma(T_{n+2} - \beta T_{n+1}) + \alpha(T_{n+2} - \beta T_{n+1}) - \gamma\alpha (T_{n+1} - \beta T_n) \end{align*} }$

のようにも変形できます。　この式から (5) 式を導いた手順を繰り返すと

　　 ${ \displaystyle \begin{align*} T_{n+1} - \beta T_n &= \frac{\alpha^n - \gamma^n}{\alpha - \gamma} & \cdots(6) \end{align*} }$

(5), (6) 式より

　　 ${ \displaystyle \begin{align*} T_{n+1} - \alpha T_n = \frac{\gamma^n - \beta^n}{\gamma - \beta} \\ T_{n+1} - \beta T_n = \frac{\alpha^n - \gamma^n}{\alpha - \gamma} \end{align*} }$

辺々をそれぞれ引くと

　　 ${ \displaystyle \begin{align*} (\beta - \alpha) T_n = \frac{\gamma^n - \beta^n}{\gamma - \beta} - \frac{\alpha^n - \gamma^n}{\alpha - \gamma} \end{align*} }$

よって

　　 ${ \displaystyle \begin{align*} T_n &= \frac{1}{\beta - \alpha}\left(\frac{\gamma^n - \beta^n}{\gamma - \beta} - \frac{\alpha^n - \gamma^n}{\alpha - \gamma}\right) \\ &= \frac{\alpha^n}{(\beta - \alpha)(\gamma - \alpha)} + \frac{\beta^n}{(\gamma - \beta)(\alpha - \beta)} + \frac{\gamma^n}{(\alpha - \gamma)(\beta - \gamma)} \\ &= -\frac{(\beta - \gamma)\alpha^n + (\gamma - \alpha)\beta^n + (\alpha - \beta)\gamma^n}{(\alpha - \beta)(\beta - \gamma)(\gamma - \alpha)} \end{align*} }$

以上をまとめるとトリボナッチ数列の一般項は以下で与えられます：

　　 ${ \displaystyle \begin{align*} T_n &= \frac{\alpha^n}{(\beta - \alpha)(\gamma - \alpha)} + \frac{\beta^n}{(\gamma - \beta)(\alpha - \beta)} + \frac{\gamma^n}{(\alpha - \gamma)(\beta - \gamma)} \\[4mm] &= -\frac{(\beta - \gamma)\alpha^n + (\gamma - \alpha)\beta^n + (\alpha - \beta)\gamma^n}{(\alpha - \beta)(\beta - \gamma)(\gamma - \alpha)} \end{align*} }$

ただし

なんか Wikipedia に載ってるの（wikipedia:フィボナッチ数列）とちょっと違う気もするけど、まっ、いっか（初項の取り方がちょっと違うのが原因でしょう）。

最初の数項を確かめてみる

トリボナッチ数列の最初の数項は

　　 ${ \displaystyle \begin{align*} 0, 0, 1, 1, 2, 4, 7, 13, \cdots \end{align*} }$

です。　この最初の数項を上記の一般項から確かめてみましょう。　特性方程式の解と係数の関係

　　 ${ \displaystyle \begin{align*} \begin{cases} \alpha + \beta + \gamma &= 1 \\ \alpha\beta + \beta\gamma + \gamma\alpha &= -1 \\ \alpha\beta\gamma &= 1 \end{cases} \end{align*} }$

も使います。　あと、分母が面倒なので

　　 ${ \displaystyle \begin{align*} S_n = -(\alpha - \beta)(\beta - \gamma)(\gamma - \alpha)T_n \end{align*} }$

として、実質的に分子のみの計算を行います。

n = 0

　　 ${ \displaystyle \begin{align*} S_0 &= (\beta - \gamma) + (\gamma - \alpha) + (\alpha - \beta) \\ &= 0 \end{align*} }$

n = 1

　　 ${ \displaystyle \begin{align*} S_1 &= (\beta - \gamma)\alpha + (\gamma - \alpha)\beta + (\alpha - \beta)\gamma \\ &= 0 \end{align*} }$

n = 2

　　 ${ \displaystyle \begin{align*} S_2 &= (\beta - \gamma)\alpha^2 + (\gamma - \alpha)\beta^2 + (\alpha - \beta)\gamma^2 \\ &=(\beta - \gamma)\alpha^2 - (\beta^2 - \gamma^2)\alpha + \beta^2\gamma - \beta\gamma^2 \\ &=(\beta - \gamma)\alpha^2 - (\beta - \gamma)(\beta + \gamma)\alpha + \beta\gamma(\beta - \gamma) \\ &= (\beta - \gamma)\left\{\alpha^2 - (\beta + \gamma)\alpha + \beta\gamma\right\} \\ &= (\beta - \gamma)(\alpha - \beta)(\alpha - \gamma) \\ &= -(\alpha - \beta)(\beta - \gamma)(\gamma - \alpha) \end{align*} }$

よって

　　 ${ \displaystyle \begin{align*} T_2 = 1 \end{align*} }$

n = 3

　　 ${ \displaystyle \begin{align*} S_3 &= (\beta - \gamma)\alpha^3 + (\gamma - \alpha)\beta^3 + (\alpha - \beta)\gamma^3 \\ &= (\beta - \gamma)\alpha^3 - (\beta^3 - \gamma^3)\alpha + \beta\gamma(\beta^2 - \gamma^2) \\ &= (\beta - \gamma) \left\{\alpha^3 - (\beta^2 + \beta\gamma + \gamma^2)\alpha + \beta\gamma(\beta + \gamma)\right\} \\ &= (\beta - \gamma)\left\{\alpha^2 - (\beta + \gamma)\alpha + \beta\gamma\right\}\left\{\alpha + (\beta + \gamma)\right\} \\ &= (\beta - \gamma)(\alpha - \beta)(\alpha - \gamma)(\alpha + \beta + \gamma) \end{align*} }$

よって

　　 ${ \displaystyle \begin{align*} T_3 = \alpha + \beta + \gamma = 1 \end{align*} }$

n = 4

　　 ${ \displaystyle \begin{align*} S_4 &= (\beta - \gamma)\alpha^4 + (\gamma - \alpha)\beta^4 + (\alpha - \beta)\gamma^4 \\ &= (\beta - \gamma)\alpha^4 - (\beta^4 - \gamma^4)\alpha + \beta\gamma(\beta^3 - \gamma^3) \\ &= (\beta - \gamma)\left\{\alpha^4 - (\beta^3 + \beta^2\gamma + \beta\gamma^2 + \gamma^3)\alpha + \beta\gamma(\beta^2 + \beta\gamma + \gamma^2)\right\} \\ &= (\beta - \gamma)\left\{\alpha^2 - (\beta + \gamma)\alpha + \beta\gamma\right\}\left\{\alpha^2 + (\beta + \gamma)\alpha + (\beta^2 + \beta\gamma + \gamma^2)\right\} \\ &= -(\alpha - \beta)(\beta - \gamma)(\gamma - \alpha)\left\{(\alpha^2 + \beta^2 + \gamma^2) + (\alpha\beta + \beta\gamma + \gamma\alpha)\right\} \end{align*} }$

ここで

　　 ${ \displaystyle \begin{align*} \alpha^2 + \beta^2 + \gamma^2 &= (\alpha + \beta + \gamma)^2 - 2(\alpha\beta + \beta\gamma + \gamma\alpha) \\ &= 1^2 - 2(-1) \\ &= 3 \end{align*} }$

なので

　　 ${ \displaystyle \begin{align*} T_4 &= \alpha^2 + \beta^2 + \gamma^2 + \alpha\beta + \beta\gamma + \gamma\alpha \\ &= 3 + (-1) \\ &= 2 \end{align*} }$
　　

n = 5

　　 ${ \displaystyle \begin{align*} S_5 &= (\beta - \gamma)\alpha^5 + (\gamma - \alpha)\beta^5 + (\alpha - \beta)\gamma^5 \\ &= (\beta - \gamma)\alpha^5 - (\beta^5 - \gamma^5)\alpha + \beta\gamma(\beta^4 - \gamma^4) \\ &= (\beta - \gamma)\left\{\alpha^5 + (\beta^4 + \beta^3\gamma + \beta^2\gamma^2 + \beta\gamma^3 + \gamma^4)\alpha + \beta\gamma(\beta^3 + \beta^2\gamma + \beta\gamma^2 + \gamma^3)\right\} \\ &= (\beta - \gamma)\left\{\alpha^2 - (\beta + \gamma)\alpha + \beta\gamma\right\}\\ &\qquad\times\left\{\alpha^3 + (\beta + \gamma)\alpha^2 + (\beta^2 + \beta\gamma + \gamma^2)\alpha + (\beta^3 + \beta^2\gamma + \beta\gamma^2 + \gamma^3)\right\} \\ &= -(\alpha - \beta)(\beta - \gamma)(\gamma - \alpha)\\ & \qquad \times\left\{(\alpha^3 + \beta^3 + \gamma^3) + (\alpha^2\beta + \alpha^2\gamma + \beta^2\gamma + \beta^2\alpha + \gamma^2\alpha + \gamma^2\beta) + \alpha\beta\gamma\right\} \end{align*} }$

ここで

　　 ${ \displaystyle \begin{align*} \alpha^3 + \beta^3 + \gamma^3 &= (\alpha + \beta + \gamma) (\alpha^2 + \beta^2 + \gamma^2 - \alpha\beta - \beta\gamma - \gamma\alpha) + 3\alpha\beta\gamma \\ &= 1\cdot (3 - (-1)) + 3\cdot 1 \\ &= 7 \end{align*} }$

また

　　 ${ \displaystyle \begin{align*} (\alpha + \beta + \gamma)^3 &= \alpha^3 + \beta^3 + \gamma^3 + 6\alpha\beta\gamma \\ & \qquad + 3(\alpha^2\beta + \alpha^2\gamma + \beta^2\gamma + \beta^2\alpha + \gamma^2\alpha + \gamma^2\beta) \end{align*} }$

より

　　 ${ \displaystyle \begin{align*} \alpha^2\beta + \alpha^2\gamma + \beta^2\gamma + \beta^2\alpha + \gamma^2\alpha + \gamma^2\beta = -4 \end{align*} }$

なので

　　 ${ \displaystyle \begin{align*} T_4 &= (\alpha^3 + \beta^3 + \gamma^3) + (\alpha^2\beta + \alpha^2\gamma + \beta^2\gamma + \beta^2\alpha + \gamma^2\alpha + \gamma^2\beta) + \alpha\beta\gamma \\ &= 7 - 4 + 1 \\ &= 4 \end{align*} }$

といった感じで、だいたい一般項はあってそう。　また、一般項が ${ \alpha,\,\beta,\,\gamma }$ の定まった次数での対称式でどのように表されるかもそんなに難しくなく出せそうですね。　それを導けばもっと簡単に一般項を計算できるかも。　というか、大学入試とかで計算問題として出題されそうな計算が沢山でてきたヨ。　受験生は試しにやってみてはいかがでしょう？