%
% Assignment 0d for CS3530 Computational Theory:
% LaTeX
% Fall 2023
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{emp,ifpdf}
\usepackage{graphicx}

\ifpdf\DeclareGraphicsRule{*}{mps}{*}{}\fi

\empprelude{input boxes; input theory}

% skip for paragraphs, don't indent
\addtolength{\parskip}{0.5\baselineskip}
\parindent=0pt

\begin{document}
\begin{empfile}

\begin{center}
\textbf{\Large CS 3530: Assignment 0d} \\[2mm]
Fall 2023

\emph{Your Name Here}
\end{center}

\raggedright

\section*{Problem 0.10 (7 points)}

\subsection*{Problem}

Find the error in the following proof that $2 = 1$.

Consider the equation $a = b$.  Multiply both sides by $a$ to obtain $a^2 = ab$.  Subtract
$b^2$ from both sides to get $a^2 - b^2 = ab - b^2$.  Now factor each side, $(a + b)(a - b) = b(a-b)$,
and divide each side by $(a - b)$ to get $a + b = b$.  Finally, let $a$ and $b$ equal $1$, which shows
that $2 = 1$.

\textbf{Solution}

\emph{Your Solution Here}

\section*{Exercise 0.11 (13 points)}

\subsection*{Problem}

Let $S(n) = 1 + 2 + \cdots + n$ be the sum of the first $n$ natural numbers and let
$C(n) = 1^3 + 2^3 + \cdots + n^3$ be the sum of the first $n$ cubes.  Prove the following equalities
by induction on $n$, to arrive at the curious conclusion that $C(n) = S^2(n)$ for every $n$.

\begin{itemize}
\item[a.] $S(n) = \frac{1}{2}n(n+1)$.
  
\textbf{Solution}

\emph{Your Solution Here}

\item[b.] $C(n) = \frac{1}{4}(n^4 + 2n^3 + n^2) = \frac{1}{4}n^2(n+1)^2 $.
  
\textbf{Solution}

\emph{Your Solution Here}

\end{itemize}
  
\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}
