Given initial conditions and a recurrence relation, what is closed form in terms of n?

Question

We are given that $a_0$ = 1000, and $a_1$ = 3000, and that $\forall n \geq 2$, $a_n = \frac{a_{n-1} + a_{n-2}}{2}$. What is the value when $n$?

I've determined that, in the long run, it converges to ~2290.

So, there must be some equation that relates the values oto this convergent point as $n$ varies.

Any thoughts?

Answer 1

We have $$2a_n-a_{n-1}-a_{n-2}=0$$

Then use this, to find $$a_n=A+B\left(-\frac12\right)^n$$ where $A,B$ are arbitrary constants

Use the values of $a_0,a_1$ to find $A,B$

Answer 2

$$\begin{align} a_n &= \frac 12 \,a_{n-1} + \frac 12\, a_{n - 2}\\ a_{n-1} &= 1\, a_{n-1} + 0\, a_{n-2} \end{align}$$

$$\begin{bmatrix}a_n \\ a_{n - 1}\end{bmatrix} = \begin{bmatrix} \frac 12 & \frac 12 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a_{n-1} \\ a_{n - 2} \end{bmatrix}$$ $$\begin{bmatrix}a_{n + 1} \\ a_{n}\end{bmatrix} = \begin{bmatrix} \frac 12 & \frac 12 \\ 1 & 0 \end{bmatrix}^n\begin{bmatrix} a_{1} \\ a_{0} \end{bmatrix}$$

Now notice that your matrix $M = \begin{bmatrix} \frac 12 & \frac 12 \\ 1 & 0 \end{bmatrix}$ is a stochastic matrix. That is a very good thing. You could close this formula by finding eigenvalues and eigenvectors; but to find the steady state, you can actually skip that step with a stochastic matrix.

To find the steady state of your matrix $S = M^\infty$, which is where successive applications of $M$ don't change the state, which is $SM = S$, it comes down to solving $S(M-I) = 0$ which is $S = \text{nullspace}(M - I)$. Doing so you find:

$$\begin{bmatrix} \frac 12 & \frac 12 \\ 1 & 0 \end{bmatrix}^\infty = \begin{bmatrix} \frac 23 & \frac 13 \\ \frac 23 & \frac 13 \end{bmatrix}$$

So altogether:

$$\begin{bmatrix}a_{\infty + 1} \\ a_{\infty}\end{bmatrix} = \begin{bmatrix} \frac 12 & \frac 12 \\ 1 & 0 \end{bmatrix}^\infty\begin{bmatrix} a_{1} \\ a_{0} \end{bmatrix} = \begin{bmatrix} \frac 23 & \frac 13 \\ \frac 23 & \frac 13 \end{bmatrix}\begin{bmatrix}3000 \\ 1000 \end{bmatrix} = \begin{bmatrix}\frac{7000}{3} \\ \frac{7000}{3}\end{bmatrix}$$

Answer 3

If you use generating functions, you'll see directly what is going on. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence as: $$ 2 a_{n + 2} = a_{n + 1} + a_n $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums: $$ 2 \frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(z) - a_0}{z} + A(z) $$ Solving for $A(z)$, written as partial fractions: $$ A(z) = \frac{2}{3} (a_0 + a_1) \frac{1}{1 - z} - \frac{2}{3} (a_1 - a_0) \frac{1}{1 + z /2)} $$ This can expanded as geometric series, to give: $$ a_n = \frac{2}{3} (a_0 + a_1) - \frac{2}{3} (a_1 - a_0) \left( - \frac{1}{2} \right)^n $$