13.3. Setting up the Recurrence Equation

Try these first

1. 1.

   Define a recurrence equation.

   Hint

   Think about how one term leads to another.

2. 2.

   What is A(1) for strings of length 1 without consecutive zeros?

   Hint

   Consider what strings are valid.

3. 3.

   What is a recurrence relation?

   • A method for counting
   • An equation using previous terms
   • A counting pattern

   Hint

   Think of sequences you know.

4. 4.

   True or False: Initial conditions are irrelevant in recurrence equations.

   • True
   • False

   Hint

   Consider the beginning of a countdown.

5. 5.

   Using A(n) = A(n-1) + A(n-2), find A(6), given A(5) and A(4).

   Hint

   You may count on A(5) being a certain value that you previously obtained.

6. 6.

   Create your own recurrence relation and solve for the first five terms.

   Hint

   Start small and build up just like adding events on a timeline.