\documentclass{article}
\usepackage{amsmath}
\usepackage{xcolor}
\usepackage{paralist}
\usepackage{graphicx}
\plparsep 2ex
\usepackage{amsfonts}
\usepackage{url}
\usepackage{listings}
\usepackage{minted}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\setlength{\parskip}{1em}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\DeclareMathOperator{\E}{\mathbf{E}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\title{Assignment 2 Solutions}
\author{COMP2804 Winter 2020}
\begin{document}
\maketitle
\newcommand{\Z}{\mathbb{Z}}
\section{ID}
Name: Lenny Learning Combinatorics \\
Student ID: 100000000
\section{Arrangements of PUNKEYDOODLES}
\begin{compactenum}[Q\thesection.1:]
\item How may distinct ways are there to rearrange the letters in PUNKEYDOODLES (the name of a town in Ontario)?
We did an example like this in class, but with the string SUCCESS. Any rearrangement of PUNKEYDOODLES has length 13. We can make any arrangement by placing the letters using the following procedure:
\begin{compactenum}[Step 1.]
\item Choose the location of the letter P. There are $\binom{13}{1}=13$ ways to do this.
\item Choose a not-already-chosen location for the letter U. There are $\binom{12}{1}=12$ ways to do this.
\item Choose a not-already-chosen location for the letter N. There are $\binom{11}{1}=11$ ways to do this.
\item Choose a not-already-chosen location for the letter K. There are $\binom{10}{1}=10$ ways to do this.
\item Choose two not-already-chosen locations for the letter E. There are $\binom{9}{2}$ ways to do this.
\item Choose a not-already-chosen location for the letter Y. There are $\binom{7}{1}=7$ ways to do this.
\item Choose two not-already-chosen locations for the letter D. There are $\binom{6}{2}$ ways to do this.
\item Choose two not-already-chosen locations for the letter O. There are $\binom{4}{2}$ ways to do this.
\item Choose a not-already-chosen location for the letter L. There are $\binom{2}{1}=2$ ways to do this.
\item Place the letter S in the only remaining location. There is only $1$ way to do this.
\end{compactenum}
Therefore, by the ProductRule, the number of rearrangements of PUNKEYDOODLES is
\[ 13\cdot12\cdot 11\cdot 10\cdot\binom{9}{2}\cdot 7\cdot \binom{6}{2}\cdot \binom{4}{2}\cdot 2\cdot 1 = \frac{13!}{2!\cdot2!\cdot2!} = 778\,377\,600 \]
\end{compactenum}
\section{Modern Coupling}
\begin{compactenum}[Q\thesection.1:]
\item Suppose we a group of $n$ women and $n$ men, all heterosexual and all strictly monogamous. How many ways are there to make $n$ couples out of these $2n$ people?
If $M$ is the group of $n$ men and $W$ is the group of $n$ women, then the question is asking how many one-to-one functions there are from $M$ to $W$. (Since $M$ and $W$ are the same size any one-to-one function from $M$ to $W$ is a bijection.) The number of one-to-one functions between two sets each of size $n$ is $n!$. There are lots of ways to see this. For example, apply Theorem~3.1.3 in the textbook with $n=m$.
\item Suppose we have $2n$ people, each of whom is bisexual but strictly monogamous. How many ways are there to make $n$ couples out of these $2n$ people?
The cleanest way to solve this is with a Combinatorial Proof (i.e., counting two different ways). Let $P=\{p_1,\ldots,p_{2n}\}$ be the set of $2n$ people. Let $S$ be the set of couplings we are trying to count, i.e., the set of partitions of $P$ into $n$ sets each of size $2$.
\[ S= \left\{
\left\{
\{p_{\pi_i},p_{\pi_2}\},
\{p_{\pi_3},p_{\pi_4}\},
\ldots,
\{p_{\pi_{2n-1}},p_{\pi_{2n}}\}
\right\}: \text{$\pi_1,\ldots,\pi_{2n}$ is a permutation of $\{1,\ldots,2n\}$}
\right\}
\]
(Note that $|S|\neq (2n)!$ since many permutations of $\{1,\ldots,2n\}$ give the same set of couples.)
Let $A$ be the set of \emph{couplings into ordered pairs}, i.e., the set of partitions of $\{p_1,\ldots,p_{2n}\}$ into $n$ \emph{ordered pairs}.
\[ A= \left\{
\{
(p_{\pi_i},p_{\pi_2}),
(p_{\pi_3},p_{\pi_4}),
\ldots,
(p_{\pi_{2n-1}},p_{\pi_{2n}})
\}: \text{$\pi_1,\ldots,\pi_{2n}$ is a permutation of $\{1,\ldots,2n\}$} \right\}
\]
(Note that $|A|\neq (2n)!$ since many permutations of $\{1,\ldots,2n\}$ give the same set of ordered couples.)
Some notes: For a coupling $C\in S$, each of the two members $x,y$ of a couple $\{x,y\}\in C$ is treated equally, since the couple is a set and therefore unordered, so $\{x,y\}=\{y,x\}$. For a coupling $C'\in A$, the two members of a couple $(x,y)\in A$ are not treated equally: $x$ comes before $y$.
We count $|A|$ in two different ways:
\begin{compactenum}[{Way} 1.]
\item We use the Product Rule with a 2-step procedure:
\begin{compactenum}[Step 1.]
\item Choose a pairing $P$ from $S$. There are $|S|$ ways to do this.
\item For each couple $\{x,y\}\in P$, choose an ordering $(x,y)$ or $(y,x)$ for that couple. There are 2 ways to do this for each couple and $n$ couples to do this for, so there are $2^n$ ways to complete this step.
\end{compactenum}
Therefore, $|A|=|S|\cdot 2^n$
\item We use the Produce Rule with a different 2-step procedure:
\begin{compactenum}[Step 1.]
\item Choose a subset $W\subset P$ of $n$ of the $2n$ people who will become first half of each pair. There are $\binom{2n}{n}$ ways to do this.
\item Call $W$ the set of \emph{women} and call $M=P\setminus W$ the set of \emph{men}. Now choose a bijection $f:W\to M$ from $W$ to $M$ and make the coupling
\[ \{(x,f(x)) : x\in W\} \enspace . \]
The number of ways to do this is equal to the number of bijections from $W$ to $M$, which is $n!$.
\end{compactenum}
Therefore $|A|=\binom{2n}{n}\cdot n!$.
\end{compactenum}
Now we have two different expressions for $|A|$ and putting them together we get
\[ |S|\cdot 2^n = |A| = \binom{2n}{n}\cdot n! \enspace . \]
Dividing the left- and right-hand sides of this equation by $2^n$ gives the answer:
\[ |S| = \frac{\binom{2n}{n}\cdot n!}{2^n} \enspace . \]
\end{compactenum}
\section{Pigeonholing}
Use the pigeonhole principle to solve each of the following problems:
\begin{compactenum}[Q\thesection.1:]
\item In an anonymous survey of a group of 20 men and 20 women, the men reported a total of 81 sexual encounters with women in the group, and all women reported having at most 4 sexual encounters with men in the group. Is everyone telling the truth?
No. Someone is lying. If the men were involved with 81 encouters with the women, then the women were involved with 81 encounters with the men. By the Pigeonhole Principle (with 81 pigeons and 20 pigeon holes) at least one woman would have been involved in at least $\lceil81/20\rceil=\lceil 4.05\rceil=5$ encounters. But none of the women admits to having been involved in more than 4 encouters.
\item A group of $n$ agents all start at the same location and each one takes a \emph{$\le m$-walk} on the line, where a $\le m$-walk is a sequence of *at most* $m$ steps and each step moves the agent one unit to the left or one unit to the right. (Different agents might take different walks.) Prove that, if $n> 2m+1$, then some pair of agents finishes their walk at the same location.
We can model any agent's position as an integer that starts 0 and, with each step either increases or decreases by 1. The agent walks for at most $m$ steps, so their location at the end of the walk is in the set
\[ \{ -m, -(m-1), \ldots,-2, -1, 0, 1, 2,\ldots,m-1, m\} \]
This set has size $2m+1$. If $n>2m+1$ then, by the Pigeonhole Principle (with $n$ pigeons and $2m+1$ holes) there must be two agents who finish their walk at the same location.
\item A group of $n$ agents all start at the same location and each one takes an \emph{$m$-walk} on the line, where a $m$-walk is a sequence of \emph{exactly} $m$ steps and each step moves the agent one unit to the left or one unit to the right. (Different agents might take different walks.) Prove that, if $n> m+1$, then some pair of agents finishes their walk at the same location.
Again, we can model any agent's position as an integer that starts 0 and, with each step either increases or decreases by 1. The agent walks for at most $m$ steps, so their location at the end of the walk is in the set
\[ S = \{ -m, -(m-1), \ldots,-2, -1, 0, 1, 2,\ldots,m-1, m\} \enspace . \]
There are two cases to consider:
\begin{compactenum}
\item If $m$ is even, then each agent finishes at an even integer in $S$, i.e., in $\{0,2,4,6,\ldots,m\}$ or in $\{-2,-4,-6,\ldots,-m\}$. The first set has size $m/2+1$ and the second set has size $m/2$, so there are only $m/2+1+m/2=m+1$ possible locations where the agent could have finished their walk.
\item If $m$ is odd, then each agent finishes at an odd integer in $S$, i.e., in $\{1,3,5,\ldots,m\}$ or in $\{-1,-3,-5,\ldots,-m\}$. Each of these two sets has size $\lceil m/2\rceil = m/2+1/2$, so there are only $2(m/2+1/2)=m+1$ possible locations where the agent could have finished their walk.
\end{compactenum}
In either case if $n>m+1$, then the Pigeonhole Principle implies that some pair of agents finished their walk at the same location.
\item Let $V=\{v_1,\ldots,v_k\}$ be any set of vectors in $\R^2$. Suppose $n$ agents each start at $(0,0)$ and each takes a \emph{$mV$-walk} where a $mV$-walk consists of a sequence of exactly $m$ steps and each step moves the agent along a vector in $V$. Prove that, if $n>\binom{m+k-1}{k-1}$, then some pair of agents finishes their walk at the same location.
Consider a particular agent whose walk takes them along $v_{i_1}$ then $v_{i_2}$, then $v_{i_2}$ and so on until the last step along $v_{i_m}$. This agent finishes at location $(0,0)+v_{i_1}+\cdots+v_{i_m}$. Vector addition is commutative, so the order in which the agent walks along the vectors $v_{i_1},\ldots,v_{i_m}$ doesn't affect the agent's final location.
For each agent $a_i$, $i\in\{1,\ldots,n\}$, let $t_{i,j}$ denote the number of times agent $a_i$'s walk travels along vector $v_j$. So, as discussed above, agent $a_i$'s final location is
\[ t_{i,1}\cdot v_1 + t_{i,2}\cdot v_2 + \cdots +t_{i,k}\cdot v_k \]
Now notice that $t_{i,1}+\cdots+t_{i,k}=m$ and each $t_{i,j}\ge 0$ is an integer. In class we learned how to count the number of integer solutions to these types of linear equations. In particular, applying Theorem~3.9.1 from the textbook, we see that the number of solutions to $t_{i,1}+\cdots+t_{i,k}=m$ where each $t_{i,j}\ge 0$ is an integer is
\[ \binom{m+k-1}{k-1} \enspace . \]
Therefore, if $n>\binom{m+k-1}{k-1}$, then the Pigeonhole Principle implies that there is some pair of agets $a_i$ and $a_\ell$ such that $(t_{i,1},\ldots,t_{i,k})=(t_{\ell,1},\ldots,t_{\ell,k})$ and the two agents $a_i$ and $a_\ell$ finishes their walks at the same location.
\item Let $S$ be a $k$-element subset of $\{1,\ldots,n\}$. Prove that, if $k> \lceil n/2\rceil$, then there exists $x,y\in S$ such that $x-y=1$.
Consider the function $f:S\to\{1,\ldots,\lceil n/2\rceil\}$ defined by $f(x)=\lceil x/2\rceil$. The range of $f$ has size $\lceil n/2\rceil$ and has domain $S$ of size $k> \lceil n/2\rceil$ so the Pigeonhole Principle implies that $S$ contains distinct values $x,y$ such that $f(x)=f(y)$. This means $\lceil x/2\rceil = \lceil y/2\rceil$, so $|x-y|<2$. Since $x$ and $y$ are both integers, this means $|x-y|=1$.
\item Let $S$ be a $k$-element subset of $\{1,\ldots,n\}$. Prove that, if $\binom{k}{2}> n-1$, then there exists $a,b,x,y\in S$ such that $a\neq b$, $\{a,b\}\neq\{x,y\}$ and $b-a=y-x$. (Note that it may be the case that $b=x$ or $a=y$.)
Let $P$ be the set of 2-element subsets of $S$, so $|P|=\binom{k}{2}$. Define the function $f:P\to\{1,\ldots,n-1\}$ given by $f(\{x,y\})=|x-y|$. If $\binom{k}{2}> n-1$, then the Pigeonhole Principle implies that there are two distinct pairs $\{a,b\},\{x,y\}\in P$ such that $f(\{a,b\})=f(\{x,y\})$. Since order doesn't matter, we can assume without loss of generality that $a** n-1$, then there exists a $4$-element subset $\{a,b,x,y\}\subset S$ such that $a-b=x-y$. (Unlike the previous question, $a,b,x,y$ must be 4 \emph{distinct} elements.)
List the elements of $S$ in order as $x_1n-1$ then, by Pigeonhole Principle, there are two distinct pairs $(x_i,x_j), (x_k,x_\ell)\in P$ such that
\begin{equation}
x_j-x_i=x_\ell-x_k > 0 \enspace . \label{blech}
\end{equation}
All that's left is to argue that $x_i,x_j,x_k,x_\ell$ are four distinct elements. We know $x_i\not\in\{x_j,x_\ell\}$ and $x_k\not\in\{x_j,x_\ell\}$. Furthermore, because of \eqref{blech}, $x_i= x_k$ if and only if $x_j=x_\ell$, but we know $(x_i,x_j)\neq (x_k,x_\ell)$ and therefore $x_i\neq x_k$ and $x_j\neq x_\ell$.
\end{compactenum}
\section{Recurrences}
\begin{compactenum}[Q\thesection.1:]
\item Let $a,b\ge 0$ be two real numbers and consider the function $f:\N\to\R$ given by the recurrence
\[
f(n) = \begin{cases} a & \text{if $n=0$} \\
f(n-1) + b & \text{if $n\ge 1$}
\end{cases}
\]
Write a closed form formula for $f(n)$ and prove that your formula is correct.
The formula, valid for all integers $n\ge 0$, is $f(n) = a + bn$. The proof is by induction on $n$. The base case $n=0$ is true since $a+b0=a=f(0)$. For the inductive step we assume $f(k)=a+bk$ for all $k\in\{0,\ldots,n-1\}$. With this assumption, we get
\[ f(n) = f(n-1)+b = a+ b(n-1) + b = a+bn \enspace , \]
for all $n\ge 1$.
\item Consider the function $f:\N\to\N$ defined by the recurrence
\[ f(n) =
\begin{cases}
\frac{1}{2} & \text{if $n=0$} \\
\frac{1}{2}\cdot n\cdot f(n-1) & \text{if $n\ge 1$.}
\end{cases}
\]
Write a closed form formula for $f(n)$ and prove that your formula is correct.
The formula, valid for all integers $n\ge 0$, is $f(n)=n!/2^{n+1}$. The proof is by induction on $n$. The base case $n=0$ is true because $0!/2^{0+1}=1/2=f(0)$. For the inductive step we assume $f(k)=k!/2^{k+1}$ for all $k\in\{0,\ldots,n-1\}$. With this assumption, we get
\[ f(n) = \frac{1}{2}\cdot n\cdot f(n-1) = \frac{1}{2}\cdot n\cdot (n-1)!/2^{n} = n!/2^{n+1} \]
\item Consider the function $f:\N^+\to\N$ defined by:
\[ f(n) =
\begin{cases}
1 & \text{if $n\in\{1,2,3\}$} \\
4\cdot f(n-3) & \text{if $n> 3$.}
\end{cases}
\]
Write a closed form formula for $f(n)$ and prove that your formula is correct.
To get a feel for this question, we can list $f(n)$ for the first few values of $n$: $f(0)=f(1)=f(2)=f(3)=1$, $f(4)=f(5)=f(6)=4$, $f(7)=f(8)=f(9)=4^2$, $f(10)=f(11)=f(12)=4^3$. Now we see a pattern and guess that, in general,
\[ f(n) = 4^{\lfloor(n-1)/3\rfloor} \]
for all $n\ge 1$.
We prove that this formula is correct by induction on $n$. The base cases $n=1,2,3$ are true because for these values of $n$, $\lfloor(n-1)/3\rfloor=0$, so $4^{\lfloor(n-1)/3\rfloor}=4^0=1=f(1)=f(2)=f(3)$.
For the inductive step we assume $f(k)=4^{\lfloor(k-1)/3\rfloor}$ for all $k\in\{0,\ldots,n-1\}$. With this assumption, we get
\[ f(n) = 4\cdot f(n-3) = 4\cdot 4^{\lfloor(n-3-1)/3\rfloor}
= 4\cdot 4^{\lfloor(n-1)/3\rfloor-1} = 4^{\lfloor(n-1)/3\rfloor} \]
\item Consider the set $A_n$ of strings over the 4-character alphabet $\{a,b,c,d\}$ whose length is $n$ and for which $cc$ does not appear as a consecutive substring.
Write a recurrence for $|A_n|$. Then, using induction, show that this recurrence solves to
\begin{equation}
|A_n| =
(1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^n +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^n \enspace , \label{tedious}
\end{equation}
where $\alpha=(3+ \sqrt{21})/2$ and $\beta=(3-\sqrt{21})/2$ are the solutions to the equation $x^2-3x-3=0$.
A string in $A_n$ has one of the following forms:
\begin{compactenum}
\item An $a$, $b$, or $d$ followed by a string in $A_{n-1}$. There are $3\cdot |A_{n-1}|$ such strings.
\item A $ca$, $cb$, or $cd$ followed by a string in $A_{n-2}$. There are $3\cdot |A_{n-2}|$ such strings.
\end{compactenum}
The question already tells us that $|A_0|=1$ and $|A_1|=4$, so we get the following recurrence for $|A_n|$:
\[ |A_n|=\begin{cases}
1 & \text{if $n=0$} \\
4 & \text{if $n=1$} \\
3\cdot|A_{n-1}|+3\cdot|A_{n-2}| & \text{if $n\ge 2$.}
\end{cases}
\]
The proof by induction that this recurrence satisfies \eqref{tedious} is straightforward and follows along the lines of the proof that $f_n=(\phi^n-\psi^n)/\sqrt{5}$. We start with the two base cases and go very slowly:
\begin{compactenum}[$n=1$:]\setcounter{enumii}{-1}
\item
\begin{align*}
& (1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^0 +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^0 \\
& = 1/2 + 5\cdot \sqrt{21}/42 + 1/2-5\cdot\sqrt{21}/42 \\
& = 1 = |A_0|
\end{align*}
\item \begin{align*}
& (1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^1 +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^1 \\
& = (\alpha+\beta)/2 + (5\cdot \sqrt{21}/42)\cdot\alpha
- (5\cdot\sqrt{21}/42)\cdot\beta \\
& = ((3+\sqrt{21})/2+(3-\sqrt{21})/2)/2 + (5\cdot \sqrt{21}/42)\cdot\alpha
- (5\cdot\sqrt{21}/42)\cdot\beta \\
& = 3/2 + (5\cdot \sqrt{21}/42)\cdot\alpha
- (5\cdot\sqrt{21}/42)\cdot\beta \\
& = 3/2 + (5\cdot \sqrt{21}/42)\cdot(3+\sqrt{21})/2
- (5\cdot\sqrt{21}/42)\cdot(3-\sqrt{21})/2 \\
& = 3/2 + (5\cdot \sqrt{21}/42)\cdot(\sqrt{21})/2
- (5\cdot\sqrt{21}/42)\cdot(-\sqrt{21})/2 \\
& = 3/2 + (5\cdot 21/84)
+ (5\cdot 21/84) \\
& = 3/2 + (105/84)
+ (105/84) = 3/2+ 210/84 = 3/2 + 5/2 = 4 = |A_1|
\end{align*}
\end{compactenum}
Now we make our \emph{inductive hypothesis (IH)}: we assume
\[ |A_k|=(1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^k +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^k \]
for each $k\in\{0,\ldots,n-1\}$. We finish up by considering any integer $n\ge 2$:
\begin{align*}
|A_n| & = 3\cdot|A_{n-1}| + 3\cdot|A_{n-2}|
& \text{(this we determined above)} \\
& = 3\cdot\left((1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^{n-1} +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^{n-1} \right) \\ &{}\qquad
+ 3\cdot\left((1/2 + 5\cdot \sqrt{21}/42)\cdot\alpha^{n-2} +(1/2-5\cdot\sqrt{21}/42)\cdot \beta^{n-2} \right)
& \text{(IH with $k=n-1$ and $k=n-2$)}\\
& = 3\cdot\left((1/2 + 5\cdot \sqrt{21}/42)\right)\cdot\left(\alpha^{n-1}+\alpha^{n-2}\right) \\
&{}\qquad
+3\cdot\left(1/2-5\cdot\sqrt{21}/42)\right)\cdot \left(\beta^{n-1}+\beta^{n-2}\right)
& \text{(regroup terms)}\\
& = 3\cdot\left((1/2 + 5\cdot \sqrt{21}/42)\right)\cdot\left(\alpha^{n-2}(\alpha+1)\right) \\
&{}\qquad
+3\cdot\left(1/2-5\cdot\sqrt{21}/42)\right)\cdot \left(\beta^{n-2}(\beta+1)\right)
& \text{(factor out common multiples)} \\
& = \left((1/2 + 5\cdot \sqrt{21}/42)\right)\cdot\left(\alpha^{n-2}(3\alpha+3)\right) \\
&{}\qquad
+\left(1/2-5\cdot\sqrt{21}/42)\right)\cdot \left(\beta^{n-2}(3\beta+3)\right)
& \text{(distribute common multiple 3)} \\
& = \left((1/2 + 5\cdot \sqrt{21}/42)\right)\cdot\left(\alpha^{n-2}\alpha^2\right) \\
&{}\qquad
+\left(1/2-5\cdot\sqrt{21}/42)\right)\cdot \left(\beta^{n-2}\beta^2\right)
& \text{(BAM!: $x^2=3x+3$ for $x\in\{\alpha,\beta\}$)}\\
& = \left((1/2 + 5\cdot \sqrt{21}/42)\right)\cdot\alpha^n \\
&{}\qquad
+\left(1/2-5\cdot\sqrt{21}/42)\right)\cdot\beta^n \\
\end{align*}
and we're done.
These types of recurrences have a special name. This is a \emph{linear homogeneous recurrence relation of order-2}. That is, it has the form $s(n)=a\cdot s(n-1)+b\cdot s(n-2)$ with initial conditions $s(0)=\gamma$ and $s(1)=\delta$. These things can be solved mechanically for any values of $a,b,\gamma,\delta$. For example, enter
\begin{verbatim}
s(n) = 3*s(n-1) + 3*s(n-2), s(0)=1, s(1)=4
\end{verbatim}
into Wolfram Alpha.
\item Consider the set $S_n$ of binary strings whose length is $n$ and for which $010$ does not appear as a consecutive substring
\begin{compactenum}
\item[(a)] Argue that, for $n\ge 3$, \begin{equation} |S_n| = |S_{n-1}| + \sum_{k=3}^n |S_{n-k}| + 2\enspace . \end{equation}
For $n\ge 3$, any string in $S_n$ has one of the following forms:
\begin{compactenum}
\item A 1 followed by a string in $S_{n-1}$. There are $|S_{n-1}|$ such strings.
\item A sequence of $1\le j< n-2$ zeros followed by 11 followed by a string in $S_{n-j-2}$. For each $j\in\{1,\ldots,n-2\}$ there are $|S_{n-j-2}|$ such strings which makes a total of
\[ \sum_{j=1}^{n-2}|S_{j-2}| = \sum_{k=3}^n |S_k| \]
such strings
\item A sequence of $n-1$ zeros followed by 1. There is 1 such string.
\item A sequence of $n$ zeros. There is one such string.
\end{compactenum}
Therefore,
\[ S_n = |S_{n-1}|+\sum_{k=3}^n |S_{n-k}| + 2 \enspace . \]
\item[(b)] Write a program to compute $|S_n|$ for $n=0,\ldots,20$ and look up the resulting sequence in the [Online Encyclopedia of Integer Sequences](https://oeis.org/). What did you find?
Here is a Python program that does it:
\begin{lstlisting}[language=python]
def s(n):
if n <= 2: return 2**n
return s(n-1) + sum([s(n-k) for k in range(3,n+1)]) + 2
print([s(n) for n in range(21)])
\end{lstlisting}
Here is the output:
\begin{verbatim}
[1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329,
5842, 10252, 17991, 31572, 55405, 97229]
\end{verbatim}
When I enter this into the OEIS I get sequence number A005251, described as
\begin{verbatim}
a(n+3) = number of n-bit sequences that avoid 010.
Example: For n=4 the 12 sequences are all 4-bit sequences except 0100, 0101, 0010, 1010.
\end{verbatim}
\url{https://oeis.org/A005251}
Interestingly, this sequence comes from a simpler recurrence: \verb/a(n) = a(n-1) + a(n-2) + a(n-4)/.
\end{compactenum}
\end{compactenum}
\end{document}
**