Solving Recurrence Relations

Find a recurrence relation for the number of ways to give someone $n$ dollars if you have 1 dollar coins, 2 dollar coins, 2 dollar bills, and 4 dollar bills where the order in which the coins and bills are paid matters.

Solve the recurrence relation $a_n = a_{n-1} + 2^n$ with $a_0 = 5$.

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

Find the solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_0 = 2$ and $a_1 = 3$.

Find the solution to the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_0 = 5$ and $a_1 = 8$ using the characteristic root method..

While walking up stairs you notice that you have a habit of using 3 ways of taking one step and 4 ways of taking two steps at a time. Find a recurrence relation for the number of ways to go up $n$ steps. Solve the recurrence relation given the initial conditions of $a_0 = 1$ and $a_1 = 3$ using the characteristic root method.

Solve the recurrence $a_n = 3a_{n-1} + 40a_{n-2}$ where $a_0 = 5$ and $a_1 = 14$ using the characteristic root method.

Solve the recurrence $a_n = 4a_{n-1} + 21a_{n-2}$ where $a_0 = 18$ and $a_1 = 366$ using the characteristic root method.