1.2 Mathematical Induction 34.Every point of three-dimensional space is colored red, green, or blue. Prove that one
of the colors attains all distances, meaning that any positive real number represents
the distance between two points of this color.
5.The union of nine planar surfaces, each of area equal to 1, has a total area equal to- Prove that the overlap of some two of these surfaces has an area greater than or
equal to^19.
6.Show that there does not exist a functionf:Z→{ 1 , 2 , 3 }satisfyingf(x) =f(y)
for allx, y∈Zsuch that|x−y|∈{ 2 , 3 , 5 }.
7.Show that there does not exist a strictly increasing functionf:N→Nsatisfying
f( 2 )=3 andf (mn)=f (m)f (n)for allm, n∈N.
8.Determine all functionsf:N→Nsatisfying
xf (y)+yf (x)=(x+y)f (x^2 +y^2 )for all positive integersxandy.
9.Show that the interval[ 0 , 1 ]cannot be partitioned into two disjoint setsAandB
such thatB=A+afor some real numbera.
10.Letn>1 be an arbitrary real number and letkbe the number of positive prime
numbers less than or equal ton. Selectk+1 positive integers such that none of
them divides the product of all the others. Prove that there exists a number among
the chosenk+1 that is bigger thann.1.2 Mathematical Induction.........................................
The principle ofmathematical induction, which lies at the very heart of Peano’s axiomatic
construction of the set of positive integers, is stated as follows.
Induction principle.GivenP (n), a property depending on a positive integern,
(i)ifP(n 0 )is true for some positive integern 0 ,and
(ii)if for everyk≥n 0 ,P(k)true impliesP(k+ 1 )true,
thenP (n)is true for alln≥n 0.
This means that when proving a statement by mathematical induction you should (i)
check the base case and (ii) verify the inductive step by showing how to pass from an
arbitrary integer to the next. Here is a simple example from combinatorial geometry.
Example.Finitely many lines divide the plane into regions. Show that these regions can
be colored by two colors in such a way that neighboring regions have different colors.