% Homework 4, CSCE 235, spring 2007
% Assigned 21 February 2007; due 28 February 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=8.5truein
\pdfhorigin=1.5truein \pdfvorigin=1.25truein

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~4} (120~points)}
\centerline{Assigned Wednesday, February~21, 2007}
\centerline{Due Wednesday, February~28, 2007}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (16~points) For each of the following functions, give the domain,
codomain, and range of the function; specify whether or not it is one-to-one,
whether or not it is onto, whether or not it is bijective, and whether or not
it is invertible; and if it is invertible, give its inverse.

\smallskip

\item{(a)} $f:\Q\to\Q$ given by $f(x)={1\over2}x^2-4$.
\smallskip
\item{(b)} $g:\R\to\R$ given by $g(x)=x^5$.
\smallskip
\item{(c)} $h:\R\to\Z$ given by $h(x)=\lfloor x\rfloor$.
\smallskip
\item{(d)} $\phi:\N\to\N\times\N$ given by $\phi(n)=(n,n)$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) Let $f:\R\to\R$ be given by $f(x)=x^2+1$ and let
$g:\R\to\R$ be given by $g(x)=3x+2$.

\smallskip

\item{(a)} Find $f\circ g$.
\item{(b)} What is the value of $(f\circ g)(1)$? of $(f\circ g)(-1)$?
\item{(c)} Find $g\circ f$.
\item{(d)} What is the value of $(g\circ f)(1)$? of $(g\circ f)(-1)$?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Find these values.

\smallskip

\item{(a)} $\lfloor1.02\rfloor$
\item{(b)} $\lceil1.02\rceil$
\item{(c)} $\lfloor-3.8\rfloor$
\item{(d)} $\lceil-3.8\rceil$
\item{(e)} $8!$
\item{(f)} $n!/(n-4)!$, where $n$ is an integer greater than~4

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (20~points) Let $P(n)$ be the statement that
$$1^2+2^2+3^2+\cdots+n^2={n(n+1)(2n+1)\over6}$$
for the positive integer~$n$. The parts of this problem outline a proof using
mathematical induction to show that this formula is true for all positive
integers~$n$.

\smallskip

\item{(a)} What is the statement~$P(1)$?
\item{(b)} Show that $P(1)$ is true, completing the basis step of the proof.
\item{(c)} What is the inductive hypothesis?
\item{(d)} What do you need to prove in the inductive step?
\item{(e)} Complete the inductive step.
\item{(f)} Explain why these steps show that this formula is true whenever $n$
is a positive integer.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (20~points) Prove that for every positive integer~$n$,
$$1\cdot 2+2\cdot 3+\cdots+n(n+1)={n(n+1)(n+2)\over3}.$$

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (20~points) Let $Q(n)$ be the statement that a postage of $n$~cents
can be formed using just 3-cent stamps and 5-cent stamps. The parts of this
problem outline a strong induction proof that $Q(n)$ is true for $n\ge8$.

\smallskip

\item{(a)} Show that the statements $Q(8)$,~$Q(9)$, and~$Q(10)$ are true,
completing the basis step of the proof.
\item{(b)} What is the inductive hypothesis of the proof?
\item{(c)} What do you need to prove in the inductive step?
\item{(d)} Complete the inductive step.
\item{(e)} Explain why these steps show that this statement is true whenever
$n\ge8$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) Find $f(1)$,~$f(2)$, $f(3)$, and~$f(4)$ if $f(n)$ is
defined recursively by $f(0)=1$ and for $n=1,2,3,\ldots\,$,

\smallskip

\item{(a)} $f(n)=f(n-1)+2$.
\item{(b)} $f(n)=\bigl(f(n-1)+1)^2$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) Find $f(2)$,~$f(3)$, $f(4)$, and~$f(5)$ if $f(n)$ is
defined recursively by $f(0)=-1$, $f(1)=2$, and for $n=2,3,4,\ldots\,$,

\smallskip

\item{(a)} $f(n)=f(n-1)+3f(n-2)$.
\item{(b)} $f(n)=f(n-2)/f(n-1)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye