4

拡張されたフィボナッチ数列(k-ナッチ数)の一般項を線形代数を使って求める

365
0
$$$$

はじめに

Mathlogで フィボナッチ数を一般化したk-ナッチ数の一般項 という記事を拝見し、自分も同じようなことを別のアプローチからやっていたことを思い出したので、書いてみました。厳密なものではないのでその点はご承知ください。また、ヴァンデルモンド行列式を使った式変形が面白いので、そこだけでもぜひご覧ください。

問題

拡張フィボナッチ数の一般項

$k$を2以上の自然数として、次の漸化式を満たす数列$\{a_n\}$を拡張フィボナッチ数列と定義する。
\begin{align*} \begin{cases} a_{n+k} &= a_{n+k-1}+a_{n+k-2}+\dots+a_{n}\\ &=\displaystyle \sum_{i=n}^{n+k-1}a_i \\ a_0 &= a_1 = \dots = a_{k-2} = 0\\a_{k-1} &= 1 \end{cases} \end{align*}
拡張フィボナッチ数の一般項を求めよ。

解答

基底を求める

漸化式を満たす実数の数列のなす空間を$V$とする。

数列$\{ a_n \}$の最初の$k$$a_0,a_1,\dots,a_{k-1}$ が与えられているので、$n\geq k$において数列 $\{ a_n \}$ は一意に定まる。$k$個のベクトルを次のように定義する。

\begin{align*} \boldsymbol{v_0}&=\{\overbrace{1,0,0,\dots,0}^{k個},1,\dots \}\\ \boldsymbol{v_1}&=\{0,1,0,\dots,0,1,\dots \}\\ & \vdots \\ \boldsymbol{v_{k-1}}&=\{0,0,0,\dots,1,1,\dots\} \end{align*}

$c_0,c_1,\dots,c_{k-1}$に対して、$c_0\boldsymbol{v_0}+c_1\boldsymbol{v_1}+\dots+c_{k-1}\boldsymbol{v_{k-1}}=\boldsymbol{0}$が成り立ったとすると、
\begin{align*} c_0\boldsymbol{v_0}+c_1\boldsymbol{v_1}+\dots+c_{k-1}\boldsymbol{v_{k-1}}&=c_0\{1,0,0,\dots \}+c_1\{0,1,0,\dots \}+\dots+c_{k-1}\{0,\dots,0,1,\dots \}\\ &=\{c_0,c_1,\dots,c_{k-1},\dots \}\\ &=\{0,0,\dots,0,\dots \} \end{align*}
となるので、$c_0=c_1=\dots =c_{k-1}=0$ である。よって、$\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$は一次独立である。
\begin{align*} \boldsymbol{a}= \{ a_0,a_1,\dots,a_{k-1},\dots \} \end{align*}
$V$の勝手な元とすると、
\begin{align*} \boldsymbol{a}&=\{ a_0,0,0,\dots \}+\{0,a_1,0,\dots \} +\dots+\{0,\dots,0,a_{k-1},\dots \} \\ &=a_0\{1,0,0,\dots \}+a_1\{0,1,0,\dots \}+\dots+a_{k-1}\{0,\dots,0,1,\dots \} \\ &=a_0\boldsymbol{v_0}+a_1\boldsymbol{v_1}+\dots+a_{k-1}\boldsymbol{v_{k-1}} \end{align*}

となり、$\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$ の一次結合で表せる。よって、$\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$$V$を生成する。

以上より、$\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$ は一次独立かつ$V$を生成するので、$V$の基底である。

$\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$$V$の基底である。

線形写像の定義

定義語句(任意)

写像 $f:V\rightarrow V$を以下のように定義する。

\begin{align*} f\left(\{ a_n\}_{n=0}^{\infty}\right)=\{ a_n\}_{n=1}^{\infty} \end{align*}

