Finden Sie den allgemeinen Term der erweiterten Fibonacci-Sequenz (k-Bonatch-Sequenz: Summe der unmittelbar vorhergehenden k Terme) mit linearer Algebra und Python

(Es scheint, dass die Formel möglicherweise nicht von einem Smartphone angezeigt wird. In diesem Fall sehen Sie sie bitte von einem PC usw. aus. Es tut mir leid.)

Was ist eine erweiterte Fibonacci-Sequenz?

Die Fibonacci-Sequenz ist eine Sequenz, die die beiden vorherigen Begriffe hinzufügt, um den nächsten Begriff zu erstellen. Als Ausdruck ausgedrückt

\begin{cases}
\begin{align}
a_{n+2} &= a_{n+1} + a_{n}\\ 
a_0 &= 0\\
a_1 &= 1
\end{align}
\end{cases}

Es wird sein. Die erweiterte Fibonacci-Sequenz ist die Erweiterung auf den nächsten Term, der die Summe der vorherigen $ k $ -Terms ist. Ich habe nach dem Namen gesucht, aber ich konnte ihn nicht finden, also nenne ich ihn $ k $ -Bonatch-Sequenz. Als Ausdruck ausgedrückt

\begin{cases}
\begin{align}
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{align}
\end{cases}

Es wird sein. Im vorherigen Artikel (Ermitteln der allgemeinen Begriffe einer Tribonatch-Sequenz mit linearer Algebra und Python) haben wir uns mit einer Tribonatch-Sequenz mit $ k = 3 $ befasst. Dieses Mal werden wir es erweitern.

Vorbereitung

(Es ist fast dasselbe wie Berechnen Sie den allgemeinen Term der Tribonacci-Sequenz mit linearer Algebra und Python, sodass Sie ihn überspringen können.)

Sei $ V $ der Raum, der durch eine Folge von reellen Zahlen gebildet wird, die den allmählichen Ausdruck erfüllen. Bei dem ersten $ k $ Term $ a_0, a_1, \ dots, a_ {k-1} $ in der Folge $ \ {a_n } $ ist die Folge $ \ {a_n \ in $ n \ geq k $ } $ Ist eindeutig bestimmt.

\begin{align}
\boldsymbol{v_0}&=\{\overbrace{1,0,0,\dots,0}^{k Stück},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}

Wird besorgt. Für $ c_0, c_1, \ dots, c_ {k-1} \ in \ mathbb {C} $, $ c_0 \ boldsymbol {v_0} + c_1 \ boldsymbol {v_1} + \ dots + c_ {k-1} Wenn \ boldsymbol {v_ {k-1}} = \ boldsymbol {0} $ gilt,

c_0\{1,0,0,\dots \}+c_1\{0,1,0,\dots \}+\dots+c_{k-1}\{0,\dots,1,\dots \}\\=\{c_0,c_1,\dots,c_{k-1},\dots \}=\{0,0,\dots,0,\dots \}

Daher ist $ c_0 = c_1 = \ dots = c_ {k-1} = 0 $. Daher ist bekannt, dass $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ linear unabhängig sind.

Nächster,

\boldsymbol{a}= \{ a_0,a_1,\dots,a_{k-1},\dots \}

Ist eine willkürliche Quelle von $ 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}

Es kann durch eine lineare Kombination von $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ dargestellt werden. $ \ Boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ erzeugen also $ V $.

Aus dem oben Gesagten ist $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ linear unabhängig und erzeugt $ V $, also ist es die Basis von $ V $.

Ordnen Sie nun $ f: V \ rightarrow V $ zu

f(\{ a_n\}_{n=0}^{\infty})=\{ a_n\}_{n=1}^{\infty}

Wird besorgt. $ \ boldsymbol {a} = \ {a_0, a_1, a_2, \ dots } \ in V $, $ f (\ boldsymbol {a}) = \ {a_1, a_2, a_3, \ dots } $ Es erfüllt den allmählichen Ausdruck, also ist es $ f (\ boldsymbol {a}) \ in V $.

\boldsymbol{a}=\{ a_n\}_{n=0}^{\infty}\in V \\
\boldsymbol{b}=\{ b_n\}_{n=0}^{\infty}\in V \\
c\in \mathbb{C}

Dann

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})

Ist wahr, also ist $ f $ eine lineare Transformation von $ V $.

Darstellung des allmählichen Ausdrucks als Matrix

In Bezug auf $ \ 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}

Damit

[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}

Kann ausgedrückt werden als. Daher ist die Repräsentationsmatrix für die Basis $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ von $ f $

\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 Zeilen k Spalten}

ist. Diese Repräsentationsmatrix sei $ A $.

Beziehung zwischen Eigenwert und gemeinsamem Verhältnis

(Es ist dasselbe wie Berechnung des allgemeinen Terms der Tribonacci-Sequenz mit linearer Algebra und Python, sodass Sie ihn überspringen können.)

\boldsymbol{p}=\{ r^{n} \}_{n=0}^{\infty}=\{1,r,r^2,\dots \}

Gehört zu $ V $

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}

