MHB Can the Limit of a Recurrence Relation Problem Approach the Square Root of 2?

[Saitama]

Problem:
Let $a_0$ and $b_0$ be any two positive integers. Define $a_n$, $b_n$ for $n\geq 1$ using the relations $a_n=a_{n-1}+2b_{n-1}$, $b_n=a_{n-1}+b_{n-1}$ and let $c_n=\dfrac{a_n}{b_n}$, for $n=0,1,2,\cdots $.

Write

a)Write $(\sqrt{2}-c_{n+1})$ in terms of $(\sqrt{2}-c_n)$.

b)Show that $|\sqrt{2}-c_{n+1}|<\frac{1}{1+\sqrt{2}}|\sqrt{2}-c_n|$.

c)Show that $\lim_{n\rightarrow \infty}c_n=\sqrt{2}$.

Attempt:
The following equations are given:
$$a_n=a_{n-1}+2b_{n-1}\,\,\,\,(*)$$
$$b_n=a_{n-1}+b_{n-1}\,\,\,\,\,(**)$$
Subtract the two to obtain:
$$a_n-b_n=b_{n-1}$$
From $(**)$, I can write $b_{n+1}-b_n=a_n$. Substituting this in above gives:
$$b_{n+1}-2b_n-b_{n-1}=0$$
The solution to above recurrence relation is: $b_n=A(1+\sqrt{2})^n+B(1-\sqrt{2})^n$ where $A$ and $B$ are constants. Since $b_{n+1}-b_n=a_n$, I also have: $a_n=\sqrt{2}\left(A(1+\sqrt{2})^n-B(1-\sqrt{2})^n\right)$. Hence,
$$c_n=\sqrt{2}\frac{A(1+\sqrt{2})^n-B(1-\sqrt{2})^n}{A(1+\sqrt{2})^n+B(1-\sqrt{2})^n}$$
I can easily solve the c) part from the above.

I tried writing down the expressions for $\sqrt{2}-c_n$ and $\sqrt{2}-c_{n+1}$ but I don't see how to relate the two.
$$\sqrt{2}-c_n=\frac{2\sqrt{2}B(1-\sqrt{2})^n}{A(1+\sqrt{2})^n+B(1-\sqrt{2})^n}$$
$$\sqrt{2}-c_{n+1}=\frac{2\sqrt{2}B(1-\sqrt{2})^{n+1}}{A(1+\sqrt{2})^{n+1}+B(1-\sqrt{2})^{n+1}}$$
I don't see where to proceed from here.

Any help is appreciated. Thanks!

 

[chisigma]

Problem:
Let $a_0$ and $b_0$ be any two positive integers. Define $a_n$, $b_n$ for $n\geq 1$ using the relations $a_n=a_{n-1}+2b_{n-1}$, $b_n=a_{n-1}+b_{n-1}$ and let $c_n=\dfrac{a_n}{b_n}$, for $n=0,1,2,\cdots $.

Write

a)Write $(\sqrt{2}-c_{n+1})$ in terms of $(\sqrt{2}-c_n)$.

b)Show that $|\sqrt{2}-c_{n+1}|<\frac{1}{1+\sqrt{2}}|\sqrt{2}-c_n|$.

c)Show that $\lim_{n\rightarrow \infty}c_n=\sqrt{2}$.

In my opinion the first step is to find the $a_{n}$ and $b_{n}$ in the following way. Defining $\overrightarrow{x}_{n}= (a_{n},b_{n})$ You have the difference equation...

$\displaystyle \overrightarrow{x}_{n+1} =\overrightarrow{x}_{n}\ A\ (1)$

...where...

$\displaystyle A = \left | \begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix} \right |\ (2)$

The solution of (1) is...

$\displaystyle \overrightarrow{x}_{n} = \overrightarrow{x}_{0}\ A^{n}\ (3)$

Kind regards$\chi$ $\sigma$

 

[Saitama]

In my opinion the first step is to find the $a_{n}$ and $b_{n}$ in the following way. Defining $\overrightarrow{x}_{n}= (a_{n},b_{n})$ You have the difference equation...

$\displaystyle \overrightarrow{x}_{n+1} =\overrightarrow{x}_{n}\ A\ (1)$

...where...

$\displaystyle A = \left | \begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix} \right |\ (2)$

The solution of (1) is...

$\displaystyle \overrightarrow{x}_{n} = \overrightarrow{x}_{0}\ A^{n}\ (3)$

Kind regards$\chi$ $\sigma$

I have no idea what you did there.

Is it not possible to continue with my approach?

 

[Opalg]

Is it not possible to continue with my approach?

