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

1. Prove that for every nonnegative integer $n$, we have ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^n{k}^2=[(2n+1)(n+1)n]∕6$.
2. Recall that $n!=1\cdot 2\cdot \cdots \cdot n$. For $n\ge 0$, find a formula for $1+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^{n}k\cdot k!$ and prove your formula is correct.
3. The adjusted Fibonacci sequence ${\widehat{F}}_n$ is given by ${\widehat{F}}_0={\widehat{F}}_1=1$ and ${\widehat{F}}_n={\widehat{F}}_{n-1}+{\widehat{F}}_{n-2}$ for $n\ge 2$. (Note that ${\widehat{F}}_2={\widehat{F}}_1+{\widehat{F}}_0=1+1=2$, and ${\widehat{F}}_3={\widehat{F}}_2+{\widehat{F}}_1=2+1=3$.) Prove that for $n\ge 0$, we have ${\widehat{F}}_n\le {\varphi }^n$, where $\varphi =(1+\sqrt{5})∕2$.

4. A unit fraction is a rational number of the form $1∕n$ for some positive integer $n$. An 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 fractions 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.

   1. 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}$.
   2. Prove that if $a$ and $b$ are nonnegative integers with $a<b$, then $\frac{a}{b}$ is an Egyptian fraction.

   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.