475 Spring 09 Homework

Contents

  1. What Is This?
  2. HW 9, Due Wed Apr 29, 23:59
  3. HW 8, Due Wed Apr 22, 23:59
  4. HW 7, Due Wed Apr 15, 23:59
  5. HW 6, Due Wed Mar 18, 23:59
  6. HW 5, Due Wed Mar 11, 23:59
  7. HW, Due Wed Mar 4, 23:59
  8. HW 4, Due Wed Feb 25, 23:59 (finalized Feb 20)
  9. HW 3, Due Wed Feb 18, 23:59
  10. HW 2, Due Wed Feb 11, 23:59
  11. HW 1, Due Wed Feb 4, 23:59

What Is This?

These are homeworks from the Math 475 class of Spring 2009. They should be submitted in typeset format over e-mail. Try them before Tuesday and ask questions then.

We also are going to turn in Big Problems, so if you are bored with the homework, go and check them out at 475 Spring 09 Big Problems.

HW 9, Due Wed Apr 29, 23:59

\begin{center} \textbf{Math 475 Homework 9}\\ \textsc{Due April 29th, 2009} \end{center} \begin{enumerate} \item Weve defined $e = \lim_{n \to \infty} (1 + \frac{1}{n})^n$. There is another famous series expression for $e$, which we can use to prove $e$ is irrational. \begin{enumerate} \item Write down the Taylor Series for the function $e^x$. (You can look it up. Ill assume you derived it in Calculus 2 and can prove it converges everywhere.) \item Write down an infinite series expression for $e$. \item Assuming $e$ is genuinely equal to the infinite series, prove $e$ is irrational. (Hint: if $e = p/q$, multiply through by $(q!)$. This should lead to an integer part plus something you can prove is less than 1.) \end{enumerate} \item Prove $\log_2 5$ is irrational. (Hint: what if it were equal to $p/q$…? ) \end{enumerate}
 • pdf
 • pdf tight
 • latex

HW 8, Due Wed Apr 22, 23:59

\begin{center} \textbf{Math 475 Homework 8} \\ \textsc{Due April 22nd, 2009} \end{center} \begin{enumerate} \item Find the triangular numbers in Pascals Triangle. Explain why the pattern continues forever. \item Identify the skew-diagonals of Pascals Triangle which sum to the Fibonacci numbers. Explain why this pattern continues forever. \item Use $n$th differences to prove the sum of every $n$th row of Pascals Triangle is $2^n$ (assuming the ``1 1 row is the first row). \item Describe every function $f:\mathbb{Z} \to \mathbb{R}$ that is equal to its own first difference function and prove there are no others. \end{enumerate}
 • pdf
 • pdf tight
 • latex

HW 7, Due Wed Apr 15, 23:59

\begin{center} \textbf{Math 475 Homework 7} \\ \textsc{Due April 15th, 2009} \end{center} \begin{enumerate} \item Find a quadratic function that models this data: \\[.1in] \begin{tabular}{c | c} IN & OUT \\ \hline 0 & -6 \\ 1 & -1 \\ 2 & -6 \\ 3 & -21 \\ 4 & -46 \\ 5 & -81 \\ \end{tabular} \item Prove that the first difference of an $N$th degree polynomial has at most degree $N-1$. \item Prove an $N$th degree polynomial has constant $N$th differences. (Hint: use the last answer.) \item The $n$th tetrahedral number is the sum of the first $n$ triangular numbers. (Its also the balls in first $n$ layers of a tetrahedral ball pyramid.) Find a closed formula for it using our analysis of functions and their first, second, third, etc. differences. \item Write me a formula for sums of cubes using our difference table analysis. \item Derive our class solution for $x^2 + Bx + C = 0$, then explain how you can solve ANY quadratic equation using this special case and derive the Quadratic Formula. \end{enumerate}
 • pdf
 • pdf tight
 • latex

HW 6, Due Wed Mar 18, 23:59

Reminder: Three Big Problems due by Spring Break.

