next up previous
Next: Example: the formula for Up: Linear recursive sequences Previous: The main theorem

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

$\displaystyle a_{n+2}= \frac{a_{n+1}+a_n}{2}$    for $ 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

$\displaystyle 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$:

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

$\displaystyle 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

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

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



Zvezdelina Stankova-Frenkel 2000-09-20