14.7. Proof of Theorem - Part 1

Try these first

1. 1.

   Write the general form of a linear homogeneous recurrence relation of degree 2.

   Hint

   Think about how each term relates to the previous ones.

2. 2.

   What is meant by characteristic roots?

   Hint

   Reflect on where they come from.

3. 3.

   What form does a linear homogeneous recurrence equation typically take?

   • T(n) = a + b
   • T(n) = a*T(n-1) + b*T(n-2)
   • T(n) = a*T(n-2) + b*T(n-3)

   Hint

   Look for how previous terms in the sequence appear.

4. 4.

   True or False: The characteristic roots of a recurrence equation can be the same.

   • True
   • False

   Hint

   Consider the nature of quadratic equations.

5. 5.

   For T(n) = 4T(n-1) - 4T(n-2), derive the characteristic equation and roots. Then find a general solution.

   Hint

   Follow the steps to construct your polynomial from the recurrence relation.

6. 6.

   Given the initial conditions T(0)=2, T(1)=3, find specific constants A and B for T(n) = A * 3^n + B * 1^n.

   Hint

   Set up simultaneous equations based on initial terms.