Daher wird $ \ boldsymbol {p} $ ein Eigenvektor mit einem Eigenwert von $ r $. Umgekehrt ist aus der obigen Gleichung ersichtlich, dass der Eigenvektor des Eigenwerts $ r $ von $ f $ eine Folge mit gleichem Verhältnis des gemeinsamen Verhältnisses $ r $ ist. Daher wissen wir, dass das gemeinsame Verhältnis und der Eigenwert gleich sind.

Finden Sie den eindeutigen Wert

Finden Sie den eindeutigen Wert von $ f $. Die Eigenpolynese von $ A $ verwendet $ I $ als Einheitsmatrix.

\begin{align}
\varphi_k(\lambda)&=|A-\lambda I|\\
&=\begin{vmatrix}
-\lambda & 1 & 0 & 0 & \cdots & 0\\
0 & -\lambda & 1 & 0 & \cdots & 0\\
0 & 0 & -\lambda & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1\\
1 & 1 & 1 & 1 & \cdots & 1-\lambda
\end{vmatrix}
\end{align}

Erweitern der Cofaktoren entlang der ersten Spalte

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

Kann als allmählicher Ausdruck ausgedrückt werden. Teilen Sie beide Seiten durch $ (-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}

Wenn Sie $ b_k = \ displaystyle \ frac {\ varphi_k} {(-1) ^ k} $ setzen,

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

Und der erste Begriff ist

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

ist. Deshalb,

\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 (\weil Montagemethode)
\end{align}

Abgeleitet wurde. Sie können sehen, dass die Gleichung $ \ varphi_k (\ lambda) = (-1) ^ k b_k = 0 $ $ b_k = 0 $ entspricht.

$ B_k = 0 $ kann jedoch nicht einfach gelöst werden. In einem späteren Kapitel werden wir einen Computer verwenden, um ihn numerisch zu berechnen.

Wenn $ k $ von Lösungen $ \ lambda_0, \ lambda_1, \ dots, \ lambda_ {k-1} $ sind, dann sind die jeder Lösung entsprechenden Eigenvektoren

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

Gehört zu $ V $. Diese sind linear unabhängig, da sie Eigenvektoren sind, die unterschiedlichen Eigenwerten von $ f $ entsprechen, vorausgesetzt, dass $ \ lambda_0, \ lambda_1, \ dots, \ lambda_ {k-1} $ alle unterschiedlich sind. Auch $ \ dim V = k $. Daher ist $ \ boldsymbol {u_0}, \ boldsymbol {u_1}, \ dots, \ boldsymbol {u_ {k-1}} $ die Basis von $ V $.

Bestimmung des Koeffizienten

Aus dem Obigen ergibt sich ein bestimmtes $ c_0, c_1, \ dots, c_ {k-1} $,

\boldsymbol{a_n}=c_0\boldsymbol{u_0}+c_1\boldsymbol{u_1}+\dots+c_{k-1}\boldsymbol{u_{k-1}}

Weil es ausgedrückt werden kann als

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

Dies als Matrix ausdrücken,

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

ist. Der Matrixausdruck für die linke Matrix ist der Van-der-Monde-Matrixausdruck $ V_k $,

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)

Ist bekannt als. Verwenden Sie die Cramel-Formel für $ 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 (\weil die Säule m-mal ausgetauscht wird)\\
&=\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 (\weil Linie k-Einmal austauschen)\\
&=\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 und ich\neq m und 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 (\weil Van der Monde Matrixformel)\\
&=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < j \leq k-1 und(i=m oder 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}

Wird benötigt.

Von Oben,

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

Damit

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)}

Wurde geführt.

Implementierungsbeispiel und Vergleich des Berechnungsbetrags

Bisher kennen wir die Form des allgemeinen Begriffs, aber wir kennen die spezifischen Werte von $ \ lambda_0, \ lambda_1, \ dots, \ lambda_ {k-1} $ nicht. Da es für Gleichungen vom Grad 5 oder höher nicht immer eine algebraische Lösung gibt, wird eine numerische Lösung erhalten. Auch dieses Mal werden wir Pythons Numpy-Bibliothek verwenden, um sie zu finden. Berücksichtigen Sie die folgenden Punkte.

Angesichts der natürlichen Zahlen $ K, N $. $ K $ -Print den $ N $ Term der Bonatch-Sequenz.

Implementierungsbeispiel 1: Berechnen Sie wie definiert

teigi.py

k, n = map(int, input().split())

a = [0] * max(n+1,k)
a[k-1] = 1

for i in range(k,n+1):
    for j in range(1,k+1):
        a[i] += a[i-j]

print(a[n])

Wenn Sie gemäß der Definition berechnen, müssen Sie $ K $ mal für jedes $ i (K \ leq i \ leq N) $ addieren, also $ O (K (NK)) = O (KN) $. Ich werde.

Implementierungsbeispiel 2: Verwenden Sie allgemeine Begriffe

ippankou.py

import numpy as np
import warnings 
warnings.filterwarnings('ignore')       #Bei der Berechnung komplexer Zahlen tritt eine Warnung auf. Löschen Sie sie daher.

k, n = map(int, input().split())

