2.3. Advanced Counting Mechanisms

Try these first

1. 1.

   Define a recurrence relation for the sequence where each term is the sum of the previous two.

   Hint

   Think of a sequence like Fibonacci.

2. 2.

   What is the base case for a recurrence relation?

   Hint

   Look for the starting value of the sequence.

3. 3.

   What is a recurrence relation?

   • A sequence defined with initial values
   • An equation defining a sequence recursively
   • A method for linear equations

   Hint

   Recurrence often involves sequences, think of Fibonacci.

4. 4.

   True or False: Recurrence relations are not used in programming.

   • True
   • False

   Hint

   Think of recursion and dynamic programming.

5. 5.

   Find the closed-form solution for the recurrence relation a_n = 3a_{n-1} - 2, a_1 = 2.

   Hint

   Consider iterating the first few terms.

6. 6.

   Discuss how recurrence relations could optimize a recursive function for calculating factorial.

   Hint

   Look at storing values of the factorial calculation.