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
Math 475 Homework 9\\
\textsc{Due April 29th, 2009}
We've 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.
Write down the Taylor Series for the function $e^x$. (You can look it up. I'll assume you derived it in Calculus 2 and can prove it converges everywhere.)
Write down an infinite series expression for $e$.
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.)
Prove $\log_2 5$ is irrational. (Hint: what if it were equal to $p/q$� )
HW 8, Due Wed Apr 22, 23:59
Math 475 Homework 8 \\
\textsc{Due April 22nd, 2009}
Find the triangular numbers in Pascal's Triangle. Explain why the pattern continues forever.
Identify the skew-diagonals of Pascal's Triangle which sum to the Fibonacci numbers. Explain why this pattern continues forever.
Use $n$th differences to prove the sum of every $n$th row of Pascal's Triangle is $2^n$ (assuming the ``1 1" row is the first row).
Describe every function $f:\mathbb{Z} \to \mathbb{R}$ that is equal to its own first difference function and prove there are no others.
HW 7, Due Wed Apr 15, 23:59
Math 475 Homework 7 \\
\textsc{Due April 15th, 2009}
Find a quadratic function that models this data:
IN
OUT
0
-6
1
-1
2
-6
3
-21
4
-46
5
-81
Prove that the first difference of an $N$th degree polynomial has at most degree $N-1$.
Prove an $N$th degree polynomial has constant $N$th differences. (Hint: use the last answer.)
The $n$th tetrahedral number is the sum of the first $n$ triangular numbers. (It's 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.
Write me a formula for sums of cubes using our difference table analysis.
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.
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.
A set $S$ has $N$ distinct elements. How many distinct subsets are there? (Be sure to include $S$ and $\{ \}$.) Explain why your formula works.
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.
Consider the power set of the rational numbers, $ P(\mathbb{Q})$.
Show that $\mathbb{R}$ fits into $P(\mathbb{Q})$. (Hint: Each real number corresponds in some natural way to a set of rational numbers.)
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}$
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$.)
Compare the cardinalities of $\mathbb{C}$ and $\mathbb{R}$. Prove your answer.
HW 5, Due Wed Mar 11, 23:59
Decimal Fractions.
Prove that every rational number has either a terminating or repeating expansion. (Hint: long division.)
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.
\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.
Prove that the sequence in the last question is Cauchy. (Reminder: a sequence ${a_n}$ is Cauchy if for any $\epsilon>0$, there is a natural number $N$ such that if $m,n > N$, then $|a_m - a_n| < \epsilon$.)
(don't 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.
Write $0.999\dots$ as the limit of a sequence of terminating decimals. Prove that the limit of this sequence is $1$. Yes, you'll have to use an $\epsilon-N$ argument.
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:
Prime numbers and whole numbers.
Terminating decimals and repeating decimals (here you can count an infinitely repeating 0 as repeating).
HW, Due Wed Mar 4, 23:59
Work on some big problems. I want you to turn in 3 of them before Fri Mar 20, 23:59 (before Spring Break).
(do but don’t turn in) You should also explain why $$ 3 \div 7 = 3/7 $$, using our definition of three-sevenths and each of the three different models of division: partitive (sharing), measurement, missing factor.
(do, but don’t turn in) Multiplying Improper Fractions. Draw a picture of $$ 4 \frac{1}{2} \times 2 \frac{1}{3} $$ using an area model. Separate the whole number parts from the fraction parts and find a tidy algorithm for multiplying improper fractions. Explain in words what your algorithm is.
HW 4, Due Wed Feb 25, 23:59 (finalized Feb 20)
Fill in the missing digits. Prove that the solutions are unique. Assume the divisions have no remainders. \\
Royal Forks and Knives Problem. The Queen's 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.
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?â¨
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?
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.
\label{samedenominator} Write a formula for subtracting fractions of the same denominator and justify it using our part-whole definition of fraction.
Derive a general formula for subtraction of fractions using our golden rule of equivalence and (\ref{samedenominator}).
HW 3, Due Wed Feb 18, 23:59
(do, but don't 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:
20 + (-20)
20 - (-20)
(-20) + (-20)
-20 + 0
(do, but don't turn in except for (\ref{minustimesminusiou)}). Modeling multiplication is more complex. Let's model $M \times N$ as follows. For a positive $N$, we say it's getting $N$ IOUs each worth $\$M$. For a negative $N$, we say it's losing $N$ IOUs each worth $\$M$. Explain in words using this model what is a reasonable value for:
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 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 we'll 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 we're 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$".
(Do, don't turn in) Prove to yourself that the relation defined above is really an equivalence relation.
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.
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')$.
What is the additive identity? Prove it.
What is the opposite of $(a-b)$? Prove it.
Give a clean description of the set of negative numbers (the opposites of the natural numbers)?
% Addition is what you'd expect: $(a - b) + (c - d) = (a+c - (b+d) )$.
Defining the Integers from the Natural Numbers: Multiplication. Once the integers are constructed with an addition, it's natural to want to extend multiplication.
What is the natural way to define multiplication on pairs of integers? I.e. $(a - b)(c - d) = ?$.
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 don't need to see that (similar) calculation.
Prove that this new integer multiplication is commutative assuming natural number multiplication is commutative.
Check that $0$ times anything is $0$.
Check that two negative numbers multiply to a positive product.
% (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.
(don't turn in) Divide 128 by 7 using relaxed repeated subtraction.
Explain why in class we called our long division algorithm abbreviated uptight repeated subtraction. Explain this using the example of 128 divided by 7.
Describe 128 divided by 7 using
a partitive model (sharing)
a measurement model (taking out bundles)
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).
HW 2, Due Wed Feb 11, 23:59
(don't 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.
(don't turn in) Demonstrate why Lattice Multiplication works using the example $78 \times 23$.
French Hand Multiplication. In Butterworth's What Counts, p.205, he writes:
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.
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.
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 we'll now call the integers. The nonzero natural numbers are called positive integers, and their opposites, negative integers.
\begin{itemize}
Prove from the definition that the opposite of $(-X)$ is $X$ (or that ``minuses cancel'') and therefore every integer has an opposite.
\end{itemize}
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}
they obey the distributive law
addition and multiplication are associative and commutative
$0$ is an additive identity
$1$ is a multiplicative identity
\end{itemize}
It can be checked that the integers can be assigned these properties in a way that doesn't lead to contradictions. You can now deduce a lot about the integers using only these basic properties.
% \setcounter{enumii}{b}
Prove that $0$ is the unique additive identity (i.e. prove that any additive identity has to equal $0$).
Prove that every integer has a unique opposite.
Prove zero times anything is zero.
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.)
HW 1, Due Wed Feb 4, 23:59
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}
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}
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.
We've 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).
Translate the following numbers, written base $2i$, into base 10: \[10, 100, 101, 102, 103, 200, 201, 202, 203, 1000, 0.1\]
Translate the following numbers, written base $10$, into base $2i$: \[3, 5, 10, 20, -3, -\frac{1}{2}i, -0.25, -\frac{3}{16} \]
Explain how to write every natural number in base $2i$.
Explain how to write every imaginary natural number (every natural number times $i$) in base $2i$.
Which rational numbers can you write with terminating ``decimals'', base $2i$?
Which numbers can you write if you allow infinite ``decimals''? Try to get a complete characterization. Prove it as best as you can.