0

I have the following recurrence relation (where $n$ is an integer greater than $0$):

$$\begin{array}{*{20}{l}} \begin{array}{l} {x_0} = \frac{1}{2},\\ {x_1} = \frac{3}{2},\\ {x_2} = \frac{1}{2}, \end{array}\\ {{x_{3n}} = \frac{1}{2}\cdot{x_{3n - 1}},}\\ {{x_{3n + 1}} = {x_{3n}} + 1,}\\ {{x_{3n + 2}} = \frac{1}{3}\cdot{x_{3n + 1}}} \end{array}$$

Question: how to find ${x_{146}}$ ( that is, ${{x_{3n + 2}}}$ for $n = 48$ )? If I am not mistaken, it should be equal to $$\frac{{3({6^{50}} - 1)}}{{5 \cdot {6^{50}}}}$$ or somewhere close to this, but what is the correct way to obtain this result?

lyrically wicked
  • 890
  • Is your recurrence truly different from $x_{n+3}=\frac{1}{6} x_n + \frac{1}{3}$? If not then there is a straightforward general recipe that can be used here. – Ian Mar 17 '17 at 03:12
  • @Ian: If not, then what recipe, and what will be its result for the 146th element? Where can I see the description of the technique? – lyrically wicked Mar 17 '17 at 04:24
  • The technique is just the standard method for linear recurrence relations with constant coefficients: the general solution to $x_{n+3}=\frac{1}{6} x_n + \frac{1}{3}$ is $c_1 r_1^n + c_2 r_2^n + c_3 r_3^n + \frac{2}{5}$ where $c_k$ are arbitrary constants and $r_k$ are the three roots of $p(x)=x^3-1/6$, namely $6^{-1/3} e^{2 k i \pi/3}$ for $k=-1,0,1$. – Ian Mar 17 '17 at 04:27
  • (Cont.) Since two of these roots are complex and the initial conditions are real, two of the $c_k$ will be complex as well. Anyway, now you just solve for the $c_k$ using the initial conditions (a system of 3 linear equations in 3 unknowns) and plug in $n=146$. – Ian Mar 17 '17 at 04:29
  • Yeah, I tried it, it looks like the solution is approximately $x_n=\frac{2}{5} + 6^{-n/3} \left ( (-0.563 - 0.310i) e^{-2 i n/3} + 1.626 + (-0.563 + 0.310i) e^{2 i n/3} \right )$. By the time $n=146$ this will be pretty much exactly $2/5$. – Ian Mar 19 '17 at 06:20

0 Answers0