\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}

\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}

\usepackage{enumitem}
\setlist{itemsep=0.5em}

%% header definitions
\def\course{MATH/CMSC H395}
\def\assign{HW \#2}
\def\doclink{\url{https://mathematicaster.org/teaching/discrete2026/hw/hw2.tex}}
\def\due{Sep 21}

%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}

% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}

% custom
\newenvironment{solution}{\noindent\textbf{Solution.}}{\qed}

%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}}       % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}}        % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert}     % absolute values, cardinality
\newcommand*{\eps}{\varepsilon}            % prettier epsilon
\newcommand*{\R}{\mathbb{R}}               % real numbers
\newcommand*{\C}{\mathbb{C}}               % complex numbers
\newcommand*{\Q}{\mathbb{Q}}               % rational numbers
\newcommand*{\Z}{\mathbb{Z}}               % integers
\newcommand*{\N}{\mathbb{N}}               % natural numbers
\newcommand*{\F}{\mathbb{F}}               % field
\newcommand*{\family}{\mathcal{F}}         % family
\newcommand*{\GL}{\mathbf{GL}}             % general linear group
\newcommand*{\what}[1]{\widehat{#1}}       % wider hat
\newcommand*{\wbar}[1]{\overline{#1}}      % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}}       % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}}         % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}}         % mathbb

% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}}       % probability
\DeclareMathOperator*{\E}{\mathbb{E}}          % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}}      % variance
\DeclareMathOperator*{\Span}{span}             % span
\DeclareMathOperator{\tr}{tr}                  % trace
\DeclareMathOperator{\rank}{rank}              % rank
\DeclareMathOperator{\supp}{supp}              % support
\DeclareMathOperator{\diam}{diam}



\begin{document}
\pagestyle{empty}

\noindent
\begin{minipage}{.33\textwidth}
	\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt

\noindent {\footnotesize This document is from \doclink}
\vskip10pt

\noindent {\small
    Solutions must be typeset in \LaTeX.
    Collaboration, but must be fully acknowledged.
    Any collaboration should involve only discussion; all writing \textbf{must} be done individually.
    Use of generative AI is \textbf{forbidden}.
    You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
}

\vskip20pt


\begin{problem}
    Show that for any fixed $d\geq 0$,
    \[
        \sum_{k=1}^n k^d\sim{n^{d+1}\over d+1}\qquad\text{as }n\to\infty.
    \]
\end{problem}


% \begin{problem}
%     Suppose that $f_1=\Theta(g_1)$ and $f_2=\Theta(g_2)$.
%     Prove that $f_1+f_2=\Theta\bigl(\max\{g_1,g_2\}\bigr)$.
% \end{problem}


% \begin{problem}
%     Writing $f\ll g$ to mean $f=o(g)$, show that
%     \[
%         \log^a n\ll 2^{\sqrt{\log n}}\ll n^b,
%     \]
%     for any fixed constants $a,b>0$.
% \end{problem}
% \begin{solution}
%
% \end{solution}


\begin{problem}
    Let $d(n)$ denote the number of divisors of $n$ (including $1$ and $n$) and define $\overline{d}(n)$ to be the average of $d(i)$ over $i\in[n]$.
    Prove that $\overline d(n)\sim\log n$.
\end{problem}



\begin{problem}
    Improve our in-class lower-bound on the harmonic numbers to $H_n\geq \log n+{1\over 2}$.

    Hint: Trapezoids!
\end{problem}





\end{document}
