Having trouble with these two questions:
Let $S_n$ be the number of bitstrings of length $n$ that contain the substring $0000$. Which of the following is true?
(a) $S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4}$
(b) $S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4} + 2^{n-4}$
(c) $S_n = S_{n-1} + S_{n-2} + S_{n-3}$
(d) $S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4} + 2^{n-4}$
The answer is (b).
I accounted for the bitstrings that begin with:
$1 \rightarrow (S_{n-1})$,
$01 \rightarrow (S_{n-2})$,
$001 \rightarrow (S_{n-3})$,
$0001 \rightarrow (S_{n-4}),$ and,
$0000 \rightarrow (2^{n-4})$
This gives $S_n = S_{n-1} + S_{n-2} + S_{n-3} + S_{n-4} + 2^{n-4}$
Is my logic correct?
How can I do this if I wanted to count bitstrings that do not contain $0000$ and then subtract those from all $2^n$ bitstrings to arrive at the same recurrence relation?
Next question (this one I am not sure how to do):
Let $n \ge 1$ be an integer and let $S_n$ be the number of ways in which $n$ can be written as a sum of 1s and 2s, such that:
- the order in which the 1s and 2s occur in the sum matters, and
- it is not allowed to have two consecutive 2s.
For example, if $n = 7$, then both,
$7 = 1 + 2 + 1 + 2 + 1$ and $7 = 2 + 1 + 1 + 2 + 1$ are allowed, whereas $7 = 1 + 2 + 2 + 1 + 1$ is not allowed.Which of the following is true?
(a) $S_n = S_{n-1} + S_{n-2}$
(b) $S_n = S_{n-1} + S_{n-3}$
(c) $S_n = S_{n-2} + S_{n-3}$
(d) $S_n = S_{n-1} + S_{n-2} + S_{n-3}$
The answer is (b).
Why is this true? I can't wrap my head around it. If all possibile sequences must start with $1$ and $21$ this should be (a) shouldn't it?
For (2), you have 2 cases. a) the "partition" starts with a 1, and b) the partition starts with a 2.
a) This is just 1+(partition of n-1), and since here, the partition of n-1 used uniquely determines your partition of n, there are $S_{n-1}$ of these.
b) Since you start with 2, the next thing to be summed must be a 1. So your partition is 2+1+(partition of n-$\underbrace{3}_{=2+1}$). This is uniquely determined by the partition of n-3 that you use, so there are $S_{n-3}$ of these.
Combining cases a) and b) gives you $S_n=S_{n-1}+S_{n-3}$.