\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{fancyhdr}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{xcolor}
\usepackage[hidelinks]{hyperref}
\pagestyle{fancy}
\fancyhf{}
\lhead{\textbf{First Last}}
\chead{\textbf{CS 250 -- Homework 4}}
\rhead{\today}
\cfoot{\thepage}
\newtheorem*{problem}{Problem}
\newenvironment{solution}{\noindent\textbf{Solution.}\quad}{\hfill$\blacksquare$\par\medskip}
\definecolor{codebg}{HTML}{F6F8FA}
\lstset{
basicstyle=\ttfamily\footnotesize,
backgroundcolor=\color{codebg},
frame=single,
breaklines=true,
numbers=left,
numberstyle=\tiny\color{gray},
keywordstyle=\color{blue!70!black}\bfseries,
commentstyle=\color{green!40!black}\itshape,
stringstyle=\color{orange!80!black}
}
\begin{document}
\begin{center}
{\LARGE\bfseries CS 250 -- Homework 4}\\[0.2em]
{\large Discrete Mathematics -- Fall Semester}\\[0.2em]
{\large Due: Friday, 11:59 PM}
\end{center}
\noindent\textbf{Name:} First Last \hfill \textbf{Student ID:} 12345678
\vspace{1em}
\hrule
\vspace{1em}
\begin{problem}[1]
Prove that for all $n \ge 1$, $\sum_{i=1}^n i = \frac{n(n+1)}{2}$.
\end{problem}
\begin{solution}
By induction on $n$. For $n=1$, $1 = 1\cdot 2/2$. Assume the statement for $n=k$.
Then $\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$.
\end{solution}
\begin{problem}[2]
Let $f: A \to B$ be a function.
\begin{enumerate}[label=(\alph*)]
\item Define what it means for $f$ to be injective.
\item Prove that if $f, g$ are injective, so is $g \circ f$.
\item Give a counterexample to the converse.
\end{enumerate}
\end{problem}
\begin{solution}
(a) $f$ is injective iff $f(x) = f(y) \Rightarrow x = y$. \\
(b) Suppose $(g\circ f)(x) = (g\circ f)(y)$. Then $g(f(x)) = g(f(y))$;
injectivity of $g$ gives $f(x) = f(y)$; injectivity of $f$ gives $x = y$. \\
(c) Let $f: \{1\}\to\{1,2\}$, $f(1)=1$; let $g: \{1,2\}\to\{1\}$, $g(\cdot)=1$.
Then $g\circ f$ is injective but $g$ is not.
\end{solution}
\begin{problem}[3]
Implement Euclid's algorithm and test it.
\end{problem}
\begin{solution}
\begin{lstlisting}[language=Python,caption={Euclidean GCD}]
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(48, 18)) # -> 6
print(gcd(100, 75)) # -> 25
\end{lstlisting}
\end{solution}
\begin{problem}[4]
Show that the set $\{ (x,y) \in \mathbb{R}^2 : x^2 + y^2 < 1 \}$ is open.
\end{problem}
\begin{solution}
For any point $(a,b)$ in the set, let $r = 1 - \sqrt{a^2+b^2} > 0$.
The open ball $B_r(a,b)$ is contained in the set by the triangle inequality.
Thus every point is interior, so the set is open.
\end{solution}
\end{document}

PDF Preview
Create an account to compile and preview