MAT 157: Assignment 2
Summary. This week is dedicated to the natural numbers, 1, 2, 3, . . .. The set of natural numbers N
is characterized by the properties that
1. 1 is in N;
2. each n in N has a (unique) successor (denoted n + 1) in N;
3. n + 1 = m + 1 only if m = n;
4. 1 is not the successor of any natural number;
5. the principle of induction: If a set A of natural numbers satisfies
• 1 lies in A, and
• n + 1 lies in A whenever n lies in A,
then A contains all natural numbers, i.e., A = N.
From these properties, addition, multiplication, and the order on N can be constructed recursively (see
Spivak, Problem 2.24). Furthermore, the integers can be constructed as differences m − n of natural
numbers, and the rationals as quotients p/q. In this course, we will not consider these constructions
in detail (they are complicated by the fact that the representations of a number as a difference or as a
quotient of integers are not unique: m − n = (m + k) − (n + k) and p/q = (k · p)/(k · q) for every
natural number k). We will discuss much later in the course how to construct R from Q.
The multiplication of natural numbers turns out to be much more interesting than their addition:
Every natural number has a unique decomposition as a product of its prime factors. Moreover, there
is an infinite sequence of primes (starting with 2, 3, 5, 7, 11, 17, 19, . . .). These facts were known to
Euclid around 2400 years ago, but prime numbers are still a principal target of research in Number
Theory today.
A useful algebraic tool for working with natural numbers is modular arithmetic. We say that two
integers n, n0 are congruent modulo m (and write n ≡ n0 mod m) if n − n0 is an integer multiple of
m. In particular, (
0 mod 2 if n is even,
n ≡
1 mod 2 if n is odd.
Addition and multiplication are well-defined modulo m: If a ≡ a0 mod m and b ≡ b0 mod m, then also
(a + b) ≡ (a0 + b0 ) mod m and also a · b ≡ a0 · b0 mod m. When p is a prime number, then addition and
multiplication mod p satisfy Properties P1-P9 from Chapter 1 — the equivalence classes form a finite
field, known as Fp . These fields cannot be ordered (see Spivak Problem 1.25).
We have also introduced two important combinatorial objects: The factorial n! = 1 · · · n, which
counts the number of permutations of 1, . . . , n, and the binomial coefficient nk = k! (n−k)!
n!
, which
counts the number of k-element subsets of {1, . . . , n}.
Read Section 2.
For further practice: Spivak Problems 1, 2, 5, 9, 11, 12, 21, 22 Part bc, 23, 24 (all in Chapter 2).
1
Hand-in (due Thursday, September 19):
1. Bernoulli’s inequality (Spivak, Problem 2.19). Prove that
(1 + h)n ≥ 1 + nh , n = 1, 2, . . .
for all real h with h > −1.
2. (Spivak Problem 2.8) Prove every natural number is either even, or odd. (Instruction: Proceed
directly from the definition and use induction. Do not appeal to general facts about modular
arithmetic.)
3. Fix a natural number n. A monomial is an expression of the form xk11 xk22 · · · xnkn for some
integers k1 , . . . , kn ≥ 0. The number d = k1 + · · · + kn is called the degree of the monomial.
Prove that there are exactly n+d−1
n−1
different monomials of degree d.
4. Pascal’s triangle modulo 2. In this problem, you will explore the even-odd pattern of the bino-
mial coefficients. (I will send a picture in a separate mail).
(a) Write out the first 9 rows of the Pascal triangle modulo two.
(b) Prove that for n = 0, 1, 2, . . .
n
2 −1
≡ 1 mod 2 for 0 ≤ k ≤ 2n − 1 ,
k
and (
for k = 0, 2n ,
n
2 1 mod 2
≡
k 0 mod 2 otherwise.
√ a > 0 there is a
5. (Spivak, Problem 2-15)). We will prove very soon that for every real number
unique real number x > 0 such that x2 = a. This number is denoted by x = a.
Let p, q be rational numbers and m ∈ N. Show that there are rational numbers a, b such that
√ √ √ √
(a) (p + q)m = a + b q , and (b) (p − q)m = a − b q .
6. The Fibonacci sequence (see Spivak, Problem 2.20). Consider the recursion
an = an−1 + an−2 for n ≥ 3 , (1)
with initial values a1 = a2 = 1.
(a) Ignoring the initial values for the moment, find solutions of the recursion in Eq. (1) that
have the form an = λn . (You will need to solve a certain quadratic equation.)
(b) Superposition principle. Suppose that a1 , a2 , . . . and b1 , b2 , . . . both satisfy the recursion in
Eq. (1), let s, t ∈ R, and set
cn := san + tbn , for n = 1, 2, . . .
Argue that cn also satisfies the recursion.
(c) Choose s, t so that c1 = c2 = 1.
(You have found a closed formula for the Fibonacci sequence!)