16.3.2. Categories of Strings

Try these first

1. 1.

   Define a strictly increasing sequence.

   Hint

   Think about the differences in numbers in a sequence.

2. 2.

   What does a recurrence relation do?

   Hint

   Consider how one term can influence the next.

3. 3.

   What denotes a strictly increasing sequence?

   • Terms are all equal.
   • Each term is greater than the prior one.
   • Terms can repeat.

   Hint

   Visualize the terms on a number line.

4. 4.

   Is the recurrence relation for F(n) dependent on only the last term?

   • True
   • False

   Hint

   Remember how these sequences are constructed.

5. 5.

   Prove that for n greater than 2, F(n) can be expressed as a function of F(n-1) and F(n-2).

   Hint

   Start with smaller values to recognize the pattern.

6. 6.

   Determine the total number of strictly increasing sequences for n=5 using the recurrence relation.

   Hint

   Use previously known values to build up to F(5).