There is a theorem called the Cantor-Schroeder-Bernstein Theorem which says that $A$ and $B$ have the same cardinality (by our class definition) if and only if there is a bijection between them. The theorem is annoyingly complicated to prove and not too edifying, so you can prove that to yourself on your own time. You are allowed to use that theorem for this problem set. \begin{enumerate} \item A set $S$ has $N$ distinct elements. How many distinct subsets are there? (Be sure to include $S$ and $\{ \}$.) Explain why your formula works. \item The power set of $S$, written $P(S)$, is the set of subsets of $S$. Prove that the cardinality of $P(S)$ is strictly larger than the cardinality of $S$ when $S$ is finite. \item Consider the power set of the rational numbers, $ P(\mathbb{Q})$. \begin{enumerate} \item Show that $\mathbb{R}$ fits into $P(\mathbb{Q})$. (Hint: Each real number corresponds in some natural way to a set of rational numbers.) \item Use the last fact, and our previously established uncountability of the reals, to give a proof that $P(\mathbb{Q})$ does not fit into $\mathbb{Q}$, and therefore $P(\mathbb{Q})$ has larger cardinality than $\mathbb{Q}$ \end{enumerate} \item Prove that for any set $S$, the cardinality of $P(S)$ is always larger than the cardinality of $S$. (Hint: Suppose there is a bijection $\phi: S \to P(S)$. By using the spirit of diagonalization, construct a subset of $S$ in $P(S)$ that cannot be in the image of $\phi$.) \item Compare the cardinalities of $\mathbb{C}$ and $\mathbb{R}$. Prove your answer. \end{enumerate}
 • pdf
 • pdf tight
 • latex

HW 5, Due Wed Mar 11, 23:59

\begin{enumerate} \item \textbf{Decimal Fractions}. \begin{enumerate} \item Prove that every rational number has either a terminating or repeating expansion. (Hint: long division.) \item In light of the last question, give me a clear way to generate an infinite decimal expansion that does not repeat, thus constructing an irrational number. Be sure I can tell how to generate each digit and also make an argument why it does not repeat. \item \label{series} Consider an infinite decimal expansion $0.d_1d_2d_3\dots$. Write it as a limit of a sequence of truncated (``cut-off) decimal representations. \item Prove that the sequence in the last question is Cauchy. (Reminder: a sequence ${a_n}$ is \emph{Cauchy} if for any $\epsilon>0$, there is a natural number $N$ such that if $m,n > N$, then $|a_m - a_n| < \epsilon$.) \item (dont turn in) Remind yourself what a completion of a metric space is, and convince yourself that the real numbers are the completion of the rational numbers. \item Write $0.999\dots$ as the limit of a sequence of terminating decimals. Prove that the limit of this sequence is $1$. Yes, youll have to use an $\epsilon-N$ argument. \end{enumerate} \item \textbf{Comparing Set Cardinalities}. Prove using the definition of ``same size and ``fits in in class that the following pairs of sets have the same size: \begin{enumerate} \item Prime numbers and whole numbers. \item Terminating decimals and repeating decimals (here you can count an infinitely repeating 0 as repeating). \end{enumerate} \end{enumerate}
 • pdf
 • pdf tight
 • latex

HW, Due Wed Mar 4, 23:59

HW 4, Due Wed Feb 25, 23:59 (finalized Feb 20)

\begin{enumerate} \item Fill in the missing digits. Prove that the solutions are unique. Assume the divisions have no remainders. \\ \includegraphics[width=2in]{../mult1.pdf} \includegraphics[width=2.5in]{../mult2.pdf}\\[.25in] \includegraphics[width=1.5in]{../div1.pdf} \includegraphics[width=2in]{../div2.pdf} \item \textbf{Royal Forks and Knives Problem}. The Queens pantry has one drawer that contains forks and knives. The Royal servants take some of them out to set the table for a Royal dinner. Every individual table setting has exactly one fork and one knife. The servants use 2/3 of the forks and 3/5 of the knives in the drawer. \begin{enumerate} \item Consider the fraction of the total number of knives and forks that are being used for the Royal dinner. How many different fractions are possible?
 \item Find a formula that tells you the fraction in use if you know the fraction of forks in use and fraction of knives in use? \end{enumerate} \item Constructively prove that between any two distinct fractions there is another fraction. That is, I want a formula for such a fraction given the surrounding fractions. \item \begin{enumerate} \item \label{samedenominator} Write a formula for subtracting fractions of the same denominator and justify it using our part-whole definition of fraction. \item Derive a general formula for subtraction of fractions using our golden rule of equivalence and (\ref{samedenominator}). \end{enumerate} \end{enumerate}
 • pdf
 • pdf tight
 • latex and fig 1, fig 2, fig 3, fig 4

HW 3, Due Wed Feb 18, 23:59

