\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Homework 1}{Due Wed, Jan. 22, 2025}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item Prove that for every nonnegative integer $n$, we have $\sum_{k=1}^n k^2 = [(2n+1)(n+1)n]/6$.

\item Recall that $n! = 1\cdot 2\cdot \cdots \cdot n$.  For $n\ge 0$, find a formula for $1+\sum_{k=1}^n k\cdot k!$ and prove your formula is correct.

\item The \emph{adjusted Fibonacci sequence} $\hat F_n$ is given by $\hat F_0 = \hat F_1 = 1$ and $\hat F_n = \hat F_{n-1} + \hat F_{n-2}$ for $n\ge 2$.  (Note that $\hat F_2 = \hat F_1 + \hat F_0 = 1 + 1 = 2$, and $\hat F_3 = \hat F_2 + \hat F_1 = 2 + 1 = 3$.)  Prove that for $n\ge 0$, we have $\hat F_n \le \phi^n$, where $\phi=(1+\sqrt{5})/2$.

\item A \emph{unit fraction} is a rational number of the form $1/n$ for some positive integer $n$.  An \emph{Egyptian fraction} is the sum of zero or more distinct unit fractions.  For example, $\frac{29}{45}$ is an Egyptian fraction since $\frac{29}{45} = \frac{1}{4} + \frac{1}{5} + \frac{1}{9} + \frac{1}{12}$.  Although $\frac{11}{12} = \frac{1}{3} + \frac{1}{3} + \frac{1}{4}$, this is not enough to establish that $\frac{11}{12}$ is an Egyptian fraction since the unit sums are not distinct.  However, $\frac{11}{12} = \frac{1}{2} + \frac{1}{4} + \frac{1}{6}$ does establish that $\frac{11}{12}$ is an Egyptian fraction.
\begin{enumerate}
	\item Let $a$ and $b$ be nonnegative integers with $0<a<b$, and let $n$ be the smallest positive integer such that $\frac{1}{n} \le \frac{a}{b}$.  Prove that $\frac{a}{b} - \frac{1}{n} = \frac{c}{d}$ for some nonnegative integers $c$ and $d$ such that $c<a$ and $\frac{c}{d} < \frac{1}{n}$.
	
	\item Prove that if $a$ and $b$ are nonnegative integers with $a<b$, then $\frac{a}{b}$ is an Egyptian fraction.
\end{enumerate}
Comment: with part (b) and the fact that the Harmonic series $1 + \frac{1}{2} + \frac{1}{3} + \cdots$ diverges, one can show that every nonnegative rational number is an Egyptian fraction.

\end{enumerate}
\end{document}
