Next: About this document ...
Up: prob1
Previous: prob1
- The Fibonacci numbers , , are defined by
the recurrence relation , ,
, for .
(Thus the first numbers in the sequence are 0, 1, 1, 2, 3, 5, 8, ...)
Prove by induction on that for all ,
where denotes the ``golden ratio''
.
- Let
. Draw the Hasse diagram of the order relation
, where
(Here denotes the standard ordering of the integers.)
Is the corresponding relation, where ``and'' is replaced by ``or''
in the definition, also a partial order?
- List all the equivalence relations (partitions) on
the set .
- Draw the Hasse diagrams of all the (partial) orders
on the set .
- Describe, in a general way, the structure of the ordered sets
and
.
(The notation ``|'' here denotes the divisibility relation
of the integers, i.e. iff is a factor of .)
What are the minimal elements of the orders? Immediate successors
of a given element? What is the maximal length in each order of
a chain, i.e. a totally ordered sequence of elements
?
- Prove that every finite ordered set contains a maximal,
but not necessarily a greatest element.
- The induction principle for natural numbers claims that
the following holds for any property of the natural numbers:
if is true, and the implication
is true for all
, then is true
for all
.
Prove the correctness of this principle, using the facts that
the standard ordering of the natural numbers
is a well-ordering with least element , and in addition
every element
has an immediate
predecessor .
Next: About this document ...
Up: prob1
Previous: prob1
Pekka Orponen
2000-09-25