% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 07 --- INSERT NAME HERE}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


\problem\ [5pts] Consider the sequence $\{ A_n \}_{n=0}^\infty$ where each element of the sequence is a set $A_n$, defined by $A_0 = \varnothing$ and for $n \geq 1$, $A_n = \{ |A_i| : 0 \leq i < n\}$. Prove that $|A_n| = n$ for all $n \geq 0$.

% Problems about Mathematical Induction!
% \clearpage
\problem\ [5pts] Define a sequence $\{c_n\}_{n=0}^\infty$ by $c_0 = 1$ and for all $n \geq 1$, let $c_n = \sum_{i=0}^{n-1} \frac{c_i}{2^{n-i}}$. Prove that for all $n \geq 1$, $c_n = \frac{1}{2}$. [Note: There are two ways to prove this statement. One is by strong induction. The other is to use weak induction after proving an equivalent recurrence relation. Either will be accepted.]



% Problems about Mathematical Induction!
% \clearpage
\problem\ [10pts] The \emph{merge sort algorithm} sorts a list of $n$ numbers $x_1,\dots,x_n$.
The algorithm works by first testing if $n = 1$, and if so does nothing. 
Otherwise, the algorithm recursively calls itself on the first $\lfloor n/2\rfloor$ entries, and then calls itself on the last $\lceil n/2\rceil$ entries, then ``shuffles'' them together by iterating through the two parts, selecting the minimum elements from each part until creating a sorted list of $n$ entries.
If $t_n$ is the time it takes to run the merge sort algorithm on a list of $n$ numbers, then $t_1 = 1$ (only need to test one operation), and (roughly)
\[
	t_n = 2t_{\lceil n/2\rceil } + n
\]
Using this recurrence relation and strong induction, prove that $t_n \leq 2n\log_2(n+1)$ for all $n \geq 1$.


% Problems about State Machines!
% \clearpage
\problem\ [10pts] Let $S = (\Q, T, 0)$ be a state machine where the states are rational numbers ($\Q$) and the transitions are of the form $x \to x+1$, $x \to 3x$, and $x \to \frac{x}{2}$, and the initial state is $0$. Prove that no matter what transitions are used, the state $\frac{1}{3}$ will never be reached. [For 2 extra points: Prove that for any $\varepsilon > 0$, there is a sequence of transitions such that a state $x$ is reachable where $|x-\frac{1}{3}| < \varepsilon$.]


% Problems about State Machines!
% \clearpage
\problem\ [15pts] Let $\Sigma = \{ 0, 1\}$ (here we say $\Sigma$ is the name of a set, not the summation notation). For $k \geq 0$, the set $\Sigma^k$ is the set of $k$-tuples where every entry comes from $\Sigma$. 
The set $\Sigma^*$ is equal to $\cup_{k=0}^\infty \Sigma^k$, the set of all finite binary strings (note that for every finite binary string $\vx$ of length $k$, $\vx \in \Sigma^k \subset \Sigma^*$). 
We will denote a string $\vx = (x_1,x_2,\dots,x_k)$ as $x_1x_2\dots x_k$.
Define a state machine $(\Sigma^*, T, 0)$ where the initial state is the string $0$, and the transitions are of the form
\begin{align*}
x_1x_2\dots x_{k-1}1 &\to x_1x_2\dots x_{k-1}10 &(1) \\
x_1x_2\dots x_{k-1}0 &\to x_1x_2\dots x_{k-1}00  &(2)\\
x_1x_2\dots x_{k-1}0 &\to x_1x_2\dots x_{k-1}01 &(3)\\
x_1x_2\dots x_{k-1}x_k &\to x_kx_{k-1}\dots x_2x_1x_1x_2\dots x_{k-1}x_k.&(4)
\end{align*}
Note that there are four types of transitions: (1) Take a string ending in 1 and add a 0, (2) take a string ending in 0 and add a 0, (3) take a string ending in 0 and add a 1, (4) take a string and add its reversal to the beginning (turning it into a palindrome).

\textbf{a.} Prove that the string $10011001$ is reachable from the initial string $0$.

\textbf{b.} Prove that the string $0110110$ is not reachable from the initial string $0$.

\textbf{c.}  Prove that a reachable string can never contain three consecutive 1's.
















\end{document} 