19
$\begingroup$

Is there any closed form for the following limit?

Define the sequence $$ \begin{cases} a_{n+1} = b_n+2a_n + 14\\ b_{n+1} = 9b_n+ 2a_n+70 \end{cases}$$ with initial values $a_0 = b_0 = 1$. Then $\lim_{n\to\infty} \frac{a_n}{b_n} = ? $

The limit is approximately $0.1376$. My math teacher Carlos Ivorra says that this limit have a closed form involving the sine of an angle. What is the closed form for is limit?

NOTE: I have found this (and another series of converging sequences) by the use of an ancient method for calculating sines recently rediscovered. I'll give the details soon as a more general question.

$\endgroup$
  • 9
    $\begingroup$ This becomes sensible in the context of linear algebra: the triple $(a_{n+1},b_{n+1},1)$ is expressed by a matrix multiplication applied to $(a_n,b_n,1)$. The eigenvalues and eigenvectors determine the asymptotic behavior, in the sense that the eigenvector corresponding to the largest eigenvalue will dominate, in general. Is this familiar-sounding stuff? $\endgroup$ – paul garrett Jun 21 '16 at 22:57
  • $\begingroup$ Everybody has avoided the question of the closed form involving a sinus.!!! $\endgroup$ – Piquito Jun 22 '16 at 0:55
  • 6
    $\begingroup$ @Piquito there is no reasonable way to involve trigonometry here. $\endgroup$ – Will Jagy Jun 22 '16 at 1:25
  • 1
    $\begingroup$ @KamilMaciorowski, yes, indeed, you're correct. Of course, the odds are good that a fairly random vector does contain a non-zero component for the largest (in modulus, yes) eigenvector, but in either aritificially posed situations, and/or some significant natural situations, it might be a delicate issue whether the largest occurs or not. Observational error and such? Potential instability. $\endgroup$ – paul garrett Jun 22 '16 at 19:06
  • 2
    $\begingroup$ @FractionalInquirer You should try to merge your accounts. $\endgroup$ – Daniel Fischer Jun 23 '16 at 14:24
31
$\begingroup$

If $\mu=\lim_{n\to\infty} \frac{a_{n} }{b_{n} } $exists then $$ \mu=\lim_{n\to\infty} \frac{a_{n+1} }{b_{n+1} } = \lim_{n\to\infty} \frac{b_n+2a_n + 14}{9b_n+ 2a_n+70 }\\= \lim_{n\to\infty} \frac{\frac{b_{n} }{b_{n} }+2\frac{a_{n} }{b_{n} } + \frac{14 }{b_{n} }}{9\frac{b_{n} }{b_{n} }+ 2\frac{a_{n} }{b_{n} }+\frac{70 }{b_{n} } }\\ =\frac{1+2\lim_{n\to\infty}(\frac{a_{n} }{b_{n} }) + \lim_{n\to\infty}(\frac{14 }{b_{n} })}{9+ 2\lim_{n\to\infty}(\frac{a_{n} }{b_{n} })+\lim_{n\to\infty}(\frac{70 }{b_{n} }) }\\ =\frac{1+2\mu+ 0}{9+ 2\mu+0} $$ Here we used the fact that ${b}_{{n}}>{n}$ and therefore $$0\leq~\lim_{{n}\to\infty}~{\frac{1}{{b}_{{n}}}}<\lim_{{n}\to\infty}~{\frac{1}{{n}}}\leq0$$

So $$2\mu^2+7\mu-1=0$$. But $\mu \gt 0$, so $$\mu={{\sqrt{57}-7}\over{4}} $$

$\endgroup$
  • $\begingroup$ See my answer for proof that the limit exists, as well as some details of the convergence behaviour. $\endgroup$ – user21820 Jun 22 '16 at 7:47
  • 6
    $\begingroup$ For completeness, you may want to give a reason for $\lim_{n\to\infty}\frac{1}{b_n}$ being $0$. $\endgroup$ – Klaus Draeger Jun 22 '16 at 13:27
  • 1
    $\begingroup$ From my calculator: 0.13745860881768742430917120173653, so the original statement is incorrect, the limit is closer to 0.1375, not 0.1376. $\endgroup$ – Mark Lakata Jun 22 '16 at 19:01
  • $\begingroup$ @KlausDraeger I hope the sentence I added makes this clear. $\endgroup$ – miracle173 Jun 23 '16 at 15:59
  • $\begingroup$ @MarkLakata You are right. Maybe the OP wanted to write 0.13746 and lost a digit, $\endgroup$ – miracle173 Jun 23 '16 at 16:01
26
$\begingroup$

One idea to get the limit in closed form :

Let $A=\begin{pmatrix} 2 & 1 \\ 2 & 9 \end{pmatrix}$, $X_n = \begin{pmatrix} a_n \\ b_n \end{pmatrix}$, and $b=\begin{pmatrix} 14 \\ 10 \end{pmatrix}$.

You can write $X_{n+1} = AX_n + b$. The idea is to solve the equation $X=AX+b$ ($X$ being a two-dimensional vector) - this equation has a unique solution as $(A-I)$ is non-singular. Let's call $X$ this solution; you can write $(X_{n+1}-X)=A(X_n - X)$ then, for all $n$, you have :

\begin{equation} (X_{n} - X ) =A^n (X_{0} - X) \end{equation}

$A^n$ can be evaluated by diagonalizing $A$. This will give you $X_n$ (and then $a_n$ and $b_n$ in closed form).

$\endgroup$
8
$\begingroup$