Instead of subtracting (**) from (*), have you tried dividing (*) by (**)? You will get $$ c_{n+1} = \frac{a_{n+1}}{b_{n+1}} = \frac{a_n+2b_n}{a_n + b_n} = \frac{c_n + 2}{c_n + 1}.$$ Then $$\sqrt2 - c_{n+1} = \sqrt2 - \frac{c_n + 2}{c_n + 1}.$$ Put the right-hand side of that over a common denominator and you will get some sort of an answer to (a). I think that this must be what the question setter had in mind, rather than finding explicit expressions for $\sqrt2 - c_{n+1}$ and $\sqrt2 - c_{n}$ (which as you have discovered are quite complicated).

 

[Saitama]

Instead of subtracting (**) from (*), have you tried dividing (*) by (**)? You will get $$ c_{n+1} = \frac{a_{n+1}}{b_{n+1}} = \frac{a_n+2b_n}{a_n + b_n} = \frac{c_n + 2}{c_n + 1}.$$ Then $$\sqrt2 - c_{n+1} = \sqrt2 - \frac{c_n + 2}{c_n + 1}.$$ Put the right-hand side of that over a common denominator and you will get some sort of an answer to (a). I think that this must be what the question setter had in mind, rather than finding explicit expressions for $\sqrt2 - c_{n+1}$ and $\sqrt2 - c_{n}$ (which as you have discovered are quite complicated).

No, I did not think of dividing them.

Rearranging, I get:
$$\sqrt{2}-c_{n+1}=\frac{(\sqrt{2}-c_n)(1-\sqrt{2})}{c_n+1}$$
This solve a).

$$\Rightarrow |\sqrt{2}-c_{n+1}|=\left|\frac{(\sqrt{2}-c_n)(1-\sqrt{2})}{c_n+1}\right|=\frac{1}{1+\sqrt{2}}\left|\frac{\sqrt{2}-c_n}{c_n+1}\right|$$
How to show that the inequality holds?

 

[Saitama]

Opalg, can you please give me some hints about the inequality part? I honestly don't know how to show that. :(

 

[Opalg]

can you please give me some hints about the inequality part?

Divide (*) by (**) to get $$ c_{n+1} = \frac{a_{n+1}}{b_{n+1}} = \frac{a_n+2b_n}{a_n+b_n} = \frac{c_n+2}{c_n+1}.$$ It follows that $$\bigl|\sqrt2-c_{n+1}\bigr| = \Bigl|\frac{\sqrt2(c_n+1) - (c_n+2)}{c_n+1}\Bigr| = \frac{\bigl|(\sqrt2-1)c_n - \sqrt2(\sqrt2-1)\bigr|}{c_n + 1} = \frac{(\sqrt2 - 1)\bigl|c_n-\sqrt2\bigr|}{c_n+1} < (\sqrt2 - 1)\bigl|c_n-\sqrt2\bigr|$$ (because $c_n>0$ and so the denominator of that fraction is greater than $1$). Also, $\sqrt2 - 1 = \frac{(\sqrt2 - 1)(\sqrt2 + 1)}{\sqrt2 + 1} = \frac1{\sqrt2 + 1},$ so that $$\bigl|\sqrt2-c_{n+1}\bigr| < \tfrac1{\sqrt2 + 1}\bigl|c_n-\sqrt2\bigr|.$$

 

[Saitama]

Divide (*) by (**) to get $$ c_{n+1} = \frac{a_{n+1}}{b_{n+1}} = \frac{a_n+2b_n}{a_n+b_n} = \frac{c_n+2}{c_n+1}.$$ It follows that $$\bigl|\sqrt2-c_{n+1}\bigr| = \Bigl|\frac{\sqrt2(c_n+1) - (c_n+2)}{c_n+1}\Bigr| = \frac{\bigl|(\sqrt2-1)c_n - \sqrt2(\sqrt2-1)\bigr|}{c_n + 1} = \frac{(\sqrt2 - 1)\bigl|c_n-\sqrt2\bigr|}{c_n+1} < (\sqrt2 - 1)\bigl|c_n-\sqrt2\bigr|$$ (because $c_n>0$ and so the denominator of that fraction is greater than $1$). Also, $\sqrt2 - 1 = \frac{(\sqrt2 - 1)(\sqrt2 + 1)}{\sqrt2 + 1} = \frac1{\sqrt2 + 1},$ so that $$\bigl|\sqrt2-c_{n+1}\bigr| < \tfrac1{\sqrt2 + 1}\bigl|c_n-\sqrt2\bigr|.$$

Thank you Opalg! It was silly of me for not noticing that $c_n>0$.