%
% 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 \#5}
\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 --- Spring 2026}
\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}}
\NewDocumentCommand\powerset{e{^}m}{
    \IfNoValueTF{#1}
        {\wp\left(#2\right)}
    {\wp^{#1}\left(#2\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, May 8th, at 1:00 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 Edges in a graph can be written as $\set{u, v}$.
\end{itemize}

\pagebreak

\section*{Problem One: Induction Proof Critiques}
    i.
    \begin{shaded}
    \textbf{Induction Proofwriting Checklist:} Write your answers in the blanks below.
    \begin{itemize}
    	\item Make $P(n)$ a Predicate, Not a Number or Function: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
	\item Watch Your Variable Scoping in $P(n)$:  \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
	\item ``Build Up'' if $P(n)$ is Existentially Quantified; ``Build Down'' if $P(n)$ is Universally-Quantified: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
	\item Choose the Simplest Base Cases Possible, and Avoid Redundant Base Cases: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
    \end{itemize}
    
    \textbf{Are there any logic errors? If so, where, and why are they logic errors?}: Write your answer here. \\
    
    \textbf{Is the overall theorem true? If so, just say so. If not, give a counterexample.}: Write your answer here.
    \end{shaded}

    \newpage
    
    ii.
    \begin{shaded}
    \textbf{Induction Proofwriting Checklist:} Write your answers in the blanks below.
    \begin{itemize}
    	\item Make $P(n)$ a Predicate, Not a Number or Function: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
	\item Watch Your Variable Scoping in $P(n)$:  \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
	\item ``Build Up'' if $P(n)$ is Existentially Quantified; ``Build Down'' if $P(n)$ is Universally-Quantified: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
	\item Choose the Simplest Base Cases Possible, and Avoid Redundant Base Cases: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs and what exactly went wrong.
    \end{itemize}
    
    \textbf{Are there any logic errors? If so, where, and why are they logic errors?}: Write your answer here. \\
    
    \textbf{Is the overall theorem true? If so, just say so. If not, give a counterexample.}: Write your answer 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: Square Triangular Numbers}
    \begin{shaded}
    Write your answer to Problem Three here.
    \end{shaded}

    \newpage

\newpage

\section*{Problem Four: Presenters Presenting Presents}
    i.
    \begin{shaded}
    Write your answer to Problem Four, part i. here.
    \end{shaded}

    \newpage

    ii.
    \begin{shaded}
    Write your answer to Problem Four, part ii. here.
    \end{shaded}

    \newpage
    
\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}

    \newpage

    ii.
    \begin{shaded}
    Write your answer to Problem Six, part ii. here.
    \end{shaded}

    \newpage

    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}