2
$\begingroup$

Let {$f_n$} be defined recursively as $f_1 = f_2 = f_3 = 1$ and $f_n = f_{n-1} + f_{n-3}$ for all $n \gt 3$.

Also, define {$a_n$} as the ratio of the terms of {$f_n$}. That is, $a_n = \frac{f_{n+1}}{f_n}$ for some $n \geq 1$.

So, the terms of {$f_n$} are $$f_1 = 1,f_2 = 1,f_3 = 1,f_4 = 2,f_5 = 3,f_6 = 4,f_7 = 6,\ldots,$$ and the terms of {$a_n$} are $$a_1 = 1,a_2 = 1,a_3 = 2,a_4 = \frac{3}{2},a_5 = \frac{4}{3},a_6 = \frac{6}{4},\ldots$$

The question then becomes evaluating the limiting ratio of {$f_n$} or, in other words,

Find $$\lim_{n \to \infty}{a_n} = \lim_{n \to \infty}\frac{f_{n+1}}{f_n}, \forall n \geq 1.$$

The way I approached this problem was to try to put bounds on $a_k = \frac{f_{k+1}}{f_k}$ for some $k$. It made the most sense to me that $1 \leq a_k \leq 2$ just based off of the first few terms of {$a_n$}.

Then, I tried to rewrite $a_k = \frac{f_{k+1}}{f_k}$ in some way that would allow me to put bounds on $a_{k+1}$, since we want to show next that $1 \leq a_{k+1} \leq 2$.

$$a_{k+1} = \frac{f_{k+2}}{f_{k+1}} = \frac{f_{k+1} + f_{k-1}}{f_{k+1}} = 1 + \frac{f_{k-1}}{f_{k+1}}.$$

Next, I thought it would be a good idea to invert the inequality $1 \leq a_k \leq 2$. That is, $1 \geq \frac{1}{a_k} = \frac{f_k}{f_{k+1}} \geq \frac{1}{2}$ and then add $1$ to get the inequality $2\geq 1 + \frac{f_k}{f_{k+1}} \geq \frac{3}{2}$.

And while $1 + \frac{f_k}{f_{k+1}}$ looks like a pretty result, what I actually need to find in this case is $1 + \frac{f_{k-1}}{f_{k+1}}$.

It seems that at this point more clever manipulation is required, but I don't know what else can be done once I've reached this dead end. Can someone please elaborate on how to proceed with the above method or provide an alternative approach altogether?

I appreciate any and all advice!

Thanks for reading,

A

$\endgroup$
  • $\begingroup$ I don't know if it'll take you anywhere useful for your problem, but my reaction would be to try this method:faculty.mansfield.edu/hiseri/MA1115/1115L30.pdf $\endgroup$ – BGreen Apr 23 '15 at 4:53
  • $\begingroup$ Thanks for your suggestion! Unfortunately, I think this math is a bit above my level of understanding (I already got lost at the beginning when he said "We know how to find explicit formulas for relational equations like this"). As a note of reference, the method that I used in my attempt was also used here: mathonline.wikidot.com/… in Example 2, which was to find the limit of the ratio of the terms of the Fibonacci Sequence (a problem very similar to the one above!). $\endgroup$ – A is for Ambition Apr 23 '15 at 4:58
  • $\begingroup$ Sorry, if I weren't getting too tired to make reliable calculations I would've tried taking it further. It looks like Dr. MV has done this, though. Terminology aside, the idea is to make an educated guess as to what a formula for the terms might look like and substitute it into the equation. Then you can use the result to derive the details. The same idea is actually used in differential equations. $\endgroup$ – BGreen Apr 23 '15 at 5:02
  • $\begingroup$ Please let me know how I can improve my answer. I just want to give you the best answer I can. $\endgroup$ – Mark Viola Apr 23 '15 at 14:18
1
$\begingroup$

Define the function $$G(x)=\sum_{n=1}^\infty f_n x^n$$ Through some standard generating function techniques, we get $$G(x)={\frac {x}{1-x-x^3}}$$ where the series converges. The series has a radius of convergence equal to $\lim\limits_{n\to\infty}\frac{f_{n}}{f_{n+1}}$. However, the radius of convergence is also the distance to the closest singularity from the centre (in this case 0) in the complex plane. The second form of the function has singularities when the denominator is 0, i.e. $x^3+x-1=0$. The smallest in magnitude is the sole real root $r$ of the cubic. Equating these expressions for the radius of convergence, we have $$\,\,\,\,\,\,\,\,\,\,\,\,\lim_{n\to\infty}\frac{f_{n}}{f_{n+1}}=r\\ \implies \lim_{n\to\infty}\frac{f_{n+1}}{f_{n}}=\frac1r$$ where $r\approx 0.68234$. Notably, this method also implicitly shows that the limit exists in the first place.

Alternative:

Somewhat more along your lines of thinking, let $L=\lim\limits_{n\to\infty}\frac{f_{n+1}}{f_n}$. Now

