Homework assignments for M361K
========================================
Nr Section : Problems
----------------------------------------
[1]    1.1 : 13,14,20
       1.2 : 16,19
       1.3 : 9,12
---------------------------------------- due Fri Jul 15
[2]    2.1 : 11,22
       2.2 : 1,5   (see Remark R1 below)
       2.3 : 6,15
---------------------------------------- due Tue Jul 19
[3]    ... : A1        (see below)
       2.4 : 2,7,11
       2.5 : 5,8
---------------------------------------- due Fri Jul 22
[4]    3.1 : 5,8,10,16
       ... : A2        (see below)
---------------------------------------- due Tue Jul 26
[5]    ... : A3        (see below)
       3.2 : 1d,9,13a,14,18,21
---------------------------------------- due Fri Jul 29
[6]    3.3 : 4
       3.4 : 7d    (see Remark R2 below)
       ... : B1,B2,B3  (see below)
       3.5 : 13
---------------------------------------- due Tue Aug 2
[7]    4.1 : 10b
       4.2 : 1c,4
       5.1 : 7,8
       5.2 : 1b
       ... : C1        (see below)
---------------------------------------- due Fri Aug 5
[8]    5.3 : 4,11
       5.4 : 2,14
       6.1 : 1d,9
---------------------------------------- due Tue Aug 9
[9]    ... : D1,D2     (see below)
       6.2 : 7,15
       7.1 : 2d,16
       7.2 : 8,12,16
       7.3 : 4,6
---------------------------------------- OPTIONAL




======================================================
NOTE: NO LATE HOMEWORK

Unless stated otherwise in class,
homework is assigned every Tuesday and Friday,
and collected in class
the following Friday and Tueday, respectively.
Late homework will not be accepted.
But as announced, the lowest homework score
gets dropped before computing the homework average.


======================================================
REMARKS

R1. For Problem 2.2.1 you can use the following

Theorem. Given any nonnegative real number y,
there exists a unique nonnegative real number x, such that x2=y.

The number x is called the square root of y and is denoted by √y.

R2. For Problem 3.4.7 you can use the following

Fact. The sequence of real numbers xn=(1+1/n)n converges.
The limit is known as Euler's constant and is denoted by e.
Its value is e=2.71828...

======================================================
PROBLEMS A1 .. A3 

A1. Let a and δ be fixed but arbitrary positive real numbers.
Show that there exists a positive real number ε
such that |b-a|< ε implies |b2-a2|< δ.

A2. Let (S,d) be a metric space, let A be a closed subset of S,
and let (x1,x2,...) be a sequence of points in A.
If this sequence converges to a limit x∈S, prove that x∈A.

A3. Let (S,d) be a metric space, A a subset of S,
(x1,x2,...) a sequence in A, x a point in A,
C a positive constant, and f:A→S a function satisfying
    d(f(u),f(v)) ≤ Cd(u,v) for all u,v∈A.
Show that if xn→x then f(xn)→f(x).

======================================================
PROBLEMS B1 .. B3 

B1. Let 0<r<1.
Let (d1,d2,...) be a sequence of nonnegative real numbers, satifying
dn+1 ≤ rdn for all n≥1. Show that dn ≤ d1rn-1 for all n≥1.
Given a fixed but arbitrary m≥1,
let (D1,D2,...) be a sequence of nonnegative real numbers, satisfying
Dk ≤ dm+dm+1+ ... +dm+k-1 for all k≥1.
Show that Dk ≤ dm(1+r+r2+ ... +rk-1) for all k≥1.
Then multiply by 1-r to prove that (1-r)Dk ≤ dm for all k≥1.

Remark. Substituting the bound dm ≤ d1rm-1, one gets Dk ≤ (1-r)-1d1rm-1.

Definition. Let (S,d) be a metric space, and let 0<r<1.
A sequence (x1,x2,...) with the property that
d(xn+2,xn+1) ≤ rd(xn+1,xn) for all n≥1, is called r-contractive.

B2. Let (S,d) be a metric space, and let (x1,x2,...)
be an r-contractive sequence in S, for some positive r<1.
Show that the numbers dn=d(xn+1,xn),
and for any given m≥1 the numbers Dk=d(xm+k,xm),
have the properties assumed in Problem B1.
Use this to prove that there exists a constant C>0,
such that d(xm+k,xm) ≤ Crm for all m,k≥1.

Remark. A possible value that one gets from B1 is C=(1-r)-1d1r-1.

B3. Show that every contractive (meaning r-contractive for
some positive r<1) sequence in a metric space is a Cauchy sequence.
Hint: Use the result of B2.

======================================================
PROBLEMS C1 ..  

C1. (The bisection algorithm for solving f(x)=y.)
Let f be a continuous real-valued function on an interval [a1,b1].
Assume that f(a1)≤y≤f(b1).
For n=1,2,... define the following.
Let xn be the mid-point between an and bn.
If f(xn)≤y, define an+1=xn and bn+1=bn. Otherwise, set an+1=an and bn+1=xn.
Show that xn→x for some x∈[a1,b1], and that f(x)=y.

======================================================
PROBLEMS D1 .. D2 

For these problems you may use the following theorem that will be proved later.

Theorem. There exists a differentiable function ln:R+→R such that
ln(1)=0,  ln'(x)=1/x for all x>0.

Here, and in what follows, R denotes the set of all real numbers,
and R+ denotes the set of all positive real numbers.

D1. Prove that ln(ax)=ln(a)+ln(x) for all real numbers a,x>0.

Hint: Given any a>0, define f(x)=ln(ax)-ln(x) for all x>0.
Show that f is constant by computing f', and then set x=1 to find the constant.

Remark. Setting a=1/x in D1 yields ln(1/x)=-ln(x).
And by induction, one gets ln(xn)=n ln(x) for all integers n.

D2. Prove that ln is strictly increasing.
Then prove that ln:R+→R is one-to-one and onto.

Hint: For "onto", prove that ln[R+] is unbounded above and below,
by considering ln(2n) for large n and small (negative) n.