$\boldsymbol{a}=\{ a_0,a_1,a_2,\dots \} \in V$のとき、$f(\boldsymbol{a})=\{ a_1,a_2,a_3,\dots \}$も漸化式を満たすので、$f(\boldsymbol{a})\in V$である。

\begin{align*} \boldsymbol{a}=\{ a_n\}_{n=0}^{\infty}\in V \\ \boldsymbol{b}=\{ b_n\}_{n=0}^{\infty}\in V \\ \end{align*}
とすると、定数 $c$ に対して、

\begin{align*} f(\boldsymbol{a}+\boldsymbol{b})=f(\{ a_n+b_n\}_{n=0}^{\infty})=\{ a_n+b_n\}_{n=1}^{\infty}=\{ a_n\}_{n=1}^{\infty}+\{ b_n\}_{n=1}^{\infty}=f(\boldsymbol{a})+f(\boldsymbol{b})\\ f(c\boldsymbol{a})=f(c\{ a_n\}_{n=0}^{\infty})=c\{ a_n\}_{n=1}^{\infty}=cf(\boldsymbol{a}) \end{align*}
が成り立つので、$f$$V$の線形変換である。

$f$$V$の線形変換である。

漸化式を行列で表現

$\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$ に関して、

\begin{align*} f(\boldsymbol{v_0})&=\{0,0,\dots,0,1,\dots \}=\boldsymbol{v_{k-1}}\\ f(\boldsymbol{v_1})&=\{1,0,\dots,0,1,\dots \}=\boldsymbol{v_0}+\boldsymbol{v_{k-1}}\\ f(\boldsymbol{v_2})&=\{0,1,\dots,0,1,\dots \}=\boldsymbol{v_1}+\boldsymbol{v_{k-1}}\\ \vdots \\ f(\boldsymbol{v_{k-1}})&=\{0,0,\dots,1,1,\dots \}=\boldsymbol{v_{k-2}}+\boldsymbol{v_{k-1}} \end{align*}
なので、

\begin{align*} [f(\boldsymbol{v_0})\quad f(\boldsymbol{v_1})\quad f(\boldsymbol{v_2}) \quad \cdots \quad f(\boldsymbol{v_{k-1}})]= [\boldsymbol{v_0}\ \boldsymbol{v_1}\ \boldsymbol{v_2} \cdots \boldsymbol{v_{k-1}}] \begin{bmatrix} 0 & 1 & 0 & 0 & \cdots & 0\\ 0 & 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1\\ 1 & 1 & 1 & 1 & \cdots & 1 \end{bmatrix} \end{align*}
と表せる。よって、$f$の基底 $\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$ に関する表現行列は、

\begin{align*} \overbrace{ \begin{bmatrix} 0 & 1 & 0 & 0 & \cdots & 0\\ 0 & 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1\\ 1 & 1 & 1 & 1 & \cdots & 1 \end{bmatrix} }^{k行k列} \end{align*}
である。この表現行列を$A$とする。

$f$の基底 $\boldsymbol{v_0},\boldsymbol{v_1},\dots,\boldsymbol{v_{k-1}}$ に関する表現行列は、
\begin{align*} A = \overbrace{ \begin{bmatrix} 0 & 1 & 0 & 0 & \cdots & 0\\ 0 & 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1\\ 1 & 1 & 1 & 1 & \cdots & 1 \end{bmatrix} }^{k行k列} \end{align*}
である。

固有値と公比の関係

\begin{align*} \boldsymbol{p}=\{ r^{n} \}_{n=0}^{\infty}=\{1,r,r^2,\dots \} \end{align*}
$V$に属したとすると、

\begin{align*} f(\boldsymbol{p})=f(\{ r^{n} \}_{n=0}^{\infty})=\{ r^{n} \}_{n=1}^{\infty}=\{ r^{n+1} \}_{n=0}^{\infty}=r\{ r^{n} \}_{n=0}^{\infty}=r\boldsymbol{p} \end{align*}
より、$\boldsymbol{p}$は固有値$r$の固有ベクトルになる。逆に、上の式から$f$の固有値 $r$の固有ベクトルは、公比$r$の等比数列になることも分かる。よって、公比と固有値は等しいとわかる。

