1. ## recursive sequence

Suppose a sequence is defined by $\displaystyle a_0 = 0$, $\displaystyle a_1 = 1$, and $\displaystyle a_{n+1} = \frac{1}{2}\left(a_{n}+a_{n-1}\right)$ for $\displaystyle n \geq 2$. Prove $\displaystyle a_n$ converges and determine its limit.

So $\displaystyle a_n = \frac{1}{2}\left(a_{n-1}+a_{n-2} \right)$. This means that for all $\displaystyle \varepsilon > 0$, there exists $\displaystyle N \in \mathbb{N}$, such that whenever $\displaystyle n \geq N$, then $\displaystyle |a_{n}-L| < \varepsilon$ and $\displaystyle |a_{n+1}-L| < \varepsilon$.

Is this the right way to go about proving it?

2. Originally Posted by particlejohn
So $\displaystyle a_n = \frac{1}{2}\left(a_{n-1}+a_{n-2} \right)$. This means that for all $\displaystyle \varepsilon > 0$, there exists $\displaystyle N \in \mathbb{N}$, such that whenever $\displaystyle n \geq N$, then $\displaystyle |a_{n}-L| < \varepsilon$ and $\displaystyle |a_{n+1}-L| < \varepsilon$.

Is this the right way to go about proving it?
Yes I believe thats ok... Its induction isnt it?

Originally Posted by particlejohn
Suppose a sequence is defined by $\displaystyle a_0 = 0$, $\displaystyle a_1 = 1$, and $\displaystyle a_{n+1} = \frac{1}{2}\left(a_{n}+a_{n-1}\right)$ for $\displaystyle n \geq 2$. Prove $\displaystyle a_n$ converges and determine its limit.

Well there could be different ways to the limit, i tried the hardest way out there. I actually found out the sequence explicitly

There are different approaches, one of them is using generating functions and the other is by redefining the sequence and simple algebraic tricks.

I will do it using generating functions,

Let $\displaystyle f(x) = \sum_{k=0}^{k=\infty} a_k x^k$

This means $\displaystyle f(x) - \frac{xf(x)+x^2f(x)}2 = a_0 + \left(a_1 - \frac{a_0}{2}\right)x+ \sum_{k=2}^{k=\infty} \left(a_k - \frac{a_{k-1} + a_{k-2}}2\right) x^k$

But for our series, $\displaystyle \forall k \ge 2, a_k - \frac{a_{k-1} + a_{k-2}}2 = 0$. And $\displaystyle a_1 = 1, a_0 = 0$.

Thus,
$\displaystyle f(x) - \frac{xf(x)+x^2f(x)}2 = x$

$\displaystyle f(x) = \dfrac{2x}{2 - x - x^2} = \dfrac{2x}{(1-x)(x+2)} = \frac23\left(-\dfrac{1}{1 + \frac{x}2} + \dfrac{1}{1-x}\right)$

Clearly both can be represented as geometric progressions. And also the above function exists for some values of x(its called the region of convergence)

$\displaystyle -\dfrac{1}{1 + \frac{x}2} = -\sum_{k=0}^{k=\infty} \left(\frac{-x}{2}\right)^k$

$\displaystyle \dfrac{1}{1-x} = \sum_{k=0}^{k=\infty} x^k$

Thus:

$\displaystyle f(x)=-\sum_{k=0}^{k=\infty}\frac23 \left(\frac{-x}{2}\right)^k + \sum_{k=0}^{k=\infty} \frac23 x^k$

$\displaystyle f(x)=\frac23\sum_{k=0}^{k=\infty} \left(1-\left(\frac{-1}{2}\right)^k\right)x^k = \sum_{k=0}^{k=\infty} a_k x^k$

By polynomial equality,

$\displaystyle a_k = \frac23\left(1-\left(\frac{-1}{2}\right)^k\right)$

Now very clearly, $\displaystyle \lim_{k \to \infty} a_k = \frac23$.