13.1. Introduction to Counting Problems

Try these first

1. 1.

   What is the base condition for counting strings of length 1 and 2?

   Hint

   Think of the possible strings.

2. 2.

   Write the recurrence relation for counting bit strings with no consecutive zeros.

   Hint

   Think about where a string can start.

3. 3.

   What is a recurrence equation?

   Hint

   Consider how terms can be calculated based on earlier values.

4. 4.

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

   • True
   • False

   Hint

   Think of how Fibonacci is traditionally defined.

5. 5.

   Given C(1) = 2, C(2) = 3. Using the derived relation, calculate C(8) and provide the reasoning for each step.

   Hint

   Draw out or visualize a tree for each sequence.

6. 6.

   Construct a different counting function that also uses a recurrence relation and compare its properties with our strings without consecutive zeros.

   Hint

   Identify how many strings might be invalid and adjust the relations accordingly.