Analysis for Realsies: 5

Hey guys! I hope that you've been having a good semester break. I...had a picnic on campus today? Totes the right weather for picnics, right? =P

I think that a few weeks ago, we had a look at question about Fibonacci numbers in our tute, and the solution sheet doesn't provide an actual solution for it. Soooooooo...here we go!

First, the question:

"You have seen the Fibonacci sequence, defined by \(f_{n+2}=f_{n+1}+f_n\) with \(f_1=f_2=1\). Now define a new sequence as follows: \begin{align}g_n=\frac{f_{n+1}}{f_n}.\end{align} Find the limit of this sequence (you should try to prove that the limit exists first). Do you recognise the limit? Is there something special about it?"

Okay, so I can see at least two ways to do this problem. The usual first-year-accelerated-maths-1 approach would be to use solve for the Fibonacci sequence as a second-order difference equation. Doing this, you get: \begin{align} f_n=\frac{1}{\sqrt{5}}(\phi^n-(-\phi)^{-n}),\text{ where }\phi=\frac{1+\sqrt{5}}{2}\text{ is the golden ratio.} \end{align} And it's pretty straightforward to work out that the limit \begin{align}\lim_{n\rightarrow\infty} g_n=\lim_{n\to\infty}\frac{\phi^{(n+1)}-(-\phi)^{-(n+1)}}{\phi^n-(-\phi)^{-n}}=\phi.\end{align}

Happily, in this course, you guys don't learn about difference equations, so we totes get to do it in a different way! So, first thing's first, let's use the monotone convergence theorem to show that this sequence converges. Observe that \begin{align} g_n=\frac{f_{n+1}}{f_n}=\frac{f_{n-1}+f_n}{f_n}=\frac{1+\left(\frac{f_n}{f_{n-1}}\right)}{\left(\frac{f_n}{f_{n-1}}\right)}=\frac{1+g_{n-1}}{g_{n-1}}.\end{align} Taking this one step further by replacing \(g_{n-1}\) with \(\frac{1+g_{n-2}}{g_{n-2}}\), we obtain that: \begin{align} g_n=\frac{1+2g_{n-2}}{1+g_{n-2}}=1+\frac{g_{n-2}}{1+g_{n-2}}=2-\frac{1}{1+g_{n-2}}.\end{align} Since \(f_n\) is always positive, \(g_n\) (as a fraction of two positive numbers) is always positive. And for positive numbers, \(\frac{1}{1+x}>0\), so the above equation tells us that the sequence \(\{g_n\}\) is bounded between \(1\) and \(2\) (although you do need to check \(g_1\) and \(g_2\) separately, because they don't necessarily satisfy the above recursion). Now, we'd love to apply the monotone convergence theorem, but the actual sequence isn't monotonic. Thankfully, the odd indexed terms are increasing, and the even indexed terms are decreasing, which means that we can still apply the theorem to these odd and even index subsequences.

As an example, let's prove (by induction) that the odd terms are increasing.

Consider the statements \(P(n): g_{2n+1}>g_{2n-1}\). For \(n=1\), this is true \(g_3=\frac{3}{2}>1=g_1\). So, we've checked the "base case" of our induction proof. Let's check the "induction step". Assume that \(P(k)\) is true. This means that: \begin{align}g_{2k+1}&>g_{2k-1}\\ \Rightarrow 1+g_{2k+1}&>1+g_{2k-1}\\ \Rightarrow \frac{1}{1+g_{2k+1}}&<\frac{1}{1+g_{2k-1}}\\ \Rightarrow 2-\frac{1}{1+g_{2k+1}}&>2-\frac{1}{1+g_{2k-1}}\\ \Rightarrow g_{2k+3}&>g_{2k+1}. \end{align} And so we see that \(P(k)\Rightarrow P(k+1)\), and so by the principle of mathematical induction, \(P(n)\) is true for all natural numbers \(n\). That is: the odd indexed terms are increasing.

Similarly, YOU can show that the even terms are decreasing. =)

So, the subsequence \(\{g_{2n-1}\}\) converges to some \(g\). Specifically, \begin{align} g=\lim_{n\to\infty}g_n=\lim_{n\to\infty}2-\frac{1}{1+g_{n-2}}=2-\frac{1}{1+g}.\end{align} Solving for \(g\), we get: \begin{align} g=\frac{1\pm\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}.\end{align} We take the positive square root as \(g\) needs to be greater than or equal to \(1\). Similarly, the subsequence \(\{g_{2n}\}\) converges to the same \(g\), which of course, is the golden ratio \(\phi\).

Finally, we need to show that the fact that these two subsequences both converge to \(g=\phi\), means that the whole sequence \(g_n\) converges to \(\phi\). And...let's do this the fun way: \(\epsilon-N\). Huzzah! Okay, so, the fact that \(\{g_{2n-1}\}\) converges to \(\phi\) means that: for every \(\epsilon>0\), there exists some \(N_{odd}\in\mathbb{N}\) such that \(\forall n>N_{odd}\), \(|g_{2n-1}-\phi|<\epsilon\). Similarly, the fact that \(\{g_{2n}\}\) converges to \(\phi\) means that: for every \(\epsilon>0\), there exists some \(N_{even}\in\mathbb{N}\) such that \(\forall n>N_{even}\), \(|g_{2n}-\phi|<\epsilon\). Thus, for every \(\epsilon>0\), there exists a natural number \(N=\max\{2N_{odd}-1,2N_{even}\}\) such that \(\forall n>N\), \begin{align} |g_n-\phi|=\left\{\right. \begin{array}{c c} |g_{2n_1-1}-\phi| <\epsilon, & \text{ if the index }n=2n_1-1\text{ is odd, and} \\ |g_{2n_2}-\phi|<\epsilon, & \text{ if the index }n=2n_2\text{ is even.}\end{array}\end{align} This is precisely the \(\epsilon-N\) definition of convergence, and we're done.

HURRAY!

So easy, right? =P