## Introduction to Discrete Mathematics, Fall 2000 Problem Set 1, 26-28 Sept.

1. 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'' .

2. 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?

1. List all the equivalence relations (partitions) on the set .
2. Draw the Hasse diagrams of all the (partial) orders on the set .

3. 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 ?

4. Prove that every finite ordered set contains a maximal, but not necessarily a greatest element.

5. 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 .