Example: solving a linear recurrence

Suppose we want to find an explicit formula for the sequence $\{a_n\}$ satisfying $a_0=1$, $a_1=4$, and

$$a_{n+2}= \frac{a_{n+1}+a_n}{2} n \ge 0$$ (6)

Since $\{a_n\}$ satisfies a linear recurrence with characteristic polynomial
$x^2-\frac12 x -\frac12 = (x-1)(x+\frac12)$, we know that there exist constants $A$ and $B$ such that

$$a_n = A (1)^n + B \left( -\frac12 \right)^n$$ (7)

for all $n$. The formula (7) is called the general solution to the linear recurrence (6). To find the particular solution with the correct values of $A$ and $B$, we use the known values of $a_0$ and $a_1$:

$$1 = a_0 = A (1)^0 + B \left( -\frac12 \right)^0 = A+B$$

$$4 = a_1 = A (1)^1 + B \left( -\frac12 \right)^1 = A - B/2.$$

Solving this system of equations yields $A=3$ and $B=-2$. Thus the particular solution is

$$a_n = 3 - 2 \left( -\frac12 \right)^n.$$

(As a check, one can try plugging in $n=0$ or $n=1$.)