$$\large{\begin{align} \frac{f_{n+1}}{f_n} &=\frac{f_{n}+f_{n-2}}{f_n}\\ &=1+\frac{1}{\frac{f_{n}}{f_{n-2}}}\\ &=1+\frac{1}{\frac{f_{n-1}+f_{n-3}}{f_{n-2}}}\\ &=1+\frac{1}{\frac{f_{n-1}}{f_{n-2}}+\frac{f_{n-3}}{f_{n-2}}}\\ &=1+\frac{1}{\frac{f_{n-1}}{f_{n-2}}+\frac{1}{\frac{f_{n-2}}{f_{n-3}}}} \end{align}}$$ Notice that for very large $n$,$\frac{f_{n+1}}{f_n}\approx\frac{f_{n-k}}{f_{n-k-1}}$ for integer $k$. Hence we essentially have $$L=1+\frac{1}{L+\frac{1}{L}}\\ \implies L^3-L^2-1=0$$ Since $L$ must be real and the above equation has one real root, the value of the limit is equal to the real root of the above polynomial.

$\endgroup$
  • $\begingroup$ How come you know that "for very large n" the approximation holds true? Also, can you explain how you used standard generating function techniques to turn the sigma function $G(x)$ into $\frac{x}{1-x-x^3}$? $\endgroup$ – A is for Ambition Apr 23 '15 at 17:46
  • $\begingroup$ Actually, let me rephrase my question. I know that the sigma function is the power series of $G(x).$ My question is how did you go from one function to the other? Can you show your work or elaborate on how you were able to find the power series? That's what I'm having trouble with. $\endgroup$ – A is for Ambition Apr 23 '15 at 22:28
  • $\begingroup$ For your first question, the approximation holds because if $n$ is very large, then both of those values are close to the limit already, so the approximation can be made. $\endgroup$ – Pauly B Apr 24 '15 at 1:43
  • 1
    $\begingroup$ As for the second, this question should provide some intuition for certain techniques of this kind: math.stackexchange.com/questions/338740/… $\endgroup$ – Pauly B Apr 24 '15 at 1:44
  • 1
    $\begingroup$ Yup, you are right on both points. I realise that the phrase I meant to say was "centred around $0$", but you figured that out :) $\endgroup$ – Pauly B Apr 24 '15 at 8:39
1
$\begingroup$

You can find a closed-form for the sequence $f_n$ in terms of the roots ($z_1,z_2,z_3$) to the cubic equation $z^3-z^2-1=0$. Two of these roots form a complex conjugate pair.

The solution can be written as

$$f_n=Az_1^n+Bz_2^n+Cz_3^n$$

where the constants $A$, $B$, and $C$ are found from the initial conditions on $f_1$, $f_2$, and $f_3$.

You should be able to directly find the coveted limit

$$\lim_{n\to \infty}\frac{f_{n+1}}{f_n}=\lim_{n\to \infty}\left(\frac{Az_1^{n+1}+Bz_2^{n+1}+Cz_3^{n+1}}{Az_1^n+Bz_2^n+Cz_3^n}\right)$$

Hint: The real root is positive, while the real part of the other roots is negative.

$\endgroup$
1
$\begingroup$

You have a Linear homogeneous recurrence relations with constant coefficients. The standard approach is to assume a solution of the form $f_n=dr^n$ (traditionally the $d$ is an $a$, but I didn't want to use $a$ as you have already). Now plug this into your recurrence, getting $dr^n=dr^{n-1}+dr^{n-3$}$ or $r^3-r^2-1=0$, which we call the characteristic polynomial. You will have one solution for each root of the polynomial. As the sum and multiple of solutions is again a solution, you have (here) a three dimensional vector space of solutions. The one with the largest real part will dominate the long term behavior. In this case you have one real root $\approx 1.4656$ and two conjugate complex roots $\approx -0.23279 \pm 0.79255i$. As $n \to \infty$ the ratio of terms $a_n$ will approach $1.4656$ unless the initial conditions are carefully chosen to give that solution a zero multiplier.

$\endgroup$
  • $\begingroup$ This is the same methodology I adopted. I would bet that there are a host of indirect methods, but this one works just fine! $\endgroup$ – Mark Viola Apr 23 '15 at 5:06
  • $\begingroup$ Hi Ross, can you please explain the concept of how the "real part will dominate the long term behavior?" I don't quite know what you mean by that, though I do understand the rest of you solution. Thanks! $\endgroup$ – A is for Ambition Apr 23 '15 at 18:28
  • $\begingroup$ The solution will be $ar_1^n+br_2^n+cr_3^n$ where $a,b,c$ are determined by the initial conditions and $r_i$ are the roots. As $n$ gets large, the term with the most positive real part, which here is the real root, will dominate over all the others. In this case, the complex roots have negative real parts so they decay to zero as $n$ gets large. $\endgroup$ – Ross Millikan Apr 23 '15 at 19:07

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.