等比数列の公比と固有値は等しい。

固有値を求める

$f$の固有値を求める。$A$の固有多項式は、$I$を単位行列として、

\begin{align*} \varphi_k(\lambda)&=|A-\lambda I|\\ &=\begin{vmatrix} -\lambda & 1 & 0 & 0 & \cdots & 0& 0\\ 0 & -\lambda & 1 & 0 & \cdots & 0& 0\\ 0 & 0 & -\lambda & 1 & \cdots & 0& 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & 0 & 0 & \cdots & -\lambda & 1\\ 1 & 1 & 1 & 1 & \cdots & 1 & 1-\lambda \end{vmatrix} \end{align*}
ここで、$\lambda=1$と仮定すると、
\begin{align*} \varphi_k(1) &=\begin{vmatrix} -1 & 1 & 0 & 0 & \cdots & 0& 0\\ 0 & -1 & 1 & 0 & \cdots & 0& 0 \\ 0 & 0 & -1 & 1 & \cdots & 0& 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & 0 & 0 & \cdots & -1 & 1\\ 1 & 1 & 1 & 1 & \cdots & 1 & 0 \end{vmatrix}\\ &=\begin{vmatrix} -1 & 0 & 0 & 0 & \cdots & 0& 0\\ 0 & -1 & 1 & 0 & \cdots & 0& 0\\ 0 & 0 & -1 & 1 & \cdots & 0& 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & 0 & 0 & \cdots & -1 & 1\\ 1 & 2 & 1 & 1 & \cdots & 1 & 0 \end{vmatrix}\quad (\mbox{1列目を2列目に加える})\\ &=\cdots \quad (\mbox{$i-1$列目を$i$列目に加える})\\ &=\begin{vmatrix} -1 & 0 & 0 & 0 & \cdots & 0& 0\\ 0 & -1 & 0 & 0 & \cdots & 0& 0\\ 0 & 0 & -1 & 0 & \cdots & 0& 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & 0 & 0 & \cdots & -1 & 0\\ 1 & 2 & 3 & 4 & \cdots & k-1 & k \end{vmatrix}\quad (\mbox{$k-1$列目を$k$列目に加える})\\ &=\begin{vmatrix} -1 & 0 & 0 & 0 & \cdots & 0& 0\\ 0 & -1 & 0 & 0 & \cdots & 0& 0\\ 0 & 0 & -1 & 0 & \cdots & 0& 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & 0 & 0 & \cdots & -1 & 0\\ 0 & 0 & 0 & 0 & \cdots & 0 & k \end{vmatrix}\quad (\mbox{$i$行目$\times i$を$k$行目に加える})\\ &=(-1)^{k-1}k \end{align*}
より、$\varphi_k(1)\neq 0$なので、$\lambda=1$は固有値ではない。

1列目に沿って余因子展開すると、

\begin{align*} \varphi_k&=(-1)^{1+1}(-\lambda) \begin{vmatrix} -\lambda & 1 & 0 & \cdots & 0\\ 0 & -\lambda & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ 1 & 1 & 1 & \cdots & 1-\lambda \end{vmatrix} + (-1)^{k+1}\cdot 1 \begin{vmatrix} 1 & 0 & 0 & \cdots & 0\\ -\lambda & 1 & 0 & \cdots & 0\\ 0 & -\lambda & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ \end{vmatrix} \\ &=-\lambda \varphi_{k-1} - (-1)^{k}\cdot 1\cdot 1\\ &=-\lambda \varphi_{k-1} - (-1)^{k} \end{align*}
と漸化式のように表せる。両辺を$(-1)^k$で割ると、

