13. Counting Using Recurrence Equations

Try these first

1. 1.

   Define a recurrence equation.

   Hint

   Think about how you can express one term through others.

2. 2.

   What is A(1) for bit strings not containing consecutive zeros?

   Hint

   Consider the possible 1-bit strings.

3. 3.

   What is a recurrence equation?

   • A function of previous outputs
   • A linear equation
   • An iterative formula

   Hint

   Think of its role in sequences.

4. 4.

   True or False: The Fibonacci sequence is an example of a recurrence relation.

   • True
   • False

   Hint

   Consider how Fibonacci numbers relate.

5. 5.

   Consider an application where you are counting paths in a grid that do not retrace steps. How would you set up a recurrence relation?

   Hint

   Consider possible moves at each grid point.

6. 6.

   Propose a unique challenge problem involving recurrence relations that is applicable in computer algorithms.

   Hint

   Explore how to build trees based on left and right nodes.