\documentclass[12pt]{article}
\newcommand{\st}{\mathrel{:}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\I}{{\sf I}}
\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{\Rpos}{{\sf R}^+}

\usepackage{amsmath}
\usepackage{comment}


\begin{document}

  \centerline{\bf 250 Untimed Midterm 2} 
  \centerline{\bf Morally Due Monday April 8}


\section{An Interesting Sum (7  points) }

For this problem you may approximate 

$$(n-1)^{11}$$ 

by 

$$n^{11}-11n^{10}$$

any time it appears. 

Consider the sum 

$$\sum_{i=100}^n i^{10}.$$

({\bf NOTE} that the summation starts at 100, so the base case will be $n=100$.)

We are NOT going to ask you to get a
closed form for it (there is one but its a mess). 
{\bf BY CONSTRUCTIVE INDUCTION} find a constant $A$ such that

$$(\forall n\ge 100)\biggl [\sum_{i=100}^n i^{10} \le An^{11}\biggr ].$$

Try to make $A$ as small as possible. 

({\bf NOTE-} There are other ways to do this but I want a proof by

\centerline{\bf CONSTRUCTIVE INDUCTION.} 

DO NOT be that guy who does it a different
way and claims that its right. That wastes my time and yours.)

({\bf NOTE-} Problem 2 implies Problem 1.
DO NOT be that guy who just does Problem 2 and claims he did Problem 1. 
{\bf JUST DO BOTH PROBLEMS}.)


\newpage


\section{A Generalization of an Interesting Sum (8 points)}

In this problem you may approximate 

$$(n-1)^a$$

by

$$n^a-an^{a-1}$$

any time it appears,


Let $a\in \N$ be such that $a\ge 11$. 

Consider the sum 

$$\sum_{i=100}^n i^a.$$

{\bf BY CONSTRUCTIVE INDUCTION} find a constant $B$ such that

$$(\forall n\ge 100)\biggl [\sum_{i=100}^n i^a \le Bn^{a+1}\biggr ].$$

({\bf NOTE-} There are other ways to do this but I want a proof by

\centerline{\bf CONSTRUCTIVE INDUCTION.} 

DO NOT be that guy who does it a different
way and claims that its right. That wastes my time and yours.)

\newpage 


\section{A Coin Problem (15 points)} 

The Daleks only have two coins: 
\begin{itemize}
\item 
a 10-cent coin, and 
\item 
a 13-cent coin. 
\end{itemize}

Note that there are some amounts they cannot create.
For example Davros cannot give Emily 22 cents. However, there is a $C\in\N$
such that 

\begin{itemize}
\item
$C-1$ cannot be written as $10x+13y$ where $x,y\in\N$, and 
\item
$(\forall n\ge C)(\exists x,y\in\N)[n=10x+13y]$. 
\end{itemize} 

And now finally the problem which will guide you to finding $C$. 

\begin{enumerate}
\item
Write a program that will, given $N\in\N$, 

determine, for all $1\le n\le N$ if $n$ can be written as the sum of
10's and 13's.
\item
Run the program on $N=1000$.
\item
Based on your numbers make a conjecture for what $C$ is.
\item
Prove your conjecture by induction.
\end{enumerate}

\newpage

\section{Sums of Squares (20 points)} 

In this problem we guide you through a proof that number of the
form $16^n(16k+15)$ cannot be written as the sum of 14 fourth-powers. 

\begin{enumerate}
\item
(0 points but you will need it later) 
Find the following set 

$$X = \{ x^4 \pmod {16} \st x\in \{0,\ldots,15\}\}.$$

\item
(3 points) 
Show that if $x\equiv 15 \pmod {16}$ then $x$ is NOT the sum of 14 fourth-powers. 

({\it Hint:} Show that any 14 elements of $X$ from Part a can never sum to 15 mod 16.) 


\item
(3 points) 
Show that if $x$ is odd then $x^4\equiv 1 \pmod {16}$.

{\bf Hints}

\begin{itemize}
\item 
Begin the proof by letting $x=2k+1$. 
\item 
Look up the Binomial Theorem. You will need it. 
\item 
Note that, for all  $k\in\N$, $k(k+1)$ is even. 
You will need this fact. 
\end{itemize} 


\item
(4 points) 
Prove that if $x_1^4+\cdots+x_{14}^4\equiv 0 \pmod {16}$ then 

\centerline{$(\forall i)[x_i\equiv 0 \pmod 2]$.} 


\item
(10 points) 
Prove the following by induction on $n$. 

{\bf Theorem} Let $n\ge 0$. Let $k\in\N$. Show that $16^n(16k+15)$ cannot be written
as the sum of 14  fourth-powers. 

\end{enumerate}

\end{document}