Solving Recurrence Relations

Find the next two terms in $(a_n)_{n\ge 0}$ beginning $3, 5, 11, 21, 43, 85\ldots$. Then give a recursive definition for the sequence. Finally, use the characteristic root technique to find a closed formula for the sequence.

Show that $4^n$ is a solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$.

Let $a_n$ be the number of $1 \times n$ tile designs you can make using $1 \times 1$ squares available in 4 colors and $1 \times 2$ dominoes available in 5 colors.

1. First, find a recurrence relation to describe the problem. Explain why the recurrence relation is correct (in the context of the problem).

2. Write out the first 6 terms of the sequence $a_1, a_2, \ldots$.

3. Solve the recurrence relation. That is, find a closed formula for $a_n$.

Solve the recurrence relation $a_n = 2a_{n-1} - a_{n-2}$.

1. What is the solution if the initial terms are $a_0 = 1$ and $a_1 = 2$?

2. What do the initial terms need to be in order for $a_9 = 30$?

3. For which $x$ are there initial terms which make $a_9 = x$?