%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan, with updates,
% edits, and simplifications by the lovely folks below.
%
% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Fall 2020 by Lucy Lu
% Updated for Winter/Spring 2021 by Cynthia Bailey Lee
% Updated for Fall 2021 by Grant McClearn
% Commands slimmed down and simplified in Fall 2022 by Keith Schwarz

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage{braket}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{wrapfig}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#4}
\author{[TODO: Replace this with your name(s)]}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 5}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Fall 2022}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\powerset}[1]{\wp\left(#1\right)}
\newcommand{\suchthat}{\ \vert \ }
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\qed}{\blacksquare}
\newcommand{\accepts}{\text{ accepts }}
\newcommand{\rejects}{\text{ rejects }}
\newcommand{\loopson}{\text{ loops on }}
\newcommand{\haltson}{\text{ halts on }}
\newcommand{\encoded}[1]{\left\langle#1\right\rangle}
\newcommand{\rlangs}{\mathbf{R}}
\newcommand{\relangs}{\mathbf{RE}}
\newcommand{\corelangs}{\text{co-}\mathbf{RE}}
\newcommand{\plangs}{\mathbf{P}}
\newcommand{\nplangs}{\mathbf{NP}}

\renewcommand{\labelitemii}{$\bullet$}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
\usepackage{float}

\makeatother

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\usepackage{boxedminipage}
\newenvironment{blank}{\colorbox{shadecolor}{\strut \underline{\ \ \ \ \ }}}

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, November 4 at 2:30 pm Pacific}
\end{center}

This Problem Set has no coding questions; all answers to the Problem Set go in this file.

Some notation you might find useful here:

\begin{itemize}
    \item Subscripts can be written as $a_{index}$. Remember to use curly braces if you have a multicharacter expression as a subscript.
    \item The notation $f^\star(n)$ comes up in the last problem.
\end{itemize}

\pagebreak

\section*{Problem One: Induction Proof Critiques}
    i.
    \begin{shaded}
    Write your answer to Problem One, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem One, part ii. here.
    \end{shaded}
    
\newpage

\section*{Problem Two: Recurrence Relations}
Fill in the blanks to Problem Two below.

 \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} For all natural numbers $n$, we have $a_n = 2^n$.
            \\ \emph{Proof: } Let $P(n)$ be the statement ``$a_n = 2^n$.'' We will prove by induction that $P(n)$ holds for all $n \in \mathbb{N}$, from which the theorem follows. \\ As our base case, we prove $P(\blank)$, that \blank. To see this, \blank. \\ For our inductive step, assume for some arbitrary $k \in \mathbb{N}$ that $P(k)$ is true, meaning that \blank. We need to show $P(\blank)$, meaning that \blank. To see this, note that 
            \begin{equation*}
                \begin{split}
                    a_{k+1} &= \blank \\
                       &= \blank \text{(by our IH)}\\
                       &= \blank.
                \end{split}
            \end{equation*}
            Therefore, we see that \blank, so $P(\blank)$ is true, completing the induction. \qedsymbol
         \end{boxedminipage}
\end{center}

\newpage

\section*{Problem Three: Stacking Cans}
    i.
    \begin{shaded}
    Write your answer to Problem Three, part i. here.
    \end{shaded}
    
    ii. Fill in the blanks to Problem Three, part ii. below.
    \begin{shaded}
    \begin{itemize}
        \item A $0$-layer tower has $\blank$ cans in in it.
        \item A $1$-layer tower has $1$ can in it.
        \item A $2$-layer tower has $8$ cans in it.
        \item A $3$-layer tower has $\blank$ cans in it.
        \item A $4$-layer tower has $\blank$ cans in it.
        \item A $5$-layer tower has $\blank$ cans in it.
        \item A $6$-layer tower has $\blank$ cans in it.
        \item A $7$-layer tower has $\blank$ cans in it.
        \item A $8$-layer tower has $\blank$ cans in it.
        \item A $9$-layer tower has $\blank$ cans in it.
        \item A $10$-layer tower has $\blank$ cans in it.
    \end{itemize}
    \end{shaded}
    
    iii. Fill in the blank to Problem Three, part iii. below.
    \begin{shaded}
    An $n$-layer tower has \blank cans in it.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Three, part iv. here.
    \end{shaded}

\newpage

\section*{Problem Four: The Circle Game}
    i.
    \begin{shaded}
    Write your answer to Problem Four, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Four, part ii. here.
    \end{shaded}
    
\newpage

\section*{Problem Five: Regular Graphs}
\begin{shaded}
Write your answer to Problem Five here.
\end{shaded}

\newpage

\section*{Problem Six: It’ll All Even Out}
    i.
    \begin{shaded}
    Write your answer to Problem Six, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Six, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Six, part iii. here.
    \end{shaded}
    
\newpage

\section*{Optional Fun Problem: Egyptian Fractions}
\begin{shaded}
Write your answer to the Optional Fun Problem here.
\end{shaded}

\end{document}