\begin{enumerate} \item (\textbf{do, but dont turn in}) Consider this model of the integers. Every integer is an IOU, either a credit or debt in dollars. So $20$ means we are owed \$20 (a \$20 credit), and $-20$ means we owe \$20 (a \$20 debt). Addition means putting together and subtracting something means to remove it. Explain in words using this model what is a reasonable value for: \begin{enumerate} \item 20 + (-20) \item 20 - (-20) \item (-20) + (-20) \item -20 + 0 \end{enumerate} \item (\textbf{do, but dont turn in except for (\ref{minustimesminusiou})}). Modeling multiplication is more complex. Lets model $M \times N$ as follows. For a positive $N$, we say its getting $N$ IOUs each worth $\$M$. For a negative $N$, we say its losing $N$ IOUs each worth $\$M$. Explain in words using this model what is a reasonable value for: \begin{enumerate} \item $20 \times 1$ \item $1 \times 20$ \item $20 \times 0$ \item $0 \times 20$ \item $20 \times -3$ \item $(20 \times 3) + (20 \times (-3))$ \item $-20 \times 3$ \item $-20 \times -1$ \item \label{minustimesminusiou}\textbf{(turn in)} $-20 \times -3$ \end{enumerate} \item \textbf{Defining the Integers from the Natural Numbers: Addition}. Suppose we have constructed the natural numbers to our satisfaction along with a binary addition operation. Note there is no ``subtraction operation or ``opposite operation yet, so this is an approach independent from the ``opposite adjoining in the last homework. Here we will use what is called the \emph{Grothendieck Construction}. This is a very general construction which actually applies to any structure with a commutative, associative binary operation and an identity element. It takes such a structure and embeds it in a larger structure that extends the operation so that every element now has an inverse (i.e. embeds it in an abelian group). The set of natural numbers fits these preconditions, and well discuss this specific case, but this exact argument works for many other sets. One defines new numbers of the form ``$a - b$ where $a$ and $b$ are natural numbers. It is tempting to just see ``3-2 as ``1 because of habit, but were not assuming we know anything about subtraction yet. So for now we just regard ``$a-b$ as an ordered pair written with panache. And yet $3-2$ really ought to be the same as $7-6$. Thus, we declare ``$a-b$ to be equivalent to ``$c-d$ if and only if $a+d=b+c$ (notice how we only use addition in the definition). We write this $a-b \sim c-d$ In fact, this is a genuine equivalence relation, so each ordered pair is really an equivalence class of expressions ``$a - b$. These ordered pairs are called the integers and the natural numbers are embedded in the integers as the classes ``$a - 0$. \begin{enumerate} \item (Do, dont turn in) Prove to yourself that the relation defined above is really an equivalence relation. \item What is the natural way to define an addition on these objects? I.e. $(a - b) + (c - d) = ?$, where your answer is another difference pair. \item Verify that your addition is well-defined. That is, if $(a-b) \sim (a-b)$ and $(c-d) \sim (c-d)$ then $(a - b) + (c - d) \sim (a - b) + (c - d)$. \item What is the additive identity? Prove it. \item What is the opposite of $(a-b)$? Prove it. \item Give a clean description of the set of negative numbers (the opposites of the natural numbers)? % Addition is what youd expect: $(a - b) + (c - d) = (a+c - (b+d) )$. \end{enumerate} \item \textbf{Defining the Integers from the Natural Numbers: Multiplication}. Once the integers are constructed with an addition, its natural to want to extend multiplication. \begin{enumerate} \item What is the natural way to define multiplication on pairs of integers? I.e. $(a - b)(c - d) = ?$. \item Check that your multiplication is well-defined, that is if $(a-b) \sim (a-b)$ then $(a-b)(c-d) \sim (a-b)(c-d)$. Technically you should also check that $(a-b)(c-d) \sim (a-b)(c-d)$ but I dont need to see that (similar) calculation. \item Prove that this new integer multiplication is commutative assuming natural number multiplication is commutative. \item Check that $0$ times anything is $0$. \item Check that two negative numbers multiply to a positive product. \end{enumerate} % (ac + bd - (bc + ad))$. One does need to check that these operations are well-defined in that they do not depend on the choice of representative for the equivalence class. Details are available in your local abstract algebra text. % % Given this definition, the product of two negative numbers $(0 - b)(0 - d)$, where $b$, $d$ are (nonzero) natural numbers, is $(0 + bd - (0 + 0)) = (bd - 0)$, which is the natural number $bd$. Thus, the product of two negative numbers is positive. \item (dont turn in) Divide 128 by 7 using relaxed repeated subtraction. \item Explain why in class we called our long division algorithm abbreviated uptight repeated subtraction. Explain this using the example of 128 divided by 7. \item Describe 128 divided by 7 using \begin{enumerate} \item a partitive model (sharing) \item a measurement model (taking out bundles) \end{enumerate} \item Henry spends 3/14 of his monthly income for rent and 2/11 of what is left on food. If he has \$540 left, what is his monthly income ? (Hint: Pictures really help). \end{enumerate}


 • pdf
 • pdf tight
 • latex

