\documentclass[12pt]{article}

\begin{document}
\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}}

\centerline{Homework 5, MORALLY Due March 25}
\newcommand{\implies}{\Rightarrow}

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

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}
\item
(20 points)
\begin{enumerate}
\item
(0 points)
What is $\int_1^n x^2 dx$?
\item
(2 points)
Use the answer to part 1 to conjecture the FORM of the 
formula (with some of the coefficients not know) for
$$\sum_{i=1}^n i^2$$
(To make your life easier you can also conjecture what the first coefficient is
based on the interval.)
\item
(9 points)
(Use part b)
By plugging in $n=0$, $n=1$, and perhaps more find a very good guess
for the formula for $\sum_{i=1}^n i^2$.
Show your work of course.
(It should be the real formula.)
\item
(9 points)
(Use part b)
Derive the formula by constructive induction.
\end{enumerate}

\item
(20 points)
Recall our usual {\it induction scheme}:

From
\begin{itemize}
\item
$P(0)$
\item
$(\forall n\ge 0, n\in \N)[P(n)\rightarrow P(n+1)]$
\end{itemize}

we get $(\forall n\in \N)[P(n)]$.

This problem is about how to modify this scheme.

\begin{enumerate}
\item
(7 points)
Give a scheme that will show 

$$(\forall n\equiv 0 \pmod 4, n\in\N)[P(n)].$$
\item
(7 points)
Give a scheme that will show 
$$(\forall n\equiv 0,1 \pmod 4,n\in\N)[P(n)].$$
\item
(6 points)
Give a scheme that will show 
$$(\forall n\in \Z)[P(n)].$$
\end{enumerate}


\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(20 points)
Assume that there are constants $A,B,C,D$ such that 

$$(\forall n\ge 0, n\in \N) \left[ \sum_{i=1}^n i\times 2^{i} = An2^n + B2^n +Cn + D\right].$$


\begin{enumerate}

\item
(10 points)
Find $A,B,C,D$ by plugging in $n=0,1,2,3$ (or less if you don't need all of those)
into the equation.

\item
(10 points)
Find $A,B,C,D$ by constructive induction.

\item
(0 points- don't hand in) What are the PROS and CONS of each technique?

\item
(0 points- don't hand in) How could you have guessed the form of the summation above?
One way is with integrals. Can you think of another way?
\end{enumerate}


\item
(20 points)
Let $T(n)$ be defined by


$$T(1)=10$$


$$T(n) = T\biggl (\floor{\frac{n}{2}}\biggr ) + T\biggl (\floor{\frac{n}{3}}\biggr ) + 17n$$

By constructive induction find value $c\in\N$ such that $(\forall n)[T(n)\le cn$.
Try to make $c$ as small as possible (and its in $\N$ so this is possible).


\item
(20 points)
In the country of Fredonia they only use 10-cent coins and 11-cent coins.
Note that the people cannot have 9 cents on them, they can have 10, they
can have 11, but they can't have 12. 
\begin{enumerate}
\item
(0 points and don't hand anything in)
Write a program that will, for $n=1$ to 1000, determine which numbers of cents
good people of  Fredonia can have. 
\item
(5 points)
Make a conjecture of the form:

\begin{itemize}
\item
$n_0-1$ CANNOT be written in the form $10x+11y$ with $x,y\in\N$.
\item
$(\forall n\ge n_0)(\exists x,y\in\N)[n=10x+11y].$
\end{itemize}
(So you need to find $n_0$.)

\item
(15 points)
Prove your conjecture by induction.
\end{enumerate}


\end{enumerate}
\end{document}