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

\begin{document}

\centerline{\bf Homework 5 MORALLY Due Mar 14 at 9:00AM}
\newcommand{\implies}{\Rightarrow}
\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}^+}

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

\begin{enumerate}

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

\item
(20 points- AND if you got the Dup-Spoiler Question wrong on the
untimed midterm, but get THIS question right, you will get FULL CREDIT
on the that question)

For this problem you may ASSUME the following
\begin{itemize}
\item 
For all $n$, for all $a\ge 2^n$, DUP wins $(\N+\N^*,L_a;n)$.
\item 
For all $n$, for all $a\ge 2^n$, DUP wins $(\N+\Z+\N^*,L_a;n)$.
\item 
For all $n$, for all $a\ge 2^n$, DUP wins $(\N+\Z+\Z+\N^*,L_a;n)$.
\item 
For all $n$,  DUP wins $(\N,\N+\Z;n)$ .
\item 
\end{itemize} 


And NOW the question.
Prove the following rigorously, similar to the end of the slides on DUP SPOILER games. 
\begin{enumerate}
\item
For all $n$, DUP wins the $(\N,\N+\Z+\Z;n)$ game.
\item 
For all $n$, DUP wins the $(\N,\N+\Z+\Z+\Z;n)$ game.
(You can use Part a)
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

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

$a_1=10$

$a_2=20$

$a_3=30$ 

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

Using constructive induction find NATURAL NUMBERS $A,B$ such that 

$(\forall n\ge 1)[a_n \le AB^n]$. 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(40 points)
In this problem $\frac{n}{2}$ means $\floor{\frac{n}{2}}$. 
In this problem we will be looking at the recurrence

$a_1=1$

$(\forall n\ge 2)[a_n = a_{n-1} + a_{n/2}]$.

\begin{enumerate}
\item
(0 points but you will need it for the later parts)
Write a program that does the following:

On input $d,N$ determine

For how many $1\le n\le N$ is $a_n\equiv 0 \pmod d$.

For how many $1\le n\le N$ is $a_n\equiv 1 \pmod d$.

For how many $1\le n\le N$ is $a_n\equiv 2 \pmod d$.

$\vdots$

For how many $1\le n\le N$ is $a_n\equiv d-1 \pmod d$.

(Advice: Compute $a_n \pmod d$ instead of $a_n$ to avoid 
large numbers.)

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(20 points) 
Run your program for $N=1000$ and $d=2,3,\ldots,20$. 
Present your data as follows (the numbers below are made up)

$d=2$
\[
\begin{array}{|c|c|}
\hline
c &  |\{ n \colon n\equiv c \pmod 2\}| \cr
\hline
0 & 410 \cr
1 & 590 \cr
\hline
\end{array}
\]

$d=3$
\[
\begin{array}{|c|c|}
\hline
c &  |\{ n \colon n\equiv c \pmod 3\}| \cr
\hline
0 & 333 \cr
1 & 333 \cr
2 & 334 \cr
\hline
\end{array}
\]


\begin{comment}
$d=4$
\[
\begin{array}{|c|c|}
\hline
c &  |\{ n \colon n\equiv c \pmod 4\}| \cr
\hline
0 & 100 \cr
1 & 200 \cr
2 & 300 \cr
3 & 400 \cr
\hline
\end{array}
\]
\end{comment}

\qquad \bm{\vdots} \qquad \bm{\vdots} \qquad \bm{\vdots} \qquad \bm{\vdots} \qquad \bm{\vdots}

$d=20$
\[
\begin{array}{|c|c|}
\hline
c &  |\{ n \colon n\equiv c \pmod {20}\}| \cr
\hline
0 & 100 \cr
1 & 0 \cr
2 & 100 \cr
3 & 0 \cr
4 & 25 \cr
5 & 25 \cr
6 & 25 \cr
7 & 25 \cr
8 & 100 \cr
9 & 0 \cr
10 & 100 \cr
11 & 0 \cr
12 & 25 \cr
13 & 25 \cr
14 & 25 \cr
15 & 25 \cr
16 & 100 \cr
17 & 100 \cr
18 & 200 \cr
19 & 0 \cr
\hline
\end{array}
\]

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(20 points)
Based on your data make a conjecture of the form:

{\it
Let $c,d$ be such that $0\le c\le d-1$ and $d\ge 2$. 
There exists an infinite number of $n$ such that $a_n\equiv c \pmod d$
IFF $XXX(c,d)$.
}

\end{enumerate}
\end{enumerate}

\end{document}