% Homework 4 solutions, 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\frac#1#2{{\textstyle{{#1}\over{#2}}}} \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|} % Pilfered from an example on page 106 of the TeXbook \def\qed{{\unskip\nobreak\hfil\penalty50 \hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule} \parfillskip=0pt \finalhyphendemerits=0 \par}} \centerline{CSCE~235: Introduction to Discrete Structures} \centerline{{\bf Homework assignment~4} (solutions)} \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)$. \solution \part{(a)} The domain of~$f$ is~$\Q$; its codomain is~$\Q$; and its range is the set $$\left\{\,{a^2\over2b^2}-4\biggm|a\in\Z\land b\in\Z\,\right\}.$$ (It is incorrect to say that the range of~$f$ is $\{\,y\in\Q\mid y\ge-4\,\}$, since, for example, $-3$~is not in the range of~$f$.) This function is not one-to-one; for example, $f(-1)=f(1)$. This function is not onto; for example, no rational value of~$x$ satisfies $f(x)=-5$. Since it is not one-to-one and not onto, it is not bijective, which means it is not invertible. \part{(b)} The domain of~$g$ is~$\R$; its codomain is~$\R$; and its range is also~$\R$. This function is one-to-one, since if $x\not=y$ we have $x^5\not=y^5$, that~is, $g(x)\not=g(y)$, which means that no two distinct real numbers will be mapped by~$g$ to the same number. This function is onto, since for any given real number~$x$ we have $g(\root5\of x)=x$. Since this function is both one-to-one and onto, it is bijective, which means that it is invertible. The inverse of the function~$g$ is given by $g^{-1}(x)=\root5\of x$. \part{(c)} The domain of~$h$ is~$\R$; its codomain is~$\Z$; and its range is also~$\Z$. This function is not one-to-one, since for example $h(\pi)=3$ and $h(\sqrt{10})=3$, but $\pi\not=\sqrt{10}$. This function is onto, since for any integer~$n$ we have $h(n)=n$. Since this function is not one-to-one, it is not bijective, which means it is not invertible. \part{(d)} The domain of~$\phi$ is~$\N$; its codomain is~$\N\times\N$; and its range is the set $$\bigl\{\,(a,b)\in\N\times\N\bigm|a=b\,\bigr\}.$$ This function is one-to-one, since no two distinct natural numbers will be mapped by~$\phi$ to the same ordered pair. It is not onto, since, for example, no natural number~$n$ satisfies $\phi(n)=(1,2)$. Since it is not onto, it is not bijective, which means it is not invertible. \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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)$? \solution \part{(a)} $f\circ g=(3x+2)^2+1=9x^2+12x+5$. \mathpart{(b)} $$\eqalign{ (f\circ g)(1)&=9\cdot1^2+12\cdot1+5=26;\cr (f\circ g)(-1)&=9(-1)^2+12(-1)+5=2.\cr }$$ \part{(c)} $g\circ f=3(x^2+1)+2=3x^2+5$. \mathpart{(d)} $$\eqalign{ (g\circ f)(1)&=3\cdot1^2+5=8;\cr (g\circ f)(-1)&=3(-1)^2+5=8.\cr }$$ \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 \solution \part{(a)} $\lfloor1.02\rfloor=1$. \part{(b)} $\lceil1.02\rceil=2$. \part{(c)} $\lfloor-3.8\rfloor=-4$. \part{(d)} $\lceil-3.8\rceil=-3$. \part{(e)} $8!=8\times7\times6\times5\times4\times3\times2\times1=40\,320$. \mathpart{(f)} $$\eqalign{ {n!\over(n-4)!} &={n(n-1)(n-2)(n-3)(n-4)(n-5)\cdots\cdot3\cdot2\cdot1\over(n-4)(n-5)\cdots\cdot3\cdot2\cdot1}\cr &=n(n-1)(n-2)(n-3)\cr &=n^4-6n^3+11n^2-6n.\cr }$$ \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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. \solution \part{(a)} $P(1)$ is the statement that $$1^2={1(1+1)(2\cdot1+1)\over6}.$$ \part{(b)} $P(1)$ is true, because $$1^2=1={6\over6}={1\cdot2\cdot3\over6}={1(1+1)(2\cdot1+1)\over6}.$$ \part{(c)} The inductive hypothesis is the assumption that $P(k)$ is true for some positive integer~$k$, i.e., that $$1^2+2^2+3^2+\cdots+k^2={k(k+1)(2k+1)\over6}.$$ \part{(d)} In the inductive step we need to prove that if the inductive hypothesis holds [i.e., if $P(k)$ is true], then $P(k+1)$ is true. \part{(e)} When we add $(k+1)^2$ to both sides of the equation in part~(c), we get $$\eqalign{ 1^2+2^2+3^2+\cdots+k^2+(k+1)^2 &={k(k+1)(2k+1)\over6}+(k+1)^2\cr &={2k^3+3k^2+k\over6}+{6k^2+12k+6\over6}\cr &={2k^3+9k^2+13k+6\over6}\cr &={(k+1)(k+2)(2k+3)\over6}\cr &={(k+1)[(k+1)+1][2(k+1)+1]\over6}.\cr }$$ This shows that $P(k+1)$ is true under the assumption that $P(k)$ is true. \part{(f)} We have completed the basis step and the inductive step. In the basis step, part~(b), we showed that the formula is true if $n=1$, and in the inductive step, part~(e), we showed that if the formula is true for some positive integer~$k$ then it is also true for $k+1$. Therefore, by the principle of mathematical induction, the formula must be true for all positive integers. \qed \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \problem (20~points) Prove that for every positive integer~$n$, $$1\cdot2+2\cdot3+\cdots+n(n+1)={n(n+1)(n+2)\over3}.$$ \solution Let $P(n)$ be the proposition that $1\cdot2+2\cdot3+\cdots+n(n+1)=n(n+1)(n+2)/3$ for the integer~$n$. \medskip \noindent{\it Basis step.\/} $P(1)$~is true because $$1\cdot2=2={6\over3}={1\cdot2\cdot3\over3}={1(1+1)(1+2)\over3}.$$ \medskip \noindent{\it Inductive step.\/} For the inductive hypothesis, we assume that $P(k)$ is true for some positive integer~$k$, that~is, we assume that $$1\cdot2+2\cdot3+\cdots+k(k+1)={k(k+1)(k+2)\over3}.\eqno(1)$$ To carry out the inductive step, we need to show that if $P(k)$ is true, then $P(k+1)$ is also true. That is, we must show that $$1\cdot2+2\cdot3+\cdots+(k+1)[(k+1)+1]={(k+1)[(k+1)+1][(k+1)+2]\over3},$$ i.e., $$1\cdot2+2\cdot3+\cdots+(k+1)(k+2)={(k+1)(k+2)(k+3)\over3},\eqno(2)$$ assuming the inductive hypothesis~$P(k)$. If we add $(k+1)(k+2)$ to both sides of Equation~(1), we get $$\eqalign{ 1\cdot2+2\cdot3+\cdots+k(k+1)+(k+1)(k+2) &={k(k+1)(k+2)\over3}+(k+1)(k+2)\cr &={k(k+1)(k+2)\over3}+{3(k+1)(k+2)\over3}\cr &={k[(k+1)(k+2)]+3[(k+1)(k+2)]\over3}\cr &={(k+3)(k+1)(k+2)\over3}.\cr }$$ This shows that Equation~(2) is true if we assume the inductive hypothesis, which completes the inductive step. \medskip \noindent We have completed both the basis step and the inductive step. That~is, we have shown that $P(1)$ is true and the conditional statement $P(k)\to P(k+1)$ is true for all positive integers~$k$. Consequently, by the principle of mathematical induction we can conclude that $P(n)$ is true for all positive integers~$n$, i.e., $1\cdot2+2\cdot3+\cdots+n(n+1)=n(n+1)(n+2)/3$ for all positive integers~$n$. \qed \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$. \solution \part{(a)} $Q(8)$ is true, since a postage of 8~cents can be formed with one 3-cent stamp and one 5-cent stamp. $Q(9)$~is true, since a postage of 9~cents can be formed with three 3-cent stamps. $Q(10)$~is true, since a postage of 10~cents can be formed with two 5-cent stamps. \part{(b)} The inductive hypothesis is the statement that $Q(j)$ is true for all integers~$j$ with $8\le j\le k$, where $k$ is an integer with $k\ge10$. That~is, we assume that we can form postage of $j$~cents, where $8\le j\le k$. (In other words, we are assuming that for some particular positive integer $k\ge10$, we are able to form postage of any amount from 8~cents up to $k$~cents.) \part{(c)} To complete the inductive step, we need to show that under this assumption, $Q(k+1)$~is true, that~is, we can form postage of $k+1$~cents. \part{(d)} Using the inductive hypothesis, we can assume that $Q(k-2)$ is true because $k-2\ge8$, that~is, we can form postage of $k-2$~cents using just 3-cent stamps and 5-cent stamps. To form postage of $k+1$~cents, we need only add another 3-cent stamp to the stamps we used to form postage of $k-2$~cents. Hence, we have shown that if the inductive hypothesis is true, then $Q(k+1)$ is also true. \part{(e)} We showed directly that $Q(8)$,~$Q(9)$, and~$Q(10)$ are true, and in the inductive step we showed that if $Q(j)$ is true for all $8\le j\le k$ with $k\ge10$ then $Q(k+1)$ is true. By the principle of strong induction, then, $Q(n)$~is true for all integers $n\ge8$. \qed \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$. \solution \mathpart{(a)} $$\eqalign{ f(1)&=f(0)+2=1+2=3,\cr f(2)&=f(1)+2=3+2=5,\cr f(3)&=f(2)+2=5+2=7,\cr f(4)&=f(3)+2=7+2=9.\cr }$$ \mathpart{(b)} $$\eqalign{ f(1)&=\bigl(f(0)+1)^2=(1+1)^2=2^2=4,\cr f(2)&=\bigl(f(1)+1)^2=(4+1)^2=5^2=25,\cr f(3)&=\bigl(f(2)+1)^2=(25+1)^2=26^2=676,\cr f(4)&=\bigl(f(3)+1)^2=(676+1)^2=677^2=458\,329.\cr }$$ \vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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)$. \solution \mathpart{(a)} $$\eqalign{ f(2)&=f(1)+3f(0)=2+3(-1)=-1,\cr f(3)&=f(2)+3f(1)=-1+3(2)=5,\cr f(4)&=f(3)+3f(2)=5+3(-1)=2,\cr f(5)&=f(4)+3f(3)=2+3(5)=17.\cr }$$ \mathpart{(b)} $$\eqalign{ f(2)&=f(0)/f(1)=(-1)/2=-\frac12,\cr f(3)&=f(1)/f(2)=2/(-\frac12)=-4,\cr f(4)&=f(2)/f(3)=(-\frac12)/(-4)=\frac18,\cr f(5)&=f(3)/f(4)=(-4)/(\frac18)=-32.\cr }$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bye