convergence of a fibonacci-like sequence

Question

I posted a question earlier on finding a formula for the sequence

$$t_1, t_2, t_1+t_2, t_1+2t_2,....$$

This is the question I posted earlier

I want to show that as $n\rightarrow \infty$, $\frac{t_{n+1}}{t_n} \rightarrow \phi$

The relationship is $T_n = A_nF_{n-2} +B_n F_{n_1}$

Where $A_1=1, A_2=0, A_{n+2} = A_{n+1}+A_{n}$ and

$B_1=0, B_2=1, B_{n+2} = B_{n+1}+B_{n}$

Since $A_n=F_{n-2}$ and $B_n = F_{n-1}$ then

$T_n = t_1 F_{n-2}+t_nF_{n-1}$

I'm wondering if this proof will work. I know that this sequence is like Fibonacci and it converges to the golden ratio...

suppose as $n \rightarrow \infty$, $F_{n+1}/F_n$ converges to a limit $L$.

Then: $L = \lim_{n\rightarrow \infty} \frac{F_{n+1}}{F_n} = \lim_{n\rightarrow \infty} 1 +\frac {1}{L}$

So I solve $L=1+\frac{1}{L} \implies L=\frac{1\pm\sqrt{5}}{2}$

We take the positive root so the answer is $\phi$

The reason i am confused is because this is for convergence $\frac{F_{n+1}}{F_n}$ but my sequence isn't exactly this.

Answer 1

From linear recurrence theory, as characteristic polynomial of the sequence is $x^2 - x - 1$ and it's roots are $\frac{1 \pm \sqrt{5}}{2}$, we have $t_n = A \left(\frac{1 + \sqrt{5}}{2}\right)^n + B \left(\frac{1 - \sqrt{5}}{2}\right)^n$ where $A$ and $B$ can be found from $t_1$ and $t_2$. If $A \neq 0$ then $\lim\limits_{n \to \infty} \frac{t_{n + 1}}{t_n} = \lim\limits_{n\to \infty} \left[\frac{1 + \sqrt{5}}{2} + \frac{B}{A}(\frac{1 - \sqrt{5}}{1 + \sqrt{5}})^n\right] / \left[1 + \frac{B}{A}(\frac{1 - \sqrt{5}}{1 + \sqrt{5}})^n\right] = \frac{1 + \sqrt{5}}{2}$ (because $|\frac{1 - \sqrt{5}}{1 + \sqrt{5}}| < 1$), otherwise it is $\frac{1 - \sqrt{5}}{2}$.

And if $A = 0$ then $t_1$ and $t_2$ have different signs - so if they are both positive, $A \neq 0$.

Answer 2

What you are looking for is practically a Fibonacci recurrence, with starting values different from $F_1=1,\; F_2=1$, like it is for Lucas sequence .
Clearly, if your $T_1 , T_2$ happens to be equal to two consecutive F's, then you just have a shifted Fibonacci Sequence.

Also in your case we have the matrix relation $$ \left( {\matrix{ {T_{\,k + 2} } \cr {T_{\,k + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {T_{\,k + 1} } \cr {T_{\,k} } \cr } } \right)\quad \Rightarrow \quad \left( {\matrix{ {T_{n + 2} } \cr {T_{\,n + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ {T_{\,2} } \cr {T_{\,1} } \cr } } \right) $$

The matrix elevated to $n$ can also be written as $$ \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} = \left( {\matrix{ {F_{\,n + 1} } & {F_{\,n} } \cr {F_{\,n} } & {F_{\,n - 1} } \cr } } \right) $$ therefore $$ {{T_{n + 2} } \over {T_{\,n + 1} }} = {{T_{\,2} F_{\,n + 1} + T_{\,1} F_{\,n} } \over {T_{\,2} F_{\,n} + T_{\,1} F_{\,n - 1} }} = {{\left( {T_{\,2} + T_{\,1} } \right)F_{\,n} + T_{\,2} F_{\,n - 1} } \over {T_{\,2} F_{\,n} + T_{\,1} F_{\,n - 1} }} = {{\left( {T_{\,2} + T_{\,1} } \right)F_{\,n} /F_{\,n - 1} + T_{\,2} } \over {T_{\,2} F_{\,n} /F_{\,n - 1} + T_{\,1} }} $$ and the limit follows easily

Also refer to the para. "Closed-form expression" in the Wikipedia article

--- answer to your comment ---

The vectorial representation is just a translation of the recursive identity (plus an obvious one) $$ \left\{ \matrix{ T_{\,n + 2} = T_{\,n + 1} + T_{\,n} \hfill \cr T_{\,n + 1} = T_{\,n + 1} \hfill \cr} \right.\quad \Rightarrow \quad \left( {\matrix{ {T_{\,n + 2} } \cr {T_{\,n + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right) \left( {\matrix{ {T_{\,n + 1} } \cr {T_{\,n} } \cr } } \right) $$ which has the advantage that multiple recursion steps are translated into matrix multiplication (power) $$ \eqalign{ & \left( {\matrix{ {T_{\,n + 2} } \cr {T_{\,n + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {T_{\,n + 1} } \cr {T_{\,n} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {T_{\,n} } \cr {T_{\,n - 1} } \cr } } \right) = \cdots = \cr & = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ {T_{\,2} } \cr {T_{\,1} } \cr } } \right) \cr} $$

Since the Fibonacci N. obey to the same recurrence $$ \eqalign{ & \left( {\matrix{ {F_{\,n + 2} } \cr {F_{\,n + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ {F_{\,2} } \cr {F_{\,1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ 1 \cr 1 \cr } } \right)\quad \Rightarrow \cr & \Rightarrow \quad \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} = \left( {\matrix{ {F_{\,n + 1} } & {F_{\,n} } \cr {F_{\,n} } & {F_{\,n - 1} } \cr } } \right) \cr} $$ and $$ \eqalign{ & \left( {\matrix{ {T_{n + 2} } \cr {T_{\,n + 1} } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)^{\,n} \left( {\matrix{ {T_{\,2} } \cr {T_{\,1} } \cr } } \right) = \left( {\matrix{ {F_{\,n + 1} } & {F_{\,n} } \cr {F_{\,n} } & {F_{\,n - 1} } \cr } } \right)\left( {\matrix{ {T_{\,2} } \cr {T_{\,1} } \cr } } \right)\quad \Rightarrow \cr & \Rightarrow \quad \left\{ \matrix{ T_{\,n + 2} = T_{\,2} F_{\,n + 1} + T_{\,1} F_{\,n} = T_{\,2} F_{\,n} + T_{\,2} F_{\,n - 1} + T_{\,1} F_{\,n} \hfill \cr T_{\,n + 1} = T_{\,2} F_{\,n} + T_{\,1} F_{\,n - 1} \hfill \cr} \right. \cr} $$