(It seems that the formula may not be displayed from a smartphone, so in that case, please see it from a PC etc. Sorry.)
The Fibonacci sequence is a sequence that adds the previous two terms to form the next term. Expressed as an expression
\begin{cases}
a_{n+2} = a_{n+1} + a_{n}\\ a_0 = 0\\a_1 = 1
\end{cases}
It will be. The Tribonacci sequence is an extension of this and the number obtained by adding the previous three terms to the next term. Expressed as an expression
\begin{cases}
a_{n+3} = a_{n+2} + a_{n+1} + a_{n}\\ a_0 = 0\\a_1 = 0\\a_2 = 1
\end{cases}
It will be. If you calculate a little,
a_3 = 1+0+0=1\\
a_4 = 1+1+0=2\\
a_5 = 2+1+1=4\\
a_6 = 4+2+1=7\\
\vdots
It will be.
Let $ V $ be the space formed by a sequence of real numbers that satisfies the recurrence formula. Given the first three terms $ a_0, a_1, a_2 $ of the sequence $ \ {a_n } $, the sequence $ \ {a_n } $ is uniquely determined in $ n \ geq3 $.
\boldsymbol{u}=\{1,0,0,1,\dots \},\ \boldsymbol{v}=\{0,1,0,1,\dots \},\ \boldsymbol{w}=\{0,0,1,1,\dots\}
will do. Assuming that $ c_1 \ boldsymbol {u} + c_2 \ boldsymbol {v} + c_3 \ boldsymbol {w} = \ boldsymbol {o} $ holds for $ c_1, c_2, c_3 \ in \ mathbb {C} $ ,
c_1\{1,0,0,\dots \}+c_2\{0,1,0,\dots \}+c_3\{0,0,1,\dots \}=\{c_1,c_2,c_3,\dots \}=\{0,0,0,\dots \}
Therefore, $ c_1 = c_2 = c_3 = 0 $. Therefore, $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ are known to be linearly independent.
next,
\boldsymbol{a}= \{ a_0,a_1,a_2,\dots \}
Is an arbitrary source of $ V $
\begin{align}
\boldsymbol{a}&=\{ a_0,0,0,\dots \}+\{0,a_1,0,\dots \} +\{0,0,a_2,\dots \} \\
&=a_0\{1,0,0,\dots \}+a_1\{0,1,0,\dots \}+a_2\{0,0,1,\dots \} \\
&=a_0\boldsymbol{u}+a_1\boldsymbol{v}+a_2\boldsymbol{w}
\end{align}
It can be represented by a linear combination of $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $. Therefore, $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ will generate $ V $.
From the above, $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ are linearly independent and generate $ V $, so they are the basis of $ V $.
Now, map $ f: V \ rightarrow V $
f(\{ a_n\}_{n=0}^{\infty})=\{ a_n\}_{n=1}^{\infty}
will do. $ \ boldsymbol {a} = \ {a_0, a_1, a_2, \ dots } \ in V $, $ f (\ boldsymbol {a}) = \ {a_1, a_2, a_3, \ dots } $ It satisfies the recurrence formula, so it is $ 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}
Then
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})
Is true, so $ f $ is a linear transformation of $ V $.
Regarding $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $
\begin{align}
f(\boldsymbol{u})&=\{0,0,1,\dots \}=\boldsymbol{w}\\
f(\boldsymbol{v})&=\{1,0,1,\dots \}=\boldsymbol{u}+\boldsymbol{w}\\
f(\boldsymbol{w})&=\{0,1,1,\dots \}=\boldsymbol{v}+\boldsymbol{w}
\end{align}
So
[f(\boldsymbol{u})\quad f(\boldsymbol{v})\quad f(\boldsymbol{w})]=
[\boldsymbol{u}\ \boldsymbol{v}\ \boldsymbol{w}]
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{bmatrix}
Can be expressed as. Therefore, the representation matrix for the basis $ \ boldsymbol {u}, \ boldsymbol {v}, \ boldsymbol {w} $ of $ f $ is
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{bmatrix}
is. Let this representation matrix be $ A $.
\boldsymbol{p}=\{ r^{n} \}_{n=0}^{\infty}=\{1,r,r^2,\dots \}
Belongs to $ 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}
Therefore, $ \ boldsymbol {p} $ becomes an eigenvector with an eigenvalue of $ r $. Conversely, from the above equation, we can also see that the eigenvector of the eigenvalue $ r $ of $ f $ is a geometric progression with a common ratio of $ r $. Therefore, we know that the common ratio and the eigenvalue are equal.
Find the eigenvalue of $ f $. The characteristic polynomial of $ A $ uses $ I $ as the identity matrix.
\begin{align}
\varphi_A(\lambda)&=|A-\lambda I|\\
&=\begin{vmatrix}
0-\lambda & 1 & 0 \\
0 & 0-\lambda & 1 \\
1 & 1 & 1-\lambda
\end{vmatrix}\\
&=-\lambda^3+\lambda^2+\lambda+1
\end{align}
It will be. However, $ \ varphi_A (\ lambda) = 0 $ cannot be easily solved. Let the three solutions be $ \ alpha, \ beta, \ gamma $, respectively. We will find $ \ alpha, \ beta, \ gamma $ in a later chapter. A geometric progression that is an eigenvector corresponding to the solution $ \ alpha, \ beta, \ gamma $
\boldsymbol{a}=\{ \alpha^{n} \}_{n=0}^{\infty}\\
\boldsymbol{b}=\{ \beta^{n} \}_{n=0}^{\infty}\\
\boldsymbol{c}=\{ \gamma^{n} \}_{n=0}^{\infty}
Belongs to $ V $. These are linearly independent because they are eigenvectors corresponding to the different eigenvalues of $ f $, assuming that $ \ alpha, \ beta, \ gamma $ are all different. Also, $ \ dim V = 3 $. Therefore, $ \ boldsymbol {a}, \ boldsymbol {b}, \ boldsymbol {c} $ are the basis of $ V $.
From the above, there are some $ c_1, c_2, c_3 $,
\boldsymbol{a_n}=c_1\boldsymbol{a}+c_2\boldsymbol{b}+c_3\boldsymbol{c}
Because it can be expressed as
\begin{align}
\boldsymbol{a_n}&=c_1\boldsymbol{a}+c_2\boldsymbol{b}+c_3\boldsymbol{c}\\
\Leftrightarrow \{a_0,a_1,a_2,\dots \}&=c_1\{ \alpha^{n} \}_{n=0}^{\infty}+c_2\{ \beta^{n} \}_{n=0}^{\infty}+c_3\{ \gamma^{n} \}_{n=0}^{\infty}\\
\Leftrightarrow \{0,0,1,\dots \}&=c_1\{ 1,\alpha,\alpha^2,\dots \}+c_2\{1,\beta,\beta^2,\dots \}+c_3\{ 1,\gamma,\gamma^2,\dots\} \\
\Leftrightarrow \{0,0,1,\dots \}&=\{ c_1+c_2+c_3,c_1\alpha+c_2\beta+c_3\gamma,c_1\alpha^2+c_2\beta^2+c_3\gamma^2, \dots\}
\end{align}
Expressing this as a matrix,
\begin{bmatrix}
1 & 1 & 1 \\
\alpha & \beta & \gamma \\
\alpha^2 & \beta^2 & \gamma^2
\end{bmatrix}
\begin{bmatrix}
c_1 \\ c_2 \\ c_3
\end{bmatrix}
=
\begin{bmatrix}
0 \\ 0 \\ 1
\end{bmatrix}
is. The determinant of the matrix on the left is
\begin{align}
\begin{vmatrix}
1 & 1 & 1 \\
\alpha & \beta & \gamma \\
\alpha^2 & \beta^2 & \gamma^2
\end{vmatrix}
&=
\begin{vmatrix}
1 & 0 & 0 \\
\alpha & \beta-\alpha & \gamma-\alpha \\
\alpha^2 & \beta^2-\alpha^2 & \gamma^2-\alpha^2
\end{vmatrix}\\
&=
\begin{vmatrix}
\beta-\alpha & \gamma-\alpha \\
\beta^2-\alpha^2 & \gamma^2-\alpha^2
\end{vmatrix}\\
&=\begin{vmatrix}
\beta-\alpha & \gamma-\alpha \\
\beta^2-\alpha^2 - (\beta-\alpha)(\beta + \alpha) & \gamma^2-\alpha^2 - (\gamma-\alpha)(\beta + \alpha)
\end{vmatrix}\\
&=\begin{vmatrix}
\beta-\alpha & \gamma-\alpha \\
0 & (\gamma-\alpha)(\gamma+\alpha) - (\gamma-\alpha)(\beta + \alpha)
\end{vmatrix}\\
&=(\beta-\alpha)(\gamma-\alpha)(\gamma - \beta)\\
&=(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
\end{align}
It will be. This is also known as the Vandermonde determinant. Using Cramer's rule,
\begin{align}
c_1 &= \frac{
\begin{vmatrix}
0 & 1 & 1 \\
0 & \beta & \gamma \\
1 & \beta^2 & \gamma^2
\end{vmatrix}
}{
\begin{vmatrix}
1 & 1 & 1 \\
\alpha & \beta & \gamma \\
\alpha^2 & \beta^2 & \gamma^2
\end{vmatrix}
}\\
&=
\frac{
-\begin{vmatrix}
1 & \beta^2 & \gamma^2 \\
0 & \beta & \gamma \\
0 & 1 & 1
\end{vmatrix}
}{
(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}\\
&=
\frac{
-\begin{vmatrix}
\beta & \gamma\\
1 & 1
\end{vmatrix}
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}\\
&=\frac{
\gamma-\beta
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}\\
&=\frac{1}{(\alpha-\beta)(\alpha-\gamma)
}
\end{align}
Is required. Similarly
c_2 = \frac{
\alpha-\gamma
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}=\frac{1
}{(\beta-\alpha)(\beta-\gamma)
}\\
c_3 = \frac{
\beta-\alpha
}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)
}
=\frac{1
}{(\gamma-\alpha)(\gamma-\beta)
}
Is required.
From the above,
\begin{align}
\boldsymbol{a_n} &= c_1 \boldsymbol{a} + c_2 \boldsymbol{b} + c_3 \boldsymbol{c}\\
&=\left\{ \frac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)} + \frac{\beta^n}{(\beta-\alpha)(\beta-\gamma)} + \frac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}\right\}_{n=0}^{\infty}
\end{align}
So
a_n = \frac{\alpha^n}{(\alpha-\beta)(\alpha-\gamma)} + \frac{\beta^n}{(\beta-\alpha)(\beta-\gamma)} + \frac{\gamma^n}{(\gamma-\alpha)(\gamma-\beta)}
Was led.
So far, we know the shape of the general term, but we don't know the specific values of $ \ alpha, \ beta, \ gamma $. There is also a method to find it using the formula of the solution of the cubic equation, but this time let's find it with Python. It is assumed that $ a [i] $ is calculated according to the definition of the tribonacci sequence, and $ b [i] $ is calculated by the general term. There is also a method of solving algebraically using sympy, but this time it is calculated numerically using numpy.
import numpy as np
import warnings
warnings.filterwarnings('ignore') #Warning occurs when calculating complex numbers, so delete it.
alpha, beta, gamma = np.roots([1,-1,-1,-1]) # solve 1*x^3 + (-1)*x^2+ (-1)*x + (-1) = 0
print("alpha =", alpha)
print("beta =", beta)
print("gamma =", gamma)
a = np.zeros(101)
b = np.zeros(101)
a[2] = 1
print(" i "," a[i] "," b[i] ", " a[i]-b[i] ")
for i in range(101):
if i > 2:
a[i] = a[i-1] + a[i-2] + a[i-3]
b[i] = np.power(alpha,i)/((alpha-beta)*(alpha-gamma)) + np.power(beta,i)/((beta-alpha)*(beta-gamma)) + np.power(gamma,i)/((gamma-alpha)*(gamma-beta))
print('{:3}'.format(i), '{:26}'.format(int(a[i])), '{:26}'.format(int(round(abs(b[i])))), '{:12}'.format(int(a[i]) - int(round(abs(b[i])))))
alpha = (1.839286755214161+0j)
beta = (-0.41964337760708065+0.6062907292071997j)
gamma = (-0.41964337760708065-0.6062907292071997j)
i a[i] b[i] a[i]-b[i]
0 0 0 0
1 0 0 0
2 1 1 0
3 1 1 0
4 2 2 0
5 4 4 0
6 7 7 0
7 13 13 0
8 24 24 0
9 44 44 0
10 81 81 0
11 149 149 0
12 274 274 0
13 504 504 0
14 927 927 0
15 1705 1705 0
16 3136 3136 0
17 5768 5768 0
18 10609 10609 0
19 19513 19513 0
20 35890 35890 0
21 66012 66012 0
22 121415 121415 0
23 223317 223317 0
24 410744 410744 0
25 755476 755476 0
26 1389537 1389537 0
27 2555757 2555757 0
28 4700770 4700770 0
29 8646064 8646064 0
30 15902591 15902591 0
31 29249425 29249425 0
32 53798080 53798080 0
33 98950096 98950096 0
34 181997601 181997601 0
35 334745777 334745777 0
36 615693474 615693474 0
37 1132436852 1132436852 0
38 2082876103 2082876103 0
39 3831006429 3831006429 0
40 7046319384 7046319384 0
41 12960201916 12960201916 0
42 23837527729 23837527729 0
43 43844049029 43844049029 0
44 80641778674 80641778674 0
45 148323355432 148323355432 0
46 272809183135 272809183135 0
47 501774317241 501774317241 0
48 922906855808 922906855808 0
49 1697490356184 1697490356184 0
50 3122171529233 3122171529233 0
51 5742568741225 5742568741225 0
52 10562230626642 10562230626642 0
53 19426970897100 19426970897100 0
54 35731770264967 35731770264967 0
55 65720971788709 65720971788709 0
56 120879712950776 120879712950775 1
57 222332455004452 222332455004451 1
58 408933139743937 408933139743935 2
59 752145307699165 752145307699160 5
60 1383410902447554 1383410902447546 8
61 2544489349890656 2544489349890641 15
62 4680045560037375 4680045560037345 30
63 8607945812375585 8607945812375530 55
64 15832480722303616 15832480722303512 104
65 29120472094716576 29120472094716384 192
66 53560898629395776 53560898629395416 360
67 98513851446415968 98513851446415296 672
68 181195222170528320 181195222170527072 1248
69 333269972246340096 333269972246337792 2304
70 612979045863284352 612979045863280000 4352
71 1127444240280152832 1127444240280144512 8320
72 2073693258389777408 2073693258389762048 15360
73 3814116544533214720 3814116544533186560 28160
74 7015254043203144704 7015254043203092480 52224
75 12903063846126137344 12903063846126039040 98304
76 23732434433862496256 23732434433862311936 184320
77 43650752323191775232 43650752323191439360 335872
78 80286250603180408832 80286250603179769856 638976
79 147669437360234692608 147669437360233480192 1212416
80 271606440286606852096 271606440286604623872 2228224
81 499562128250021937152 499562128250017808384 4128768
82 918838005896863416320 918838005896855945216 7471104
83 1690006574433492271104 1690006574433477853184 14417920
84 3108406708580377427968 3108406708580351213568 26214400
85 5717251288910732984320 5717251288910684749824 48234496
86 10515664571924601634816 10515664571924511457280 90177536
87 19341322569415712047104 19341322569415540080640 171966464
88 35574238430251047714816 35574238430250737336320 310378496
89 65431225571591361396736 65431225571590774194176 587202560
90 120346786571258121158656 120346786571257030639616 1090519040
91 221352250573100547047424 221352250573098500227072 2046820352
92 407130262715950037991424 407130262715946279895040 3758096384
93 748829299860308689420288 748829299860301844316160 6845104128
94 1377311813149359375122432 1377311813149346221785088 13153337344
95 2533271375725618236751872 2533271375725593540689920 24696061952
96 4659412488735286167076864 4659412488735240533049344 45634027520
97 8569995677610263510515712 8569995677610179758653440 83751862272
98 15762679542071167914344448 15762679542071011148038144 156766306304
99 28992087708416715444453376 28992087708416427681644544 287762808832
100 53324762928098150090539008 53324762928097265327276032 884763262976
Thus, when $ i $ is small, it matches. When $ i $ is large, there is an error due to floating point numbers, but since the error is small compared to the numerical value, the general term is considered to be correct.
In Python, the pow function used for power is implemented repeatedly in the square method, so a certain number of $ N $ power can be obtained quickly with $ O (\ log N) $. Therefore, the complexity required to find $ a [N] $ is $ O (N) $, but $ b [N] $ can be found by $ O (\ log N) $. On a computer, $ a [i] $ has the advantages and disadvantages that the value can be calculated accurately but the amount of calculation is large, and $ b [i] $ can be calculated at high speed but an error occurs.
I wrote an article Finding general terms of extended Fibonacci sequence (k-Bonacci sequence: sum of previous k terms) with linear algebra and Python. Please see if you like.
Recommended Posts