Chapter 1

Let \(U=\\{1,2,3,4,5,6,7,8,9,10\\}\) be a universal set. Let \(A, B, C \subseteq U\) such that \(A=\\{1,3,4,8\\}, B=(2,3,4,5,9,10),\) and \(C=\\{3,5,7,9,10\\},\) Use bit representations for \(A, B,\) and \(C\) together with UNION, INTER, DIFF, and COMP to find the bit representation for the following: (a) \(A \cup B\) (b) \(A \cap B \cap C\) (c) \((A \cup C) \cap B\) (d) \((A-B) \cup C\) (e) \(A \cap(B-(C \cap B))\) (f) \(A-(B-C)\) (g) \((A \cup B) \cup(C-B)\)

Find a rational number representing each of the following repeating decimals: (a) \(0.537537537537537537537537537 \ldots\) (b) \(31.25469696969696969696969 \ldots\)

A fixed dose of a given drug increases the concentration of that drug above normal levels in the bloodstream by an amount \(C_{0}\) (measured in percent). The effect of the drug wears off over time such that the concentration at some time \(t\) is \(C_{0} e^{-k t}\) where \(k\) is the known rate at which the concentration of the drug in the bloodstream declines. (a) Find the residual concentration \(R\), the accumulated amount of the drug above normal levels in the bloodstream, at time \(t\) after \(n\) doses given at intervals of \(t_{0}\) hours starting with the first dose at \(t=0\). (b) If the drug is alcohol and 1 oz. of alcohol has \(C_{0}=0.05 \%\), how often can a "dose" be taken so that the residual concentration is never more than \(0.15 \%\) ? Assume \(k=(1 / 3) \ln (2)\)

(a) Suppose you take out a mortgage for \(A\) dollars at a monthly interest rate \(I\) and a monthly payment \(P\). (To calculate \(I\) : if the annual interest rate is \(12 \%\), divide by 12 to get a monthly rate of \(1 \%,\) then replace the percentage with the decimal fraction 0.01.) Let \(A_{n}\) denote the amount you have left to pay off after \(n\) months. So, \(A_{0}=A\) by definition. At the end of each month, you are first charged interest on all the money you owed during the month, and then your payment is subtracted. So. $$A_{n+1}=A_{n}(1+I)-P$$ Prove by induction that $$A_{n}=\left(A-\frac{P}{I}\right)(1+I)^{n}+\frac{P}{I}$$ (b) Use this to calculate the monthly payment on a 30 -year loan of \(\$ 100,000\) at \(12 \%\) interest per year. (Note that the formula is inexact, since moncy is always rounded off to a whole number of cents. The derivation here does not do that. We use \(12 \%\) to make the arithmetic easier. You should consult a local bank to find a current value.)

For natural number exponents and nonzero bases, most of the familiar laws of exponents can be proved by induction on the exponents using the facts that \(b^{0}=1\) (for \(b \neq 0\) ) and \(b^{n+1}=b \cdot b^{n}\), Assuming that \(m\) and \(n\) are natural numbers and both \(r\) and \(s\) are nonzero real numbers, prove the following: (a) \(r^{m+n}=r^{m} \cdot r^{n}\) (b) \(r^{m n}=\left(r^{m}\right)^{n}\). (c) If \(r>1,\) then \(r^{m}>r^{n}\) if and only if \(m>n\). (d) If \(n, r, s>0,\) then \(r^{n}>s^{n}\) if and only if \(r>s\).

A common use of induction is to prove various facts that seem to be fairly obvious but are otherwise awkward or impossible to prove. These frequently involve expressions with ellipses. Use induction to show that: (a) \(X \cup\left(X_{1} \cap X_{2} \cap X_{3} \cap \cdots \cap X_{3}^{n}\right)=\left(X \cup X_{1}\right) \cap\left(X \cup X_{2}\right) \cap \cdots \cap\left(X \cup X_{n}\right)\) (b) \(X \cap\left(X_{1} \cup X_{2} \cup X_{3} \cup \ldots \cup X_{n}\right)=\left(X \cap X_{1}\right) \cup\left(X \cap X_{2}\right) \cup \ldots \cup\left(X \cap X_{n}\right)\) (c) \(\overline{\left(X_{1} \cap X_{2} \cap \cdots \cap X_{n}\right)}=\overline{X_{1}} \cup \overline{X_{2}} \cup \ldots \cup \overline{X_{n}}\) (d) \(\overline{\left(X_{1} \cup X_{2} \cup \ldots \cup X_{n}\right)}=\overline{X_{1}} \cap \overline{X_{2}} \cap \ldots \cap \overline{X_{n}}\)

Challenge: Exactly where is the mistake in the following proof that all personal computers are the same brand? Let \(\mathcal{T}=\\{n \in \mathbb{N}: n \geq 1\) and in every set of \(n\) personal computers, all the personal computers are the same brand \(\\} .\) Prove by induction that for every natural number \(n\) such that \(n \geq 1\) is in \(T\). (Base step) \(1 \in T\), since, trivially, if a set of personal computers contains only one computer, then every (one) computer in the set has the same brand. (Inductive step) Suppose \(n \in T\). We need to show \(n+1 \in T\). So, let \(P\) be any set of \(n+1\) personal computers. Pick any computer \(c \in P ;\) we need to show that every computer in \(P\) is the same brand as \(c\). So, let \(d\) be any computer in \(P\). If \(d=c\), then, trivially, \(d\) and \(c\) are the same brand. Otherwise, \(c \in P-(d\\} .\) The set \(P-(d)\) contains \(n\) computers, so by inductive hypothesis, all the computers in \(P-(d]\) are the same brand. Furthermore, \(d \in P-\mid c\\},\) and. also by inductive hypothesis, all the computers in \(P-\\{c\\}\) are the same brand. Now, let \(e\) be a computer in both \(P-\mid c\\}\) and \(P-[d\\}\). Then, \(d\) is the same brand as \(e,\) and \(c\) is the same brand as \(e\). Therefore, \(d\) is the same brand as \(c\).

Using the Principle of Mathematical Induction, prove each of the following different forms of the principle; (a) Induction with a possibly negative starting point: Suppose that \(S \subseteq \mathbb{Z}\), that some integer \(n_{0} \in S,\) and that for every \(n \in \mathbb{Z},\) if \(n \in S\) and \(n \geq n_{0},\) then \(n+1 \in S .\) Then, for every integer \(n \geq n_{0}\), we have \(n \in S\). (b) Induction downward: Suppose that \(S \subseteq \mathbb{Z}\), that some integer \(n_{0} \in S\), and that for every \(n \in \mathbb{Z},\) if \(n \in S\) and \(n \leq n_{0},\) then \(n-1 \in S .\) Then, for every integer \(n \leq n_{0}\) we have \(n \in S\) (c) Finite induction upward: Let \(n_{0}, n_{1} \in \mathbb{Z}, n_{0} \leq n_{1} .\) Suppose that \(S \subseteq \mathbb{Z}, n_{0} \in S\). and for every \(n \in \mathbb{Z},\) if \(n \in S, n \geq n_{0},\) and \(n