14. Solving Linear Homogenous Recurrence Equations – Part I

Try these first

1. 1.

   State the general form of a linear homogeneous recurrence equation.

   Hint

   Consider the structure of sequences based on previous terms.

2. 2.

   What does the term 'characteristic roots' refer to?

   Hint

   Think of how these roots help define the terms of the sequence.

3. 3.

   What is the general form of a linear homogeneous recurrence relation?

   • a_n = c_1 a_{n-1} + c_2 a_{n-2}
   • a_n = c_1 a_{n-1} + c_2 a_{n-2} + c_3
   • a_n = c_1 + c_2 a_{n-2}

   Hint

   Focus on the dependency of terms on previous terms.

4. 4.

   True or False: The characteristic equation for degree two always has two distinct roots.

   • True
   • False

   Hint

   Consider the properties of quadratic equations.

5. 5.

   Consider a recurrence relation $a_n = 2a_{n-1} + 3a_{n-2}$ with a(0) = 4, a(1) = 5. Determine a closed form for a_n.

   Hint

   Focus on solving the characteristic equation and then using initial conditions.

6. 6.

   Prove that the sequence defined by $F_n = F_{n-1} + F_{n-2}$ indeed generates the Fibonacci series.

   Hint

   Base cases are key, then follow with cases n >= 2.