\begin{align*} \frac{\varphi_k}{(-1)^k} &= -\lambda \frac{\varphi_{k-1}}{(-1)^k} - 1\\ &=\lambda \frac{\varphi_{k-1}}{(-1)^{k-1}} - 1 \end{align*}
$b_k = \displaystyle \frac{\varphi_k}{(-1)^k}$とおくと、$\lambda \neq 1$より、

\begin{align*} b_k &= \lambda b_{k-1} - 1\\ b_k - \frac{1}{\lambda - 1} &= \lambda \left(b_{k-1} - \frac{1}{\lambda - 1}\right)\\ &=\cdots \\ &= \lambda^{k-2}\left(b_{2} - \frac{1}{\lambda - 1}\right) \end{align*}
であり、初項は、

\begin{align*} b_2- \frac{1}{\lambda - 1} &= \displaystyle \frac{\varphi_2}{(-1)^2} - \frac{1}{\lambda - 1}\\ &=\varphi_2 - \frac{1}{\lambda - 1}\\ &=\begin{vmatrix} -\lambda & 1 \\ 1 & 1-\lambda \end{vmatrix}- \frac{1}{\lambda - 1}\\ &=\lambda^2 - \lambda - 1- \frac{1}{\lambda - 1}\\ &=\frac{\lambda^3-2\lambda^2}{\lambda-1} \end{align*}
よって、

\begin{align*} b_k &- \frac{1}{\lambda - 1}= \lambda^{k-2} \frac{\lambda^3-2\lambda^2}{\lambda-1}\\ b_k &= \frac{\lambda^{k+1}-2\lambda^k}{\lambda-1} + \frac{1}{\lambda - 1} \\ &= \frac{\lambda^{k+1}-2\lambda^k+1}{\lambda-1}\\ &=\lambda^k - \lambda^{k-1} - \lambda^{k-2} - \dots - \lambda^2 - \lambda - 1\quad (\because 組み立て除法)\\ &=\lambda^k - \sum_{i=0}^{k-1}\lambda^i\\ &=-\sum_{i=0}^{k}(-1)^{\delta_{ik}}\lambda^i \end{align*}
が導出された。ただし、$\delta_{ij}$はクロネッカーのデルタである。また、方程式 $\varphi_k(\lambda) = (-1)^k b_k = 0$ は、$b_k = 0$$-b_k=0$と同値である。すなわち、
\begin{align*} g(\lambda) = (\lambda-1)b_k = \lambda^{k+1}-2\lambda^k+1=0 \end{align*}
$\lambda=1$以外の$k$個の解が求める固有値である。しかし、これは簡単に求めることはできないので、計算機などを使って求める。

$A$の固有値は、方程式$g(\lambda)=\lambda^{k+1}-2\lambda^k+1=0$$\lambda=1$以外の$k$個の解

$k$ 個の解を $\lambda_0,\lambda_1,\dots,\lambda_{k-1}$とする。また、それぞれの解に対応する固有ベクトルである等比数列を
\begin{align*} \boldsymbol{u_0}=\{ \lambda_0^{n} \}_{n=0}^{\infty}\\ \boldsymbol{u_1}=\{ \lambda_1^{n} \}_{n=0}^{\infty}\\ \vdots \\ \boldsymbol{u_{k-1}}=\{ \lambda_{k-1}^{n} \}_{n=0}^{\infty} \end{align*}
と定義する。$\boldsymbol{u_0},\boldsymbol{u_1},\dots,\boldsymbol{u_{k-1}}$$V$に属する。

ここで、$g(\lambda)=0$が重解$\alpha\neq 1$を持つと仮定する。このとき、$g(\lambda)=(\lambda-\alpha)^2h(\lambda)$と表せる。
\begin{align*} \frac{\mathrm{d} g(\lambda)}{\mathrm{d}\lambda} &= 2(\lambda-\alpha)h(\lambda)+(\lambda-\alpha)^2\frac{\mathrm{d}h(\lambda)}{\mathrm{d}\lambda}\\ &= (\lambda-\alpha)\left(2h(\lambda)+(\lambda-\alpha)\frac{\mathrm{d}h(\lambda)}{\mathrm{d}\lambda}\right) \end{align*}
より、$\alpha$$\displaystyle \frac{\mathrm{d}g(\lambda)}{\mathrm{d}\lambda}=0$でも解となる。

