Payoff: Where do those summation formulas (from chapter 2) come from?
Motivating Example
Let’s look at counting problem involving string in $\underbrace{\{0,1\}^{*\rarr\text{string of arbitrary but finite length}}}_{\text{the alphabet }\Sigma}$
Since strings are defined recursively, it’s not too surprising that we analyze them recursively.
We’ll call a string ‘good’ if it doesn’t have a pair of consecutive 1’s.
How many good strings are these with any particular length(n).
| $n=0$ | $n=1$ | $n=2$ | $n=3$ |
|---|---|---|---|
| $\lambda$ | $1$ | $00$ | $000$ |
| $0$ | $10$ | $001$ | |
| $01$ | $010$ | ||
| $100$ | |||
| $101$ |
Let $a_n$ be the number of good strings with length $n$.
Suppose we have a good string of length $n$:
There are two possibilities, it starts with a $0"$ or it stats with a $1"$ (as long as $n\ge 1$)