HW 2, Due Wed Feb 11, 23:59

\begin{enumerate} \item (dont turn in) Symbolically check that American, European, Make It Nice and Negative Numbers methods work in base 4 using $311_4 - 112_4$ as an example. \item (dont turn in) Demonstrate \textbf{why} Lattice Multiplication works using the example $78 \times 23$. \item \textbf{French Hand Multiplication}. In Butterworths \emph{What Counts}, p.205, he writes: \emph{To this day [about 1930], the peasant of central France (Auvergne) uses a curious method for multiplying numbers above 5. If he wished to multiply $9 \times 8$ he bends down 4 fingers on his left hand (4 being the excess of 9 over 5) and 3 fingers on his right hand ($8-5=3$) . Then the number of bent-down fingers gives him the tens of the result ($4+3=7$) while the product of the unbent fingers gives him the units ($1 \times 2=2$).} Does this method work for multiplying any two numbers between 6 and 9? Justify why, or give a counter-example. \item \textbf{Doubling/Halving Multiplication}. I showed you in class how to multiply two numbers $A \times B$, by making two columns. In the first column, halve A (discarding the remainder), the next column, double B. Go to the next line and repeat the process. Stop when you halve A down to 1. Then you circle each line with an odd A. Add up all the numbers in the B column. Demonstrate why this works. \item Take the natural numbers as the set we know and love equipped with addition and multiplication (and for simplicity, we count 0 as a natural number). For each natural number $A$ let us define a new mysterious opposite number, $-A$, with the property $A + (-A) = 0 = (-A) + A $, i.e. $-A$ is an additive inverse of $A$. The union of the naturals and all their opposites well now call the integers. The nonzero natural numbers are called positive integers, and their opposites, negative integers. \begin{itemize} \item Prove from the definition that the opposite of $(-X)$ is $X$ (or that ``minuses cancel) and therefore every integer has an opposite. \end{itemize} \item We would like to extend addition and multiplication to these new opposites in a way that extends essential properties of natural number arithmetic. We ask that \begin{itemize} \item they obey the distributive law \item addition and multiplication are associative and commutative \item $0$ is an additive identity \item $1$ is a multiplicative identity \end{itemize} It can be checked that the integers can be assigned these properties in a way that doesnt lead to contradictions. You can now deduce a lot about the integers using \textbf{only these basic properties}. \begin{enumerate} % \setcounter{enumii}{b} \item Prove that $0$ is the unique additive identity (i.e. prove that any additive identity has to equal $0$). \item Prove that every integer has a unique opposite. \item Prove zero times anything is zero. \item Prove the product of $-A$ and $-B$ is $AB$ and therefore ``negative times negative is positive. (Hint: The slickest way I know proves first that $(-A)(-B)$ and $(A)(-B)$ are opposites, then that $(A)(-B)$ and $AB$ are opposites, then wraps things up.) \end{enumerate} \end{enumerate}

 • pdf
 • pdf tight
 • latex

HW 1, Due Wed Feb 4, 23:59

\begin{enumerate} \item Select from the following list of values two or three that are most important to you: Athletic ability, being good at art, creativity, independence, living in the moment, membership in a social group (such as your community, racial group, or school club), music, politics, relationships with friends or family, religious values, and sense of humor. \begin{itemize} \item Write about one or more times in your life when these values were important to you. Write a few sentences about why they were important to you. \end{itemize} \item Write a complete characterization of the numbers that can be written as the difference of two squared integers. You need to precisely name the set and prove that the set really is exactly all such differences. \item Weve dealt with base 10 and base 4 arithmetic. Now imagine a number system that is base $2i$, where $i$ is the square root of $-1$, and only uses the symbols $0, 1, 2, 3$ (in that order) and a decimal point (strictly speaking, it should be called a radix point in non-base-10). \begin{enumerate} \item Translate the following numbers, written base $2i$, into base 10: \[10, 100, 101, 102, 103, 200, 201, 202, 203, 1000, 0.1\] \item Translate the following numbers, written base $10$, into base $2i$: \[3, 5, 10, 20, -3, -\frac{1}{2}i, -0.25, -\frac{3}{16} \] \item Explain how to write every natural number in base $2i$. \item Explain how to write every imaginary natural number (every natural number times $i$) in base $2i$. \item Which rational numbers can you write with terminating ``decimals, base $2i$? \item Which numbers can you write if you allow infinite ``decimals? Try to get a complete characterization. Prove it as best as you can. \end{enumerate} \end{enumerate}
 • pdf
 • pdf tight
 • latex