Finding the limit of the sequence $T_1=0,T_2=1, T_n=\frac{T_{n-1}+T_{n-2}}{2}$ Given that $T_1=0$, $T_2=1$ and $T_n=\frac{T_{n-1}+T_{n-2}}{2}$, show that the sequence converges to $\frac{2}{3}$.
 A: Start from the matrix representation of the problem
$$\begin{bmatrix}
T_{n} & T_{n-1} 
\end{bmatrix}=\begin{bmatrix}
T_{n-1} & T_{n-2} 
\end{bmatrix}
\begin{bmatrix}
 \frac{1}{2}& 1\\ 
 \frac{1}{2}& 0
\end{bmatrix}$$
$$\begin{bmatrix}
T_{2} & T_{1} 
\end{bmatrix}=\begin{bmatrix}
1 & 0 
\end{bmatrix}$$
Chaining it all you have
$$\begin{bmatrix}
T_{n} & T_{n-1} 
\end{bmatrix}=\begin{bmatrix}
T_{2} & T_{1} 
\end{bmatrix}
\begin{bmatrix}
 \frac{1}{2}& 1\\ 
 \frac{1}{2}& 0
\end{bmatrix}^{n-2}$$
So it all comes down to finding
$$\lim\limits_{n \to \infty}
\begin{bmatrix}
 \frac{1}{2}& 1\\ 
 \frac{1}{2}& 0
\end{bmatrix}^{n}$$
Now this part is really classical and you just find eigenvalues of the matrix $\lambda_{1}=-\frac{1}{2}$,$\lambda_{2}=1$ and diagonalize
$$
\begin{bmatrix}
 \frac{1}{2}& 1\\ 
 \frac{1}{2}& 0
\end{bmatrix}=\begin{bmatrix}
 -1 & 2\\ 
  1 & 1
\end{bmatrix}
\begin{bmatrix}
 -\frac{1}{2}& 0\\ 
 0 & 1
\end{bmatrix}
\begin{bmatrix}
 -\frac{1}{3} & \frac{2}{3}\\ 
 \frac{1}{3} & \frac{1}{3}
\end{bmatrix}$$
to have
$$\lim\limits_{n \to \infty}
\begin{bmatrix}
 -1 & 2\\ 
  1 & 1
\end{bmatrix}
\begin{bmatrix}
 -\frac{1}{2}& 0\\ 
 0 & 1
\end{bmatrix}^{n}
\begin{bmatrix}
 -\frac{1}{3} & \frac{2}{3}\\ 
 \frac{1}{3} & \frac{1}{3}
\end{bmatrix}=\lim\limits_{n \to \infty}
\begin{bmatrix}
 -1 & 2\\ 
  1 & 1
\end{bmatrix}
\begin{bmatrix}
 (-\frac{1}{2})^{n}& 0\\ 
 0 & 1
\end{bmatrix}
\begin{bmatrix}
 -\frac{1}{3} & \frac{2}{3}\\ 
 \frac{1}{3} & \frac{1}{3}
\end{bmatrix}=$$
$$\begin{bmatrix}
 -1 & 2\\ 
  1 & 1
\end{bmatrix}
\begin{bmatrix}
 0 & 0\\ 
 0 & 1
\end{bmatrix}
\begin{bmatrix}
 -\frac{1}{3} & \frac{2}{3}\\ 
 \frac{1}{3} & \frac{1}{3}
\end{bmatrix}=\frac{1}{3}\begin{bmatrix}
 2 & 2\\ 
 1 & 1
\end{bmatrix}$$
This is giving
$$\lim\limits_{n \to \infty}\begin{bmatrix}
1 & 0 
\end{bmatrix}
\begin{bmatrix}
 \frac{1}{2}& 1\\ 
 \frac{1}{2}& 0
\end{bmatrix}^{n-2}=\begin{bmatrix}
1 & 0 
\end{bmatrix}\frac{1}{3}\begin{bmatrix}
 2 & 2\\ 
 1 & 1
