Proof that the sequence defined by the average of the last two terms is convergent.

Question

$a_n=\frac{a_{n-1}+a_{n-2}}{2} \ \ a_1,a_2\in\mathbb{R}$

It would mean so much if someone could try and understand my proof and tell me if it is correct, if you have a more direct proof please share but also it'd be really nice if someone could tell me if my logic works, thanks, here is my proof:

We will first prove the following fact: each pair $a_n$ and $a_{n+1}$ form a pair of lower and upper bounds for the rest of the sequence.

Notice:

(i) $a_n>a_{n+1}\implies a_n > a_{n+2} > a_{n+1}$

Now, assume $a_n > a_{n+1}$, the same proof with minor alterations can be proved in the case that $a_n<a_{n+1}$, the case where $a_n=a_{n+1}$ is trivial.

By (i) $a_n>a_{n+2}>a_{n+1}$
By (i) $a_n>a_{n+2}>a_{n+3}>a_{n+1}$
By (i) $a_n>a_{n+2}>a_{n+4}>a_{n+3}>a_{n+1}$

And so on, by induction forall $n$, $a_n$ and $a_{n+1}$ are bounds, now it is clear by this fact that every second $a_n$ forms an upper bound and every other $a_n$ forms a lower bound, denote these two subsequences $l_n$ for the lower bounds of $a_n$ and $u_n$ for the upper bounds of $a_n$, we are to prove that these two sequences are convergent to the same value, meaning $a_n$ is cauchy, meaning $a_n$ is convergent.

It is clear that $u_n$ is monotonically decreasing and $l_n$ is monotonically increasing, and that $u_n>l_n$, meaning they're bounded. Assume for a contradiction that $\text{inf}(u_n)\neq\text{sup}(l_n)$, allow $G=\frac{\text{inf}(u_n)+\text{sup}(l_n)}{2}$ and $\epsilon=|\text{inf}(u_n)-\text{sup}(l_n)|$, by the definion of supremem and infinum $\exists l_n > \text{sup}(l_n)-\epsilon$ and $\exists u_{n} < \text{inf}(u_n)+\epsilon$, by the definition of $a_n$, $a_{n+1}=\frac{u_n+l_n}{2}=\frac{\text{sup}(l_n)+\kappa+\text{inf}(u_n)-\phi}{2}=G+\frac{\kappa-\phi}{2}$ such that $\frac{\kappa-\phi}{2}<\frac{\epsilon}{2}$ meaning there exists $a_n$ inbetween inf$(u_n)$ and sup$(l_n)$, a contradiction. $\square$

Answer 1

Your logic is correct, but it can be made a bit cleaner. $$ \begin{align} a_n &=\frac{a_{n-1}+a_{n-2}}2\tag{1a}\\ &=\frac{\frac{a_{n-2}+a_{n-3}}2+a_{n-2}}2\tag{1b}\\ &=\frac{3a_{n-2}+a_{n-3}}4\tag{1c}\\ &=\frac{3a_{n-2}+(2a_{n-2}-a_{n-4})}4\tag{1d}\\ &=\frac{5a_{n-2}-a_{n-4}}4\tag{1e} \end{align} $$ Explanation:
$\text{(1a):}$ given recurrence
$\text{(1b):}$ apply the recurrence to $a_{n-1}$
$\text{(1c):}$ simplify
$\text{(1d):}$ solve $a_{n-2}=\frac{a_{n-3}+a_{n-4}}2$
$\phantom{\text{(1d):}}$ to get $a_{n-3}=2a_{n-2}-a_{n-4}$
$\text{(1e):}$ simplify

Subtract $a_{n-2}$ from both sides of $(1)$: $$ a_n-a_{n-2}=\frac{a_{n-2}-a_{n-4}}4\tag2 $$ Thus, if we look at every other term, the sequence is monotone, whether increasing or decreasing, and the difference between terms is reduced by a factor of $4$ as the indices are increased by $2$.

Applying induction to $(2)$, we get $$ a_{2n+3}-a_{2n+1}=\frac{a_3-a_1}{4^n}\tag3 $$ We can sum $(3)$ to get $$ \begin{align} a_{2n+1}-a_1 &=\sum_{k=0}^{n-1}(a_{2k+3}-a_{2k+1})\tag{4a}\\ &=(a_3-a_1)\sum_{k=0}^{n-1}\frac1{4^k}\tag{4b}\\ &=\frac{1-\frac1{4^n}}{1-\frac14}(a_3-a_1)\tag{4c} \end{align} $$ Taking the limit as $n\to\infty$, we get $$ \begin{align} \lim_{n\to\infty}a_{2n+1} &=\frac43(a_3-a_1)+a_1\tag{5a}\\ &=\frac{4a_3-a_1}3\tag{5b}\\ &=\frac{2(a_2+a_1)-a_1}3\tag{5c}\\ &=\frac{2a_2+a_1}3\tag{5d} \end{align} $$ We get the same result looking at the limit of the even terms.

---

Linear Recurrence Approach

The characteristic equation for the linear recurrence $$ a_n=\frac{a_{n-1}+a_{n-2}}2\tag6 $$ is $$ x^2-\frac12x-\frac12=0\tag7 $$ which has roots $1$ and $-\frac12$. Thus, the solution is $$ a_n=b+\left(-\frac12\right)^nc\tag8 $$ If we know $a_1$ and $a_2$, we can use $(8)$ to set up two equations in two unknowns, then solve to get $b$ and $b$. Plugging these $b$ and $c$ into $(8)$ gives $$ a_n=\frac13(a_1+2a_2)-\left(-\frac12\right)^n\frac43(a_1-a_2)\tag9 $$ It is simple to verify that $(4)$ holds for $n=1$ and $n=2$. It is not too hard to verify that $(4)$ also satisfies the recurrence $(6)$. Furthermore, $$ \lim_{n\to\infty}a_n=\frac13(a_1+2a_2)\tag{10} $$