The point of this homework is to give you practice proving basic facts in arithmetic (ones that you all know), but only using the barest of assumptions while doing so. This promotes economy of expression and forces you to be very clear about the concepts involved.

Here are some common letters we use to represent number systems:

• \(\nums = \{0,1,2,\ldots \}\) is the set of natural numbers. Notice that this set includes zero.
• \(\ints = \{\ldots ,-2,-1,0,1,2,\ldots \}\) is the set of integers.
• \(\rats = \{ a/b \mid a,b \in \ints \text{ and } b \ne 0 \}\) is the set of rational numbers.
• \(\reals \) is the set of real numbers.

We have \(\nums \subseteq \ints \subseteq \rats \subseteq \reals \). Note that we include zero as the first natural number. Other people start the natural numbers with one instead.

Exercises

1.

Using just Definition 0.1 above and elementary facts about arithmetic, prove directly that for integers \(a\) and \(b\), if at least one of them is even, then \(ab\) is even.

2.

With the same assumptions as in the previous exercise, prove directly that if \(a\) and \(b\) are even, then \(a+b\) and \(-a\) are even.

3.

With the same assumptions as in the previous exercise, prove by contradiction that if \(a\) is even and \(b\) is odd, then \(a+b\) is odd. That is, assume that \(a\) is even and \(b\) is odd, but that \(a+b\) is even; then derive a contradiction. (The only fact you can use about a number being odd is that it is not even. For example, don’t use the fact (not proven yet) that any odd number is of the form \(2k+1\) for some integer \(k\).)

4.

Now using the fact that all odd integers are of the form \(2k+1\) where \(k\in \ints \), prove directly that the sum of two odd integers is even.

5.

Prove the following facts hold for all natural numbers \(n\) by using induction.

• \(\sum \limits _{i=1}^n i = \dfrac{n(n+1)}{2}\)
• \(\sum \limits _{i=1}^n i^3 = \frac{1}{4}(n^4 + 2n^3 + n^2) = \dfrac{n^2{(n+1)}^2}{4}\)

6.

What is the largest integer that cannot be expressed as a sum of \(4\)’s and \(7\)’s? That is, find the largest integer \(n\) such that \(n \ne 4k+7\ell \) for any integers \(k,\ell \ge 0\). Prove your answer. (Your proof should use induction.)

7.

The associative law (for real multiplication) states that, for any \(a,b,c\in \reals \), we have \((ab)c = a(bc)\). Using just this law (repeatedly), prove that \(((ab)c)d = a(b(cd))\) for any \(a,b,c,d\in \reals \). To avoid ambiguity, you should fully parenthesize all your expressions. A string of equalities is a valid method of proof.