\begin{align*} \frac{\mathrm{d}g(\lambda)}{\mathrm{d}\lambda} &= (k+1)\lambda^k-2k\lambda^{k-1}\\ &= \{(k+1)\lambda-2k\}\lambda^{k-1}\\ &= 0 \end{align*}
より、解は$\lambda = \displaystyle \frac{2k}{k+1},0$である。
\begin{align*} g\left(\frac{2k}{k+1}\right) &= \left(\frac{2k}{k+1}\right)^{k+1}-2\left(\frac{2k}{k+1}\right)^k+1\\ &= \frac{(2k)^{k+1}-2(2k)^k(k+1)+(k+1)^{k+1}}{(k+1)^{k+1}}\\ &= \frac{2^{k+1}k^{k+1}-2^{k+1}k^k(k+1)+(k+1)^{k+1}}{(k+1)^{k+1}}\\ &= \frac{2^{k+1}k^{k+1}-2^{k+1}k^{k+1}-2^{k+1}k^{k}+(k+1)^{k+1}}{(k+1)^{k+1}}\\ &= \frac{-2^{k+1}k^{k}+(k+1)^{k+1}}{(k+1)^{k+1}}\\ &= 1 - \frac{2}{k+1}\left(\frac{2k}{k+1}\right)^k \end{align*}

$k>1$では、$2k>k+1$が成り立ち、$g(2k/(k+1))$$k>1$では常に負になるので、$g(\lambda)=0$の解ではない。また、$g(0)=1$なので$\lambda=0$$g(\lambda)=0$の解ではない。よって、$g(\lambda)=0$$\lambda=1$以外の$k$個の解$\lambda_0,\lambda_1,\dots,\lambda_{k-1}$は全て異なる。

方程式$g(\lambda)=\lambda^{k+1}-2\lambda^k+1=0$$\lambda=1$以外の$k$個の解$\lambda_0,\lambda_1,\dots,\lambda_{k-1}$は全て異なる。

$\lambda_0,\lambda_1,\dots,\lambda_{k-1}$ が全て異なることより、$f$の相異なる固有値に対応する固有ベクトルなので一次独立である。また、$\dim V=k$ である。よって、$\boldsymbol{u_0},\boldsymbol{u_1},\dots,\boldsymbol{u_{k-1}}$$V$の基底となる。

$\boldsymbol{u_0},\boldsymbol{u_1},\dots,\boldsymbol{u_{k-1}}$$V$の基底である。

係数の決定

以上より、ある $c_0,c_1,\dots,c_{k-1}$が存在して、

\begin{align*} \boldsymbol{a_n}=c_0\boldsymbol{u_0}+c_1\boldsymbol{u_1}+\dots+c_{k-1}\boldsymbol{u_{k-1}} \end{align*}
と表せるので、

\begin{align*} \boldsymbol{a_n}&=c_0\boldsymbol{u_0}+c_1\boldsymbol{u_1}+\dots+c_{k-1}\boldsymbol{u_{k-1}}\\ \Leftrightarrow \{a_0,a_1,\dots,a_{k-1},\dots \}&=c_0\{ \lambda_0^{n} \}_{n=0}^{\infty}+c_1\{ \lambda_1^{n} \}_{n=0}^{\infty}+\dots+c_{k-1}\{ \lambda_{k-1}^{n} \}_{n=0}^{\infty}\\ \Leftrightarrow \{0,0,\dots,1,\dots \}&=c_0\{ 1,\lambda_0,\dots,\lambda_0^{k-1},\dots \}+c_1\{1,\lambda_1,\dots,\lambda_1^{k-1},\dots \}+\dots+c_{k-1}\{ 1,\lambda_{k-1},\dots,\lambda_{k-1}^{k-1},\dots\} \\ \Leftrightarrow \{0,0,\dots,1,\dots \}&=\{ c_0+c_1+\dots+c_{k-1},\ c_0\lambda_0+c_1\lambda_1+\dots+c_{k-1}\lambda_{k-1},\dots, c_0\lambda_0^{k-1}+c_1\lambda^{k-1}+\dots+c_{k-1}\lambda^{k-1}, \dots\} \end{align*}
これを行列で表現すると、

