Exercise 3.3.3, subsequences

[blueglyph]

In a string of length n, how many of the following are there?

1. Prefixes.
2. Suffixes.
3. Proper prefixes.
4. ! Substrings.
5. ! Subsequences.

The current solution for the last part of the question is Σ(i=0,n) C(n, i), but it can be simplified as 2^n since each position can be either deleted or not.