equation = [1]
for i in range(k):
    equation.append(-1)     # equation = [1, -1, -1, ... , -1] = lambda^k - lambda^{k-1} - ... - lambda -1 = 0

lam = np.roots(equation)     # lambda_i

a = 0

for i in range(k):
    prod = 1
    for j in range(k):
        if j != i:
            prod *= lam[i] - lam[j]
    a += np.power(lam[i],n) / prod
    
        

print(int(round(a)))

Mit allgemeinen Begriffen berechnet, wird jedes $ i (0 \ leq i \ leq K) $ mit jedem $ j (0 \ leq j <i, i <j \ leq K) $ und $ N $ multipliziert Da $ O (\ log N) $ für die Multiplikationsberechnung erforderlich ist, ist $ O (K (K + \ log N)) = O (K ^ 2 + K \ log N) $. Bei dieser Methode scheint es aufgrund der Gleitkommazahl einen Fehler von ungefähr 1/10 ^ {14} $ des numerischen Werts zu geben, wie im Fall von $ k = 3 $ beim letzten Mal.

Implementierungsbeispiel 3: Verwenden Sie den folgenden schrittweisen Ausdruck (speichern Sie die Summe der Begriffe k und tauschen Sie nur den Anfang und das Ende aus).

\begin{align}
a_{n+k} &= \sum_{i=n}^{n+k-1}a_i\\
a_{n+k+1} &= \sum_{i=n+1}^{n+k}a_i \\
&= a_{n+k}+\sum_{i=n}^{n+k-1}a_i-a_n\\
&= a_{n+k}+a_{n+k}-a_n\\
&= 2a_{n+k} - a_n
\end{align}

zenkashiki.py

k, n = map(int, input().split())

a = [0] * max(n+1,k)
a[k-1] = 1
a[k] = 1

for i in range(0,n-k):
    a[i+k+1] = 2 * a[i+k] - a[i] 

print(a[n])

Wenn Sie sich einen Algorithmus wie die kumulative Summe vorstellen, in der die Summe der $ k $ -Terme gespeichert ist, ohne den allgemeinen Term zu finden, können Sie ihn auf diese Weise mit dem Berechnungsbetrag $ O (N) $ finden.

Ausführungsbeispiel

2 5
5

3 50
3122171529233

4 25
1055026

10 50  
1082392024832

50 30
0

100 150
1125899906842618

1000 1010
1024

Vergleich des Berechnungsbetrags

Durch Vergleichen des Rechenaufwands zwischen Implementierung 2 und Implementierung 3 ist es besser, $ N $ und $ K ^ 2 + K \ log N $ zu vergleichen und zu prüfen, welche schneller sind.

Vergleich der Ausführungszeit

measure_time.py

import time
import numpy as np
import warnings 
warnings.filterwarnings('ignore')       #Bei der Berechnung komplexer Zahlen tritt eine Warnung auf. Löschen Sie sie daher.

k, n = map(int, input().split())
m = 100        # loop count

"""
#Implementierung 1
start = time.time()
for loop in range(m):

    a = [0] * max(n+1,k)
    a[k-1] = 1

    for i in range(k,n+1):
        for j in range(1,k+1):
            a[i] += a[i-j]

elapsed_time = time.time() - start
elapsed_time /= m
print ("Implementierung 1: {0}".format(elapsed_time) + "[sec]")
"""


#Implementierung 2
start = time.time()
for loop in range(m):

    equation = [1]
    for i in range(k):
        equation.append(-1)     # equation = [1, -1, -1, ... , -1] = lambda^k - lambda^{k-1} - ... - lambda -1 = 0

    lam = np.roots(equation)     # lambda_i

    a = 0

    for i in range(k):
        prod = 1
        for j in range(k):
            if j != i:
                prod *= lam[i] - lam[j]
        a += np.power(lam[i],n) / prod

elapsed_time = time.time() - start
elapsed_time /= m
print ("Implementierung 2: {0}".format(elapsed_time) + "[sec]")


#Implementierung 3
start = time.time()
for loop in range(m):

    a = [0] * max(n+1,k)
    a[k-1] = 1
    a[k] = 1

    for i in range(0,n-k):
        a[i+k+1] = 2 * a[i+k] - a[i] 

elapsed_time = time.time() - start
elapsed_time /= m
print ("Implementierung 3: {0}".format(elapsed_time) + "[sec]")

Beispiel für ein Messergebnis

# N ~ K^2+Klog N
10 500 
Implementierung 2: 0.00041536092758178713[sec]
Implementierung 3: 0.0003914594650268555[sec]

# N > K^2+Klog N
3 10000
Implementierung 2: 0.0002478790283203125[sec]
Implementierung 3: 0.012493629455566407[sec]

# N < K^2+Klog N
100 500
Implementierung 2: 0.01716961145401001[sec]
Implementierung 3: 0.0002404618263244629[sec]

Wie ich im Vergleich des Berechnungsbetrags dachte, wird bestätigt, dass Implementierung 2 schnell ist, wenn $ N> K ^ 2 + K \ log N $, und Implementierung 3 schnell ist, wenn $ N <K ^ 2 + K \ log N $ Ich werde.