# convergence of a fibonacci-like sequence

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.

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

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}

• I'm confused about the matric relation because I don't know why you decided to raise it to the nth power. and the last line you have with $\frac{T_{n+2}}{T_{n+1}}$, where are you getting that equality from? i'm just wondering which matrices you are multiplying to get that May 20 '19 at 2:25
• also am i looking for the pell numbers in the lucas sequence? May 20 '19 at 2:26
• @user130306: I added some "slow motion" clarifications: hope they are "enlighting" May 20 '19 at 11:20

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$$.

• sorry i'm just a little confused, how did you get the equation for $t_n$ I looked at the link you provided and I'm still confused. May 20 '19 at 2:23
• Sorry, I for some reason was certain there is closed form solution on this page. Link refers to Wikipedia now, which definitely includes such formula. May 20 '19 at 11:05
• thanks for the clarification. also, when you say you can find $A$ and $B$ from $t_1$ and $t_2$ what exactly does that mean? just pick n as 1 and 2 and substitute? also why does the limit hold for $A\neq 0$ ? May 20 '19 at 21:14
• For $A$ and $B$ does my definition for those sequences work? can I just state those values for $A_n$ and $B_n$ instead of solving for them by using $t_1, t_2$? May 20 '19 at 21:15
• Yes, you just pick two values for $n$ and solver linear system. I edited post to be add one extra transition for limit if $A \neq 0$. $A$ and $B$ in general form are different from your $A_n$ and $B_n$. And of course you can define the sequence by setting $A$ and $B$ instead of $t_1$ and $t_2$. May 20 '19 at 21:42