\begin{align*} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1\\ \lambda_0 & \lambda_1 & \lambda_2 & \cdots & \lambda_{k-1} \\ \lambda_0^2 & \lambda_1^2 & \lambda_2^2 & \cdots & \lambda_{k-1}^2\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \lambda_0^{k-1} & \lambda_1^{k-1} & \lambda_2^{k-1} & \cdots & \lambda_{k-1}^{k-1} \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ c_3 \\ \vdots \\ c_{k-1} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix} \end{align*}

ヴァンデルモンド行列式

左の行列の行列式は、ヴァンデルモンド行列式 $V_k$ であり、
\begin{align*} V_k = \begin{vmatrix} 1 & 1 & 1 & \cdots & 1\\ \lambda_0 & \lambda_1 & \lambda_2 & \cdots & \lambda_{k-1} \\ \lambda_0^2 & \lambda_1^2 & \lambda_2^2 & \cdots & \lambda_{k-1}^2\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \lambda_0^{k-1} & \lambda_1^{k-1} & \lambda_2^{k-1} & \cdots & \lambda_{k-1}^{k-1} \end{vmatrix} =\prod_{0\leq i < j \leq k-1}\big(\lambda_j - \lambda_i\big) \end{align*}
である。

クラメルの公式を用いると、$0\leq m\leq k-1$ に対して

\begin{align*} c_m &= \frac{\begin{vmatrix} 1 & 1 & \cdots & 1 & 0 & 1 & \cdots & 1\\ \lambda_0 & \lambda_1 & \cdots & \lambda_{m-1} & 0 & \lambda_{m+1} & \cdots & \lambda_{k-1} \\ \lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2 & 0 & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \lambda_0^{k-1} & \lambda_1^{k-1} & \cdots & \lambda_{m-1}^{k-1} & 1 & \lambda_{m+1}^{k-1} & \cdots & \lambda_{k-1}^{k-1} \end{vmatrix}}{V_k}\\ &=\frac{(-1)^{m}\begin{vmatrix} 0 & 1 & 1 & \cdots & 1 & 1 & \cdots & 1\\ 0 & \lambda_0 & \lambda_1 & \cdots & \lambda_{m-1} & \lambda_{m+1} & \cdots & \lambda_{k-1} \\ 0 & \lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2 & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\ 0 & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \lambda_0^{k-1} & \lambda_1^{k-1} & \cdots & \lambda_{m-1}^{k-1} & \lambda_{m+1}^{k-1} & \cdots & \lambda_{k-1}^{k-1} \end{vmatrix}}{V_k}\quad (\because 列をm回交換)\\ &=\frac{(-1)^{m+k-1}\begin{vmatrix} 1 & \lambda_0^{k-1} & \lambda_1^{k-1} & \cdots & \lambda_{m-1}^{k-1} & \lambda_{m+1}^{k-1} & \cdots & \lambda_{k-1}^{k-1}\\ 0 & 1 & 1 & \cdots & 1 & 1 & \cdots & 1\\ 0 & \lambda_0 & \lambda_1 & \cdots & \lambda_{m-1} & \lambda_{m+1} & \cdots & \lambda_{k-1} \\ 0 & \lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2 & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\ 0 & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \lambda_0^{k-2} & \lambda_1^{k-2} & \cdots & \lambda_{m-1}^{k-2} & \lambda_{m+1}^{k-2} & \cdots & \lambda_{k-1}^{k-2} \end{vmatrix}}{V_k}\quad (\because 行をk-1回交換)\\ &=\frac{(-1)^{m+k-1}\begin{vmatrix} 1 & 1 & \cdots & 1 & 1 & \cdots & 1\\ \lambda_0 & \lambda_1 & \cdots & \lambda_{m-1} & \lambda_{m+1} & \cdots & \lambda_{k-1} \\ \lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2 & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \lambda_0^{k-2} & \lambda_1^{k-2} & \cdots & \lambda_{m-1}^{k-2} & \lambda_{m+1}^{k-2} & \cdots & \lambda_{k-1}^{k-2} \end{vmatrix}}{V_k}\\ &=\frac{(-1)^{m+k-1}\displaystyle \prod_{0\leq i < j \leq k-1かつi\neq mかつj \neq m}\big(\lambda_j - \lambda_i\big)}{\displaystyle \prod_{0\leq i < j \leq k-1}\big(\lambda_j - \lambda_i\big)}\quad (\because ヴァンデルモンド行列式)\\ &=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < j \leq k-1かつ(i=mまたはj=m)}\big(\lambda_j - \lambda_i\big)}\\ &=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}\big(\lambda_j - \lambda_m\big)}\\ &=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}(-1)\big(\lambda_m - \lambda_j\big)}\\ &=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)(-1)^{k-m-1}\prod_{m < j \leq k-1}\big(\lambda_m - \lambda_j\big)}\\ &=\frac{(-1)^{(m+k-1)-(k-m-1)}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}\big(\lambda_m - \lambda_j\big)}\\ &=\frac{(-1)^{2m}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}\big(\lambda_m - \lambda_j\big)}\\ &=\frac{1}{\displaystyle \prod_{0\leq i < m,m< i\leq k-1}\big(\lambda_m - \lambda_i\big)} \end{align*}
が求められる。

以上より、

\begin{align*} \boldsymbol{a_n} &= c_0 \boldsymbol{u_0} + c_1 \boldsymbol{u_1} +\dots+ c_{k-1} \boldsymbol{u_{k-1}}\\ &=\left\{ \frac{\lambda_0^n}{\displaystyle \prod_{1\leq i \leq k-1}\big(\lambda_0 - \lambda_i\big)} + \frac{\lambda_1^n}{\displaystyle \prod_{0\leq i <1,1 < j\leq k-1}\big(\lambda_1 - \lambda_i\big)} +\dots+ \frac{\lambda_{k-1}^n}{\displaystyle \prod_{0\leq i \leq k-2}\big(\lambda_{k-1} - \lambda_i\big)}\right\}_{n=0}^{\infty}\\ &=\left\{\sum_{i=0}^{k-1}\frac{\lambda_i^n}{\displaystyle \prod_{0\leq j < i, i< j\leq k-1}\big(\lambda_i - \lambda_j\big)}\right\}_{n=0}^{\infty} \end{align*}

である。

一般項

以上より、一般項を求めることができた。

拡張フィボナッチ数列の一般項

$S=\{0,1,2,\dots,k-1\}$とする。$i\in S$に対して、$\lambda_i$$\lambda^{k+1}-2\lambda^k+1=0$$\lambda=1$以外の$k$個の解とする。$n\geq 0$に対して、拡張フィボナッチ数列の一般項は、

\begin{align*} a_n &= \sum_{i=0}^{k-1}\frac{\lambda_i^n}{\displaystyle \prod_{0\leq j < i, i< j\leq k-1}\big(\lambda_i - \lambda_j\big)}\\ &= \sum_{i\in S}\frac{\lambda_i^n}{\displaystyle \prod_{j\in S\backslash \{i\}}\big(\lambda_i - \lambda_j\big)}\\ \end{align*}
である。

投稿日:20201230

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中