Homework 7

tex

School

Texas A&M University *

*We aren’t endorsed by this school

Course

222

Subject

Computer Science

Date

Feb 20, 2024

Type

tex

Pages

Uploaded by PrivateSteelKomodoDragon37

% Comment lines start with % % LaTeX commands start with \ % This template was provided by Jennifer Welch for CSCE 222-200, Honors, Spring 2015 \documentclass[12pt]{article} % This is an article with font size 12-point % Packages add features \usepackage{times} % font choice \usepackage{amsmath} % American Mathematical Association math formatting \usepackage{amsthm} % nice formatting of theorems \usepackage{amssymb} % provides some symbols \usepackage{latexsym} % provides some more symbols \usepackage{fullpage} % uses most of the page (1-inch margins) \usepackage{enumitem} \usepackage{hyperref} \setlength{\parskip}{.1in} % increase the space between paragraphs \renewcommand{\baselinestretch}{1.1} % increase the space between lines % Convenient renaming of symbols for logic formulas \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMPLIES}{\rightarrow} \newcommand{\IFF}{\leftrightarrow} \providecommand{\myceil}[1]{$\left \lceil #1 \right \rceil$} \providecommand{\myfloor}[1]{$\left \lfloor #1 \right \rfloor$} \newcommand{\powerset}[1]{\mathbb{P}(#1)} % Actual content starts here. \begin{document} \begin{center} % center all the material between begin and end {\large % use larger font CSCE 222 (Carlisle), Discrete Structures for Computing \\ % \\ is line break Spring 2022 \\ Homework 7} \end{center} \rule{6in}{.1pt} % horizontal line 6 inches long and .1 point high \begin{center} {\large Type your name below the pledge to sign\\ On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work.\\ **HUY QUANG LAI**} \end{center} % blank line separates paragraphs. First line of a paragraph is automatically % indented. \rule{6in}{.1pt} % horizontal line 6 inches long and .1 point high \noindent % don't indent {\bf Instructions:} % \bf makes text boldface % \em makes text emphasized (italics)

\begin{itemize} % makes an itemized list \item The exercises are from the textbook. You are encouraged to work extra problems to aid in your learning; remember, the solutions to the odd-numbered problems are in the back of the book. \item Grading will be based on correctness, clarity, and whether your solution is of the appropriate length. \item Always justify your answers. \item Don't forget to acknowledge all sources of assistance in the section below, and write up your solutions on your own. \item {\em Turn in .pdf file to Gradescope by the start of class on Monday, March 7, 2022.} It is simpler to put each problem on its own page using the LaTeX clearpage command. \end{itemize} \rule{6in}{.1pt} % horizontal line 6 inches long and .1 point high {\bf Help Received:} % \bf makes text boldface \begin{itemize} \item Rosen, Kenneth H. \emph{Discrete Mathematics and Its Applications}. McGraw- Hill, 2019. \end{itemize} \rule{6in}{.1pt} % horizontal line 6 inches long and .1 point high %--------------------------------------------------------------------- % \subsection makes a subsection heading; * leaves it unnumbered. % (Usually subsections are inside sections, but the \section command % used a font that was larger than I wanted.) \subsection*{Exercises for Section 5.1:} \noindent{\bf{6: (2 point).}} \noindent{Prove that $1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1$ whenever $n$ is a non-negative integer.} \noindent{\textit{Basis Step}:} \noindent\\ $P(n)=n\cdot n!$\\ $P(0)=0$\\ $(0+1)!-1=1-1=0$\\ $n\cdot n!=(n+1)!-1$ when $n=0$ \noindent{\textit{Induction Hypothesis}:} \noindent\\ $\displaystyle\sum_{i=0}^{n}(n\cdot n!)=(n+1)!-1$ \noindent{\textit{Induction Step}:} \noindent\\ $\displaystyle\sum_{i=0}^{n+1}(n\cdot n!)$\\ $\displaystyle=\sum_{i=0}^{n}(n\cdot n!)+(n+1)(n+1)!$\\ $=(n+1)!-1+(n+1)(n+1)!$\\ $=(n+1)!(1-1+(n+1))$\\ $=(n+1)(n+1)!$ \clearpage

\noindent{\bf{18(a-f): (3 points).}}\\ Let $P(n)$ be the statement that $n!<n^n$, where $n$ is an integer greater than 1. \begin{enumerate} \item What is the statement $P(2)$?\\ $P(2)\equiv2!<2^2$ \item Show that $P(2)$ is true, completing the basis step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1.\\ $2<4$\\ $P(2)\equiv$ True \item What is the inductive hypothesis of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1?\\ Let $P(k)$ be True for $k\geq2$.\\ $k!<k^k$ \item What do you need to prove in the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1?\\ Prove that $P(k+1)$ is also True.\\ $(k+1)!<(k+1)^{k+1}$ \item Complete the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1.\\ $(k+1)!=(k+1)k$\\ $(k+1)k!<(k+1)^k<(k+1)(k+1)^k$\\ $(k+1)(k+1)^k=(k+1)^{k+1}$\\ Therefore, $(k+1)!<(k+1)^{k+1}$ \item Explain why these steps show that this inequality is true whenever $n$ is an integer greater than 1.\\ Since we have completed the base and inductive steps, by the principle of mathematical induction, the inequality is true for any $n\geq2$. If we had shown $P(3)$ as our basis step, then the inequality would only be proven for $n\geq3$. \end{enumerate} \clearpage \noindent{\bf 32:{(3 points).}}\\ Prove that 3 divides $n^3+2n$ whenever $n$ is a positive integer. \noindent{\emph{Base Case}:}\\ If $n=1$, $1^3+2(1)=3$. So it is divisible by 3. \noindent{\emph{Inductive Step}:}\\ $(n+1)^3+2(n+1)$\\ $=n^3+3n^2+3n+1+2n+2$\\ $=(n^3+2n)+(3n^2+3n+3)$\\ $=(n^3+2n)+3(n^2+n+1)$ \noindent{$3(n^2+n+1)$ is divisible by 3.}\\ Therefore, $n^3+2n$ is divisible by 3 whenever $n$ is a positive integer. \clearpage \subsection*{Exercises for Section 5.2:} \noindent{\bf{6(a-c): (3 points)}} \begin{enumerate} \item Determine which amounts of postage can be formed using just 3-cent and 10-cent stamps.\\ We can form the following amounts of postage as indicated:\\

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

$3=3,6=3+3,9=3+3+3,10=10,12=3+3+3+3,13=10+3,$\\ $15=3+3+3+3+3,16=10+3+3,18=3+3+3+3+3+3,19=10+3+3+3,20=10+10$.\\ By having considered all the combinations, we know that the gaps in this list cannot be filled. We claim that we can form all amounts of postage greater than or equal to 18 cents using just 3-cent and 10-cent stamps. \item Prove your answer to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step. \noindent Let $P(n)$ be the statement that we can form $n$ cents of postage using just 3- cent and 10-cent stamps.\\ We want to prove that $P(n)$ is true for all $n\geq18$.\\ The basis step, $n=18$, is handled above. ($18=3+3+3+3+3+3$) \noindent{The Inductive Hypothesis}\\ Assume that we can form $k$ cents of postage.\\ Show how to form $k+1$ cents of postage. \noindent{The Inductive Step}\\ If the $k$ cents included two 10-cent stamps, then replace them by seven 3-cent stamps $(7\cdot3=2\cdot10+1$).\\ Otherwise, $k$ cents was formed either from just 3-cent stamps, or from one 10- cent stamp and $k-10$ cents in 3-cent stamps.\\ Because $k\geq18$, there must be at least three 3-cent stamps involved in either case. Replace three 3-cent stamps by one 10-cent stamp, and we have formed $k+1$ cents in postage ($10=3\cdot3+1$). \clearpage \item Prove your answer to (a) using strong induction. How does the inductive hypothesis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction? \noindent{$P(n)$} is the same as in part (b).\\ To prove that $P(n)$ is true for all $n\geq18$, we note for the basis step that from part (a), $P(n)$ is true for $n=18,19,20$.\\ Assume the inductive hypothesis, that $P(j)$ is true for all $j$ with $18\leq j\leq k$, where $k\geq20$\\ We want to show that $P(k+1)$ is true.\\ Because $k-2\geq18$, we know that $P(k-2)$ is true.\\ Put one more 3-cent stamp on the envelope, and we have formed $k+1$ cents of postage, as desired. \end{enumerate} \clearpage \noindent{\bf{10: (3 points)}}\\ \noindent{Assume that a chocolate bar consists of $n$ squares arranged in a rectangular pattern. The entire bar, or any smaller rectangular piece of the bar, can be broken along a vertical or a horizontal line separating the squares. Assuming that only one piece can be broken at a time, determine how many breaks you must successively make to break the bar into $n$ separate squares. Use strong induction to prove your answer.} \noindent{Let} $P(n)$ be the statement ``A chocolate bar can be broken in $n-1$ breaks''. \noindent{\textit{Basis Step}:} $n=1$\\ Consider a chocolate bar that consists of 1 square.\\

The chocolate bar is then already completely broken into pieces and thus requires $0=1-1=n-1$ breaks to completely break the chocolate bar.\\ Therefore, $P(1)$ is true. \noindent{\textit{Inductive Step}:}\\ Assume that $P(1),P(2),\cdots,P(k)$ are all true, such that the chocolate bar consisting of $i$ squares requires $i$ breaks, where $1\leq i\leq k$. \noindent From this, prove that $P(k+1)$ is true.\\ Consider a chocolate bar with $k+1$ squares.\\ Let $m$ and $q$ be positive integers such that $k+1=mg$ and such that the squares of the chocolate bar form a rectangle with $m$ rows and $q$ columns.\\ Let the first break be breaking off the last column of the rectangle.\\ Then divide the chocolate bar in a $(m-1)\times q$ rectangle and in a $1\times q$ rectangle.\\ Since $P((m-1)q)$ is true, we require $(m-1)g-1$ breaks to break the $(m-1)\times q$ rectangle.\\ Since $P(q)$ is true, we require $q-1$ breaks to break the $1\times q$ rectangle.\\ The chocolate bar require $(m-1)q-1+(q-1)+1$ breaks to complete break the chocolate bar consisting of $k+1$ squares. \noindent $(m-1)q-1+(q-1)+1=mq-q-1+q-1+1=mq-1$\\ From this, $(k+1)-1$ breaks to is required to break a chocolate bar with $k+1$ squares and thus $P(k+1)$ is true. \noindent By the principle of strong induction, $P(n)$ is true for all positive integers $n$. The chocolate bar requires $n-1$ breaks to break. \clearpage \noindent{\bf{12: (3 points)}}\\ \noindent{Use strong induction to show that every positive integer can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers $2^0=1,2^1=2,2^2=4$, and so on. [Hint: For the inductive step, separately consider the case where $k+1$ is even and where it is odd. When it is even, note that $\ displaystyle\frac{k+1}{2}$ is an integer.]} \noindent{\textit{Base Case}:}\\ For $n=1$, we can write $1=2^0$. \noindent{\textit{Inductive Step}:}\\ Suppose that for $1\leq k\leq n$ we can write $k$ as a sum of distinct powers of 2.\\ We want to show that $n+1$ can be written as a sum of distinct powers of two. \noindent{If} $n+1$ is even, then $\displaystyle\frac{n+1}{2}$ is an integer, and $\displaystyle1\leq \frac{n+1}{2}\leq n$, so by the inductive hypothesis we can write $\displaystyle\frac{n+1}{2}=2^{a_1}+2^{a_2}+\cdots+2^{a_j}$, where $a_1,\ cdots,a_j$ are all distinct.\\ Multiplying both sides by 2, $n+1=2\times(2^{a_1}+2^{a_2}+\ cdots+2^{a_j})=2^{a_1+1}+2{a_2+1}+\cdots+2^{a_j+1}$.\\ Because $a_1,a_2,\cdots,a_j$ were distinct, $a_1+1,a_2+1,\cdots,a_j+1$ are distinct. \noindent{If} $n+1$ is odd, then by by inductive hypothesis we can write $n=2^{a_1}+...+2^{a_j}$, where $a_1,\cdots,a_j$ are distinct powers.\\ Taking both sides mod 2, all non-zero powers of 2 drop out on the right hand side, and the left hand side is 0 (because n is even).\\

Because of this, $0\not\in{a_1,a_2,\cdots a_j}$.\\ From this, $n+1=2^0+2^{a_1}+2^{a_2}+\cdots+2^{a_j}$. \noindent{\bf{32: (3 points)}}\\ \noindent{Find the flaw with the following ``proof” that every postage of three cents or more can be formed using just 3-cent and 4-cent stamps.} \noindent{\emph{Basis Step}: We can form postage of three cents with a single 3- cent stamp and we can form postage of four cents using a single 4-cent stamp.} \noindent{\emph{Inductive Step}: Assume that we can form postage of $j$ cents for all non-negative integers $j$ with $j\leq k$ using just 3-cent and 4-cent stamps. We can then form postage of $k+1$ cents by replacing one 3-cent stamp with a 4-cent stamp or by replacing two 4-cent stamps by three 3-cent stamps.} \noindent Forming a 5-cent stamp would be impossible with only 3 and 4-cent stamps. Because of this, the Basis Step would be incorrect. \end{document}

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Homework 7

Related Documents