\end{bmatrix}=\begin{bmatrix}
 \frac{2}{3} & \frac{2}{3}
\end{bmatrix}$$
which means that the series converges to $\frac{2}{3}$
A: Hint: $2T_n+T_{n-1}$ remains constant. Hence, once you show the series converges, you know the limit $T$ will give the value $2T+T$ equal to this constant.
A: The typical way of solving such recurrence is to take the ansatz as $T_n \sim a^n$. We then have
$$a^n = \dfrac{a^{n-1}+a^{n-2}}2 \implies 2a^2 = a+1 \implies 2a^2-a-1=0 \implies (a-1)(2a+1) = 0$$
Hence, the solution is given by
$$T_n = c \cdot 1^n + d \cdot \left(-\dfrac12\right)^n = c+d\left(-\dfrac12\right)^n$$
Setting $T_1 = 0$ and $T_2 = 1$, we obtain
$$c-\dfrac{d}2 = 0 \text{ and }c + \dfrac{d}4 = 1$$
which gives us $c=\dfrac23$ and $d=\dfrac43$. Taking the limit as $n \to \infty$, we obtain
$$\lim_{n \to \infty} T_n = c = \dfrac23$$
A: I am quite a fan of the following solution: We fist show that the sequence converges for arbitrary two starting values and then derive the limit indirectly from its dependence on the starting values.
Let $a,b \in \mathbb{R}$ and define the sequence $(c_n)_{n \in \mathbb{N}}$ by $c_0 = a$, $c_1 = b$ and $c_{n+2} = (c_n + c_{n+1})/2$ for all $n \in \mathbb{N}$. Then for all $n \geq 1$ we have
$$
 | c_{n+1} - c_{n} |
 = \left| \frac{c_n + c_{n-1}}{2} - c_n \right|
 = \frac{|c_n-c_{n-1}|}{2}
$$
and thus
$$
 | c_{n+1} - c_{n} |
 = \frac{|c_n-c_{n-1}|}{2}
 = \frac{|c_{n-1}-c_{n-2}|}{4}
 = \dotsb
 = \frac{|c_1-c_0|}{2^n}
 = \frac{|b-a|}{2^n}.
$$
It follows that for all $m \geq n \geq 1$ we have
$$
 |c_m - c_n|
 \leq \sum_{k=n}^{m-1} |c_{k+1}-c_k|
 = \sum_{k=n}^{m-1} \frac{|b-a|}{2^k}
 \leq \sum_{k=n}^\infty \frac{|b-a|}{2^k}
 = \frac{|b-a|}{2^{n-1}}.
$$
Thus the sequence $(c_n)_{n \in \mathbb{N}}$ is a Cauchy sequence and thus converges.
We can now calculate the limit in a rather nice way: For all $a,b \in \mathbb{R}$ let $\Phi(a,b) \in \mathbb{R}$ denote the limit of the above sequence with start values $a$ and $b$. We want to show that $\Phi(0,1) = \frac{2}{3}$.
For this notice that from the properties of convergent series and the special form of our sequence it directly follows that for all $a,b,c \in \mathbb{R}$ we have
$$
 \Phi(a+c,b+c) = \Phi(a,b) +c, \quad
 \Phi(ca,cb)= c\, \Phi(a,b), \quad
 \Phi(a,b) = \Phi\left(b, \frac{a+b}{2}\right)
$$
From this we can now follow that
\begin{align*}
 \Phi(0,1)
 = \frac{1}{2} \Phi(0,2)
 = \frac{1}{2} \Phi(2,1)
 = \frac{1}{2} \Phi(0,-1) + 1
 = -\frac{1}{2} \Phi(0,1) + 1.
\end{align*}
Comparing the left and right hand side of the above equality yields $\Phi(0,1) = \frac{2}{3}$.
From this we find even more generally that for all $a,b \in \mathbb{R}$ we have
$$
 \Phi(a,b)
 = \Phi(0,b-a) + a
 = (b-a) \Phi(0,1) + a
 = \frac{2}{3}(b-a) + a
 = \frac{2b+a}{3}.
$$
