04-BS-16, December 2016, Q8 | Nivaar Exam Prep

Question 8 (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $S_n$, $V_n$, $W_n$ count $n$-bit binary strings avoiding the sub-pattern "11", conditioned as stated.

Find. (a) $S_1,S_2$ by direct enumeration. (b) $V_n,W_n$ in terms of $S_{n-1},S_{n-2}$. (c) A recurrence for $S_n$. (d) A closed form for $S_n$.

Approach. Every valid string starts with either 0 or 1; if it starts with 1, the next bit is forced to 0 (else "11" appears), splitting the count into the $V_n$/$W_n$ cases, then peel off the fixed prefix to relate to a shorter no-"11" string.

(a) $S_1,S_2$ by enumeration. 1-bit strings: $0,1$ — neither contains "11" — $S_1=2$. 2-bit strings: $00,01,10,11$; only $11$ is excluded — $S_2=3$. $\boxed{S_1=2,\ S_2=3}$
(b) $V_n, W_n$ in terms of $S_{n-1}, S_{n-2}$. A valid $n$-bit string starting with $0$ is exactly "$0$" followed by any valid $(n-1)$-bit no-"11" string (the leading 0 can never create an "11" with what follows), so $V_n=S_{n-1}$. A valid string starting with $10$ is "$10$" followed by any valid $(n-2)$-bit no-"11" string (again the prefix cannot create "11" with the tail), so $W_n=S_{n-2}$: $$\boxed{V_n = S_{n-1}, \qquad W_n = S_{n-2}}$$
(c) $S_n$ in terms of $S_{n-1}, S_{n-2}$. Every valid $n$-bit string starts with either $0$ (case $V_n$) or with $1$ — and if it starts with $1$, the next bit must be $0$ (a leading "11" is forbidden outright), so every "starts with 1" string is captured by $W_n$. These two cases are exhaustive and disjoint, so $S_n=V_n+W_n$: $$\boxed{S_n = S_{n-1}+S_{n-2}\quad (n\ge 3)}$$
(d) Closed form for $S_n$. With $S_1=2,S_2=3$ and $S_n=S_{n-1}+S_{n-2}$, this is the Fibonacci recurrence shifted by two indices: writing $F_1=F_2=1,F_3=2,F_4=3,\ldots$ for the standard Fibonacci sequence, $S_n=F_{n+2}$ (check: $S_1=2=F_3$, $S_2=3=F_4$, and both satisfy the same two-term recurrence with matching seeds). Using Binet's formula for $F_k=\dfrac{\varphi^k-\psi^k}{\sqrt5}$ with $\varphi=\dfrac{1+\sqrt5}{2}$, $\psi=\dfrac{1-\sqrt5}{2}$: $$\boxed{S_n = \dfrac{\varphi^{\,n+2}-\psi^{\,n+2}}{\sqrt5},\qquad \varphi=\dfrac{1+\sqrt5}{2},\ \ \psi=\dfrac{1-\sqrt5}{2}}$$ (equivalently $S_n=F_{n+2}$, the $(n+2)$-th Fibonacci number).

Question 8 – results
Part	Result
a	$S_1=2,\ S_2=3$
b	$V_n=S_{n-1}$, $W_n=S_{n-2}$
c	$S_n=S_{n-1}+S_{n-2}$
d	$S_n=\dfrac{\varphi^{n+2}-\psi^{n+2}}{\sqrt5}=F_{n+2}$

Topic: Recurrence relations derived from a combinatorial case split, and their closed form (Binet's formula).

Key relations: conditioning on the first one or two bits of a binary string; Fibonacci recurrence $F_k=F_{k-1}+F_{k-2}$; Binet's formula $F_k=(\varphi^k-\psi^k)/\sqrt5$.

Why this works: Splitting on the first bit (and, when the first bit is 1, the forced second bit) is the standard technique for turning a "no 11" counting problem into a linear recurrence, because it reduces every $n$-bit case to strictly shorter valid strings with no double-counting. The recurrence's shape is literally Fibonacci's, just re-indexed by the seed values $S_1,S_2$.

Common pitfall: Forgetting that a string starting with "1" is not the same as $V_n$ — it must be split further into "10" (valid continuation) since "11" is immediately forbidden, which is exactly why $W_n$ (not a general "starts with 1" count) appears in the recurrence.

Source: Rosen, Discrete Mathematics and Its Applications, 7th ed., Ch. 8 (Advanced Counting Techniques: Recurrence Relations).

Question 8 of 12

Question 8 (10 marks)