\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}

\begin{document}

\centerline{\bf Homework 7 MORALLY Due Apr 4 at 9:00AM}
\newcommand{\MOD}{{\rm MOD}}
\newcommand{\PRIMES}{{\rm PRIMES}}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}

\newcommand{\NCU}{{\rm NCU}}
\newcommand{\NCUZ}{{\rm NCUZ}}


\centerline{\bf WARNING: THIS HW IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}

\begin{enumerate}

\item 
(0 points but please DO IT)
What is your name?

\item
(25 points)
Let $a_n$ be defined by

$a_1=1$

$a_2=21$

$(\forall n\ge 3)[a_n = 7a_{n-1} + 8a_{\floor{\frac{n}{2}}} + 6].$

Show by induction that,  for all $n\ge 1$, $a_n\equiv 1 \pmod {20}$. 



\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage

\item
(24 points)
In class I prove the following four ways:

$$(\forall n\ge 3)(\exists d_1<\cdots<d_n\in\N)\biggl [1 = \frac{1}{d_1} + \cdots + \frac{1}{d_n}\biggr ]$$

Each way I proved it can be re-interpreted as an algorithm that will,

Given $n\ge 3$, generate $d_1<\cdots < d_n$ such that $1 = \frac{1}{d_1} + \cdots + \frac{1}{d_n}$.

\begin{enumerate}
\item 
(8 points) 
Use the proofs to generate three ways to write 1 as the sum of FOUR reciprocals.

\item
(8 points) 
Use the proofs to generate four ways to write 1 as the sum of FIVE reciprocals.

\item 
(8 points) 
Use the proofs to generate four ways to write 1 as the sum of SIX reciprocals.
\end{enumerate}

DO NOT show work- just give us 
three $(d_1,d_2,d_3,d_4)$,  
four $(d_1,d_2,d_3,d_4,d_5)$, 
and four  $(d_1,d_2,d_3,d_4,d_5,d_6)$.


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(26 points) 
(As always, $\N$ contains 0.) 
Bill has a statement $P(n)$. 
He has proven the following:

$$(\exists n\ge 100)[P(n)] \implies (\forall n\ge 10)[P(n)]$$

Let 

$$A = \{ n \colon P(n) \hbox{ is true } \}.$$

\begin{enumerate}
\item 
(13 points) 
List ALL possibilities for what $A$ could be ($A$ is a subset of $\N$.) 
(For a start: $A$ could be empty, $A$ could be $\N$, $A$ could be $\{10,11,12,\ldots\}$,
but there are more possibilities: Describe them all.) 
\item
(13 points) 
How many possibilities are there for $A$?
How many are finite? How many are infinite and have a finite complement?
How many are infinite and have an infinite complement?
\end{enumerate} 

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(25 points) 
In this problem we want you to write the answer in BOTH the notation form
(e.g., $\binom{11}{3}$) and as an actual number (e.g., 165). 
\begin{enumerate}
\item
(8 points) There are 10 people at a party. Everyone hugs everyone!
How many hugs are there? 
(NOTE- this is after COVID. They are going to party like its 2019.) 
\item 
(8 points) There are 10 people at a party. Everyone gives everyone else a gift!
How many gifts are there? 
\item
(9 points) There are 20 students taking Ramsey Theory (all the cool kids are into the Ramsey!). 
They meet in a room like our classroom with tables. Bill demands that
6 sit at table 1, 5 sit at table 2,  and 9 sit at table 3.
How many ways can they do this (within a table we do not care where they sit). 
\end{enumerate}

\end{enumerate}
\end{document}