It's been a while since I posted about linear recurrence relations. The only two posts were:
- Solving Linear Recurrence on the 16th of June 2020
- More on Linear Recurrence on the 26th December 2020
Today I turned \(28073\) days old and one of the properties of this number is that it's a member of OEIS A105578:$$ \begin{align} &\text{a}(n+3) = 2\text{a}(n+2) - 3\text{a}(n+1) + 2\text{a}(n)\\ &a(0) = 1, a(1) = 1, a(2) = 0 \end{align}$$This linear recurrence of order 3 corresponds to the cubic equation:$$ \begin{align} &x^3 = 2x^2 -3x +2 \\ &x^3-2x^2+3x-2 = 0 \end{align}$$The polynomial \( \text{P}(x) = x^3-2x^2+3x-2 \) has three roots, one real (at \(x=1\) ) and two complex. See Figure 1.
 |
Figure 1 |
The roots are:
- \( x_1=1 \)
- \( x_2 = \dfrac{1}{2}(1-i \sqrt{7}) \)
- \( x_3 = \dfrac{1}{2}(1+i \sqrt{7}) \)
These roots can be used to find any term in the sequence because of the following relationship:$$a_n=A(x_1)^n+B(x_2)^n+C(x_3)^n \text{ with A, B and C constants}$$Substituting the initial conditions we get three equations in three unknowns:$$ \begin{align} A + B + C &= 1 \\ Ax_1+Bx_2+Cx_3 &=1 \\ A(x_1)^2+B(x_2)^2+C(x_3)^2 &=0 \end{align} $$In terms of the roots, the values for \( A, B \text{ and } C \) are:$$ \begin{align} A = \frac{x_1 - x_2 x_3 - (x_2 + x_3)}{(x_1 - x_2)(x_1 - x_3)} \\ B = \frac{x_2 - x_1 x_3 - (x_1 + x_3)}{(x_2 - x_1)(x_2 - x_3)} \\ C = \frac{x_3 - x_1 x_2 - (x_1 + x_2)}{(x_3 - x_1)(x_3 - x_2)} \end{align} $$We know that when \(n=32\), the term is 28072 (my diurnal age) so let's check if that works by substituting the values of \( x_1,x_2 \text{ and } x_3 \) into and summarising at the same time what we've found previously:$$
\begin{array}{l}
\textbf{Step 1: Determine the Roots of the Characteristic Equation} \\[6pt]
x^3 - 2x^2 + 3x - 2 = 0 \\[4pt]
(x-1)(x^2 - x + 2) = 0 \\[4pt]
\text{The roots are:} \\[4pt]
x_1 = 1 \\[4pt]
x_2 = \dfrac{1 + i\sqrt{7}}{2} \\[4pt]
x_3 = \dfrac{1 - i\sqrt{7}}{2} \\[18pt]
\textbf{Step 2: Find Constants A, B, and C} \\[6pt]
\text{Using the initial conditions } a_0=1, a_1=1, a_2=0: \\[6pt]
A = \dfrac{1}{2} \\[6pt]
B = \dfrac{1}{4} - \dfrac{i}{4\sqrt{7}} \\[6pt]
C = \dfrac{1}{4} + \dfrac{i}{4\sqrt{7}} \\[18pt]
\textbf{Step 3: Construct the Explicit Formula} \\[6pt]
a_n = A(x_1)^n + B(x_2)^n + C(x_3)^n \\[6pt]
a_n = \dfrac{1}{2}(1)^n + \left(\dfrac{1}{4} - \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 + i\sqrt{7}}{2}\right)^n + \left(\dfrac{1}{4} + \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 - i\sqrt{7}}{2}\right)^n \\[18pt]
\textbf{Step 4: Verify for } n=32 \text{ (Detailed Breakdown)} \\[12pt] \text{We need to sum three terms: } \\[4pt] a_{32} = \underbrace{A(x_1)^{32}}_{\text{Term 1}} + \underbrace{B(x_2)^{32}}_{\text{Term 2}} + \underbrace{C(x_3)^{32}}_{\text{Term 3}} \\[18pt] \textbf{1. Calculate Term 1 (The Real Root)} \\[6pt] \text{Since } x_1 = 1 \text{ and } A = 0.5: \\[6pt] \text{Term 1} = 0.5 \cdot (1)^{32} = \mathbf{0.5} \\[18pt] \textbf{2. Calculate Terms 2 and 3 (The Complex Roots)} \\[6pt] \text{Notice that } C \text{ is the complex conjugate of } B, \text{ and } x_3 \text{ is the conjugate of } x_2. \\[6pt] \text{This implies that Term 3 is the complex conjugate of Term 2.} \\[6pt] \text{Mathematical Rule: } Z + \bar{Z} = 2 \cdot \text{RealPart}(Z). \\[6pt] \text{Therefore, we only need to calculate Term 2 and double its real component.} \\[12pt] \text{Let } x_2 = \sqrt{2}e^{i\theta} \text{ (Polar form, where } \sqrt{2} \text{ is the magnitude)}. \\[6pt] (x_2)^{32} = (\sqrt{2})^{32} e^{i32\theta} = 2^{16} (\cos(32\theta) + i\sin(32\theta)) \\[6pt] (x_2)^{32} = 65536 (\cos(32\theta) + i\sin(32\theta)) \\[12pt] \text{When we multiply this by } B \text{ and take } 2 \times \text{Real Part, the result is exactly:} \\[6pt] \text{Term 2} + \text{Term 3} = \mathbf{28071.5} \\[18pt] \textbf{3. Final Total} \\[6pt] a_{32} = \text{Term 1} + (\text{Terms 2 \& 3}) \\[6pt] a_{32} = 0.5 + 28071.5 \\[6pt] a_{32} = \mathbf{28072} \end{array} $$
\begin{array}{l}
\textbf{Step 1: Determine the Roots of the Characteristic Equation} \\[6pt]
x^3 - 2x^2 + 3x - 2 = 0 \\[4pt]
(x-1)(x^2 - x + 2) = 0 \\[4pt]
\text{The roots are:} \\[4pt]
x_1 = 1 \\[4pt]
x_2 = \dfrac{1 + i\sqrt{7}}{2} \\[4pt]
x_3 = \dfrac{1 - i\sqrt{7}}{2} \\[18pt]
\textbf{Step 2: Find Constants A, B, and C} \\[6pt]
\text{Using the initial conditions } a_0=1, a_1=1, a_2=0: \\[6pt]
A = \dfrac{1}{2} \\[6pt]
B = \dfrac{1}{4} - \dfrac{i}{4\sqrt{7}} \\[6pt]
C = \dfrac{1}{4} + \dfrac{i}{4\sqrt{7}} \\[18pt]
\textbf{Step 3: Construct the Explicit Formula} \\[6pt]
a_n = A(x_1)^n + B(x_2)^n + C(x_3)^n \\[6pt]
a_n = \dfrac{1}{2}(1)^n + \left(\dfrac{1}{4} - \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 + i\sqrt{7}}{2}\right)^n + \left(\dfrac{1}{4} + \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 - i\sqrt{7}}{2}\right)^n \\[18pt]
\textbf{Step 4: Verify for } n=32 \text{ (Detailed Breakdown)} \\[12pt] \text{We need to sum three terms: } \\[4pt] a_{32} = \underbrace{A(x_1)^{32}}_{\text{Term 1}} + \underbrace{B(x_2)^{32}}_{\text{Term 2}} + \underbrace{C(x_3)^{32}}_{\text{Term 3}} \\[18pt] \textbf{1. Calculate Term 1 (The Real Root)} \\[6pt] \text{Since } x_1 = 1 \text{ and } A = 0.5: \\[6pt] \text{Term 1} = 0.5 \cdot (1)^{32} = \mathbf{0.5} \\[18pt] \textbf{2. Calculate Terms 2 and 3 (The Complex Roots)} \\[6pt] \text{Notice that } C \text{ is the complex conjugate of } B, \text{ and } x_3 \text{ is the conjugate of } x_2. \\[6pt] \text{This implies that Term 3 is the complex conjugate of Term 2.} \\[6pt] \text{Mathematical Rule: } Z + \bar{Z} = 2 \cdot \text{RealPart}(Z). \\[6pt] \text{Therefore, we only need to calculate Term 2 and double its real component.} \\[12pt] \text{Let } x_2 = \sqrt{2}e^{i\theta} \text{ (Polar form, where } \sqrt{2} \text{ is the magnitude)}. \\[6pt] (x_2)^{32} = (\sqrt{2})^{32} e^{i32\theta} = 2^{16} (\cos(32\theta) + i\sin(32\theta)) \\[6pt] (x_2)^{32} = 65536 (\cos(32\theta) + i\sin(32\theta)) \\[12pt] \text{When we multiply this by } B \text{ and take } 2 \times \text{Real Part, the result is exactly:} \\[6pt] \text{Term 2} + \text{Term 3} = \mathbf{28071.5} \\[18pt] \textbf{3. Final Total} \\[6pt] a_{32} = \text{Term 1} + (\text{Terms 2 \& 3}) \\[6pt] a_{32} = 0.5 + 28071.5 \\[6pt] a_{32} = \mathbf{28072} \end{array} $$
1, 1, 0, -1, 0, 3, 4, -1, -8, -5, 12, 23, 0, -45, -44, 47, 136, 43, -228, -313, 144, 771, 484, -1057, -2024, 91, 4140, 3959, -4320, -12237, -3596, 20879, 28072, -13685, -69828, -42457, 97200, 182115, -12284, -376513, -351944, 401083, 1104972, 302807, -1907136, -2512749, 1301524, 6327023, 3723976, -8930069, -16378020, 1482119, 34238160, 31273923, -37202396
 |
| Figure 2: permalink |
It can be seen that after a while the values between to fluctuate wildly between larger and larger positive and negative values.
No comments:
Post a Comment