The requested limit is: $$ \frac{4 \sqrt{57} - 20}{4 \sqrt{57} + 44} \approx 0.1374586 $$ This is $$ \frac{ \sqrt{57} - 5}{ \sqrt{57} + 11} $$ and rationalizing the denominator gives $$ \frac{ \sqrt{57} - 7}{ 4} $$

$$ a_{n+2} = 11 a_{n+1} - 16 a_n - 42 $$

$$ b_{n+2} = 11 b_{n+1} - 16 b_n - 42 $$

The separate linear recurrences are the result of the Cayley-Hamilton Theorem applied to the matrix $$ \left( \begin{array}{rr} 2 & 1 \\ 2 & 9 \end{array} \right) $$ although I wrote everything out in detail because I was not sure what the constant terms $14,70$ would do.

Hmmm. Good thing I was careful, it was not necessary that the 42's come out the same. Given the matrix system $X_{n+1} = A X_n + B,$ where $\tau = \operatorname{trace} A$ and $\delta = \det A,$ we get $$ X_{n+2} = \tau X_{n+1} - \delta X_n + (A - (\tau - 1)I) B. $$ There is no reason to expect the two components of $(A - (\tau - 1)I) B$ to come out the same, it was arranged for this particular problem. Indeed, here $$ (A - (\tau - 1)I)^{-1} = \frac{1}{6} \left( \begin{array}{rr} 1 & 1 \\ 2 & 8 \end{array} \right) $$ so to get the two constants the same it was required to take the constant vector $B$ as a scalar multiple of $$ \left( \begin{array}{rr} 1 & 1 \\ 2 & 8 \end{array} \right) \left( \begin{array}{r} 1 \\ 1 \end{array} \right) = \left( \begin{array}{r} 2 \\ 10 \end{array} \right), $$ and they multiplied this by $7.$

$$ a_n = \left( 4 - \frac{20}{\sqrt{57}} \right) \left( \frac{11 + \sqrt {57}}{2} \right)^n + \left( 4 + \frac{20}{\sqrt{57}} \right) \left( \frac{11 - \sqrt {57}}{2} \right)^n - 7 $$ $$ b_n = \left( 4 + \frac{44}{\sqrt{57}} \right) \left( \frac{11 + \sqrt {57}}{2} \right)^n + \left( 4 - \frac{44}{\sqrt{57}} \right) \left( \frac{11 - \sqrt {57}}{2} \right)^n - 7 $$

$\endgroup$
6
$\begingroup$

Here is a rigorous and systematic way to analyze the existence and value of the limit. (miracle173's answer didn't prove existence but uses essentially the same method for finding the value if it exists.)

Let $c_n = \frac{a_n}{b_n}$ (for each $n \in \mathbb{N}$).

Then $b_{n+1} c_{n+1} = b_n + 2 b_n c_n + 14$.

And $b_{n+1} = 9 b_n + 2 b_n c_n + 70$.

Thus $c_{n+1} = \dfrac{ b_n + 2 b_n c_n + 14 }{ 9 b_n + 2 b_n c_n + 70 } = \dfrac{ 1 + 2 c_n + \frac{14}{b_n} }{ 9 + 2 c_n + \frac{70}{b_n} }$.

Let $r = \dfrac{\sqrt{57}-7}{4}$ so that $r = \dfrac{1+2r}{9+2r}$, and let $d_n = c_n - r$.

Take any $ε > 0$, and let "$[x]$" denote "$\{ t : t \in \mathbb{R} \land |t| \le x \}$".

Then $c_{n+1} \in \dfrac{ 1 + 2 c_n }{ 9 + 2 c_n } + [ε]$ as $n \to \infty$, since $b_n \to \infty$ as $n \to \infty$.

Then $d_{n+1} \in \dfrac{ 1 + 2 (r+d_n) }{ 9 + 2 (r+d_n) } + [ε] - r = \dfrac{ 2 - 2 r }{ 9 + 2 (r+d_n) } d_n + [ε] \subseteq [\frac29 d_n] + [ε]$.

Thus $d_n \in [2ε]$ eventually as $n \to \infty$, since $\frac29 x + 1 < x - \frac12$ for any $x > 2$.

Therefore since $ε$ was arbitrary, $d_n \to 0$ as $n \to \infty$.

$\endgroup$
  • $\begingroup$ Note that this technique applies to many such iterative processes, where we attempt to isolate the significant terms and analyze the remainder. Also, one can usually easily recover hard bounds on the convergence behaviour. In this case, one only needs to know how large $n$ must be for the $[ε]$ error bound to hold, and we could if desired compute an upper bound on $d_n$ after that point by solving $d_{n+1} = \frac29 d_n + ε$. I didn't do that here because we didn't need it at all. $\endgroup$ – user21820 Jun 22 '16 at 7:51
4
$\begingroup$

Define

$$ L = \lim_{n \to \infty} \frac{a_n}{b_n} $$ $$ r = \lim_{n \to \infty} \frac{a_{n+1}}{b_n} $$ $$ s = \lim_{n \to \infty} \frac{b_{n+1}}{b_n} $$

then it's not hard to see that $L = r/s$. Also, by substituting in the recursion, since we have $b_n \to \infty$ we can compute

$$ r = \lim_{n \to \infty} \left(1 + 2 \frac{a_n}{b_n} + \frac{14}{b_n}\right) = 1 + 2L $$ $$ s = \ldots = 9 + 2L $$

(the reason to define $r$ and $s$ is precisely because I wanted to simplify the recursions in this fashion)

Solving the system of equations, along with $L>0$, gives

$$ L = \frac{-7 + \sqrt{57}}{4} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.