# Thread: recursive sequence

1. ## recursive sequence

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

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

Is this the right way to go about proving it?

2. Originally Posted by particlejohn
So $a_n = \frac{1}{2}\left(a_{n-1}+a_{n-2} \right)$. This means that for all $\varepsilon > 0$, there exists $N \in \mathbb{N}$, such that whenever $n \geq N$, then $|a_{n}-L| < \varepsilon$ and $|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 $a_0 = 0$, $a_1 = 1$, and $a_{n+1} = \frac{1}{2}\left(a_{n}+a_{n-1}\right)$ for $n \geq 2$. Prove $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 $f(x) = \sum_{k=0}^{k=\infty} a_k x^k$

This means $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, $\forall k \ge 2, a_k - \frac{a_{k-1} + a_{k-2}}2 = 0$. And $a_1 = 1, a_0 = 0$.

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

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

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

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

Thus:

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

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

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

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