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$
13
  • 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$ Jun 21, 2016 at 22:57
  • $\begingroup$ Everybody has avoided the question of the closed form involving a sinus.!!! $\endgroup$
    – Piquito
    Jun 22, 2016 at 0:55
  • 6
    $\begingroup$ @Piquito there is no reasonable way to involve trigonometry here. $\endgroup$
    – Will Jagy
    Jun 22, 2016 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$ Jun 22, 2016 at 19:06
  • 2
    $\begingroup$ @FractionalInquirer You should try to merge your accounts. $\endgroup$ Jun 23, 2016 at 14:24

5 Answers 5

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$
5
  • $\begingroup$ See my answer for proof that the limit exists, as well as some details of the convergence behaviour. $\endgroup$
    – user21820
    Jun 22, 2016 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$ Jun 22, 2016 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$ Jun 22, 2016 at 19:01
  • $\begingroup$ @KlausDraeger I hope the sentence I added makes this clear. $\endgroup$
    – miracle173
    Jun 23, 2016 at 15:59
  • $\begingroup$ @MarkLakata You are right. Maybe the OP wanted to write 0.13746 and lost a digit, $\endgroup$
    – miracle173
    Jun 23, 2016 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$
0
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$
1
  • $\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, 2016 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$
0

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.