14
$\begingroup$

Let $\{a_n\}$ and $\{b_n\}$ be two integer sequences such that $a_1=b_1=1,$

\begin{align*} a_n=a_{n-1}+b_{n-1},\qquad\qquad b_n =r\,a_{n-1}+b_{n-1}. \end{align*}

Where $r$ is a natural number $>1$. ($r$ is a fixed value)

Write $c_n={b_n}/{a_n}$, how to prove the following limit exist without finding it?

\begin{align*} \lim_{n\to\infty} c_n. \end{align*}


Attempt

I used mathematical induction to prove $\{c_{2n}\}$ is monotonically decreasing and $\{c_{2n+1}\}$ is monotonically increasing.

Then, note that

\begin{align*} c_{n+1}=\frac{b_{n+1}}{a_{n+1}}&=\frac{r\,a_n+b_n}{a_n+b_n}\\ &=r-\frac{r-1}{\frac 1{b_n/a_n}+1}<r \end{align*}

Therefore, $0<c_n<r$.

$\vdots$

Instead of continuing using this method (too complicated), any other faster ways to prove "exist"?

I tried to use the definition of Cauchy sequence and contraction mapping (they are 2 methods), but I don't think they work here.

Any hints or tips are appreciated:)

$\endgroup$
6
$\begingroup$

Not sure if the following fits the requirement to avoid finding the limit, but anyway... Consider the change of variable $$x_n=c_n-\frac{r}{c_n}$$ then $$x_{n+1}=-f(c_n)x_n$$ with $$f(c)=\frac{(r-1)c}{(c+1)(c+r)}$$ Now, for every $c>0$, $$(c+1)(c+r)\geqslant(r+1)c$$ hence $$f(c)\leqslant s$$ with $$s=\frac{r-1}{r+1}<1$$ Thus, $$|x_n|\leqslant s^{n-1}\cdot|x_1|$$ which implies that $$x_n\to0$$ hence $$c_n\to\text{____}$$

$\endgroup$
  • $\begingroup$ Nice answer! Could you explain how $f$ is created? $\endgroup$ – Tianlalu Sep 1 '17 at 1:46
  • $\begingroup$ By computing carefully $$x_{n+1}=c_{n+1}-\frac{r}{c_{n+1}}$$ in terms of $c_n$ and factoring $x_n$ in the result. $\endgroup$ – Did Sep 1 '17 at 6:15
  • $\begingroup$ I read your proof carefully just now and it seems nice as usual. (+1) $\endgroup$ – Sangchul Lee Sep 1 '17 at 23:02
10
$\begingroup$

Write your formulas in a matrix form:

$$\begin{bmatrix}a_n\\b_n\end{bmatrix} = \begin{bmatrix}1&1\\r&1\end{bmatrix}\begin{bmatrix}a_{n-1}\\b_{n-1}\end{bmatrix}$$ i.e. $$w_n=Aw_{n-1}$$

Notice that if you normalize every vector after applying $A$, that is if you consider $$v_n=\frac{Av_{n-1}}{||Av_{n-1}||}$$ instead $w_n$, then it will generate the same $\{c_n\}$. This is because

  • normalization changes magnitude of the given vector, not its direction
  • $A$ is a linear transformation; changing the magnitude of its input doesn't change the direction of its output
  • and finally $c_n$ depends on the n-th direction only.

This formula for $v_n$ above is exactly what power iteration does. The following citation is useful (it has been translated to match our chosen names and starting index):

If $A$ has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector $v_{1}$ has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence $\{v_n\}$ converges to an eigenvector associated with the dominant eigenvalue.

Think about eigenvalues (say: $\lambda$) and how they depend on $r$. You will have to consider a quadratic equation w.r.t. $\lambda$ and its discriminant, which will be of first degree w.r.t. $r$. By analyzing the two you will find that for $r>1$ there are always two distinct real eigenvalues (and none of them is $0$, this will be important in a moment). Apply proper Vieta's formula to show they cannot sum to $0$. They cannot be equal, they cannot be opposite, so one eigenvalue is strictly greater in magnitude for sure.

If the starting non-zero vector had zero component in the direction of one of the two eigenvectors, then it would be the other eigenvector. Applying $A$ to it would act as multiplying by eigenvalue (which is nonzero). This means $w_1, w_2, w_3, …$ would have the same direction, so $c_1, c_2, c_3, …$ would be equal and $\{c_n\}$ would trivially converge. In our case however $c_1=1$ and $c_2\neq1$. This means $v_1$ has non-zero component in the direction of any of the two eigenvectors; in particular in the direction associated with the dominant eigenvalue.

So the conditions are met, $\{v_n\}$ converges to some eigenvector. It has some direction which corresponds to the limit of $\{c_n\}$.

Q: But wait! If $\begin{bmatrix}0\\1\end{bmatrix}$ was this eigenvector associated with the dominant eigenvalue, wouldn't the limit be $\infty$ or $-\infty$?

A: I think it would, it doesn't matter though. Calculate $A\begin{bmatrix}0\\1\end{bmatrix}$ and you will see it's not an eigenvector.

$\endgroup$
  • 3
    $\begingroup$ So far this seems to be the only proof that doesn't at some point have the value of the limit in it, as it never calculates what the eigenvectors actually are. $\endgroup$ – eyeballfrog Sep 1 '17 at 2:35
  • $\begingroup$ @eyeballfrog the only proof that doesn't at some point have the value of the limit in it My answer proves the limit exists without giving it, too. (Note that $A_2, B_2$ are never calculated there, they are just known to exist - very much like the above doesn't actually calculate the eigenvectors.) $\endgroup$ – dxiv Sep 1 '17 at 19:57
  • $\begingroup$ @dxiv Fair point. In fact, unless I'm mistaken, your proof and this one are equivalent. $\endgroup$ – eyeballfrog Sep 1 '17 at 20:03
  • 2
    $\begingroup$ @eyeballfrog Indeed, it's the same core idea about reducing it to the case of a linear homogeneous recurrence, but (neatly) done in matrix form. $\endgroup$ – dxiv Sep 1 '17 at 20:07
4
$\begingroup$

Again, not sure if this satisfies your criteria, but if we let $f : [0,\infty) \to \mathbb{R}$ by

$$ f(z) = \frac{r+z}{1+z} $$

then $f$ is decreasing, $0\leq f \leq r$, and $c_{n+1} = f(c_n)$. So if we let

$$ \beta = \limsup_{n\to\infty} c_n, \qquad \alpha = \liminf_{n\to\infty} c_n $$

then we have $ \beta = f(\alpha)$ and $\alpha = f(\beta)$, i.e., both $\alpha$ and $\beta$ are non-negative fixed points of $g = f\circ f$. Since this function has a unique non-negative fixed point, this proves that $\alpha = \beta$.

$\endgroup$
  • $\begingroup$ How do we know it has a unique fixed point? $\endgroup$ – eyeballfrog Sep 1 '17 at 2:26
  • $\begingroup$ @eyeballfrog, You can solve $g(x) = x$ directly. It reduces to a quadratic equation with zeros $x = \pm \sqrt{r}$. But certainly solving this equation is related to knowing the possible limit candidate, which I am not sure if OP likes. $\endgroup$ – Sangchul Lee Sep 1 '17 at 2:30
  • $\begingroup$ Yeah that was what I was thinking of as the problem. It does require evaluating the fixed point which is the limit. Not super sure why OP wants us to not do that, but still. $\endgroup$ – eyeballfrog Sep 1 '17 at 2:33
3
$\begingroup$

From the first relation $b_{n-1}=a_n-a_{n-1}$, then substituting into the second one:

$$ a_{n+1} = 2 a_n +(r-1)a_{n-1} \tag{1} $$

From the second relation $ra_{n-1}=b_n-b_{n-1}$, then substituting into the first one and simplifying:

$$ b_{n+1} = 2b_n+(r-1)b_{n-1} \tag{2} $$

Therefore $a_n$ and $b_n$ satisfy the same linear homogeneous recurrence with characteristic polynomial $t^2-2t-(r-1)$, only with different initial conditions.

Let $t_{1}=1 - \sqrt{r},\, t_{2}=1 + \sqrt{r}$ be the roots of the characteristic polynomial, with $|t_2| \gt |t_1|$.

Then $a_n=A_1t_1^n+A_2t_2^n$ and $b_n=B_1t_1^n+B_2t_2^n$ for some constants $A_i, B_j$ determined by the initial conditions. It can be easily verified that $A_2 \ne 0$, therefore $c_n = b_n / a_n \to B_2 / A_2$.

$\endgroup$
3
$\begingroup$

Note that $$c_{n+1}=\frac{ra_n+b_n}{a_n+b_n}=1+\frac{r-1}{\frac{a_n+b_n}{a_n}} =1+\frac{r-1}{1+c_n}.$$ Wanting to show that the map $$f(x)=1+\frac{r-1}{1+x} $$ is a contraction, is a bit problematic However, $$ f(f(x))=1+\frac{r-1}{2+\frac{r-1}{1+x}}=1+\frac{(r-1)(1+x)}{2(1+x)+r-1}=\frac{(r+1)x+2r}{2x+r+1}$$ has derivative $$ \frac{(r+1)(2x+r+1)-2((r+1)x+2r)}{(2x+r+1)^2}=\frac{(r-1)^2}{(2x+r+1)^2}<1$$ for non-negative $x$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. $f\circ f$ is proved to be a contraction. Does it mean we should consider the even and the odd terms of $c_n$ separately? Then, how to prove two fixed points in even and odd situations are equal? $\endgroup$ – Tianlalu Sep 1 '17 at 13:53

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.