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

1. The Fibonacci numbers $F_n$, $n \geq 0$, are defined by the recurrence relation $F_0 = 0$, $F_1 = 1$, $F_{n} = F_{n-1} + F_{n-2}$, for $n \geq 2$. (Thus the first numbers in the sequence are 0, 1, 1, 2, 3, 5, 8, ...) Prove by induction on $n$ that for all $n \geq 2$,
   
   $$\phi^{n-2} \leq F_n \leq \phi^{n-1},$$
   
   
   where $\phi$ denotes the ``golden ratio'' $\phi = \frac{\sqrt{5}+1}{2}$.

2. Let $A = \{0,1,2\}^2$. Draw the Hasse diagram of the order relation $\preceq\; \subseteq A\times A$, where
   
   $$(r,s) \preceq (r',s') \qquad \mbox{iff} \qquad r \leq r' \mbox{ and } s \leq s'.$$
   
   
   (Here $\leq$ denotes the standard ordering of the integers.) Is the corresponding relation, where ``and'' is replaced by ``or'' in the definition, also a partial order?

3. 1. List all the equivalence relations (partitions) on the set $\{a,b,c\}$.
   2. Draw the Hasse diagrams of all the (partial) orders on the set $\{a,b,c\}$.

4. Describe, in a general way, the structure of the ordered sets $({\cal P}(\{1,2,\dots,n\}),\subseteq)$ and $(\{2,3,4,\dots,n\}, \vert)$. (The notation ``|'' here denotes the divisibility relation of the integers, i.e. $m \vert n$ iff $m$ is a factor of $n$.) 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 $a_1 \prec a_2 \prec \cdots \prec a_k$?

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

6. The induction principle for natural numbers claims that the following holds for any property $P$ of the natural numbers: if $P(0)$ is true, and the implication $P(n-1) \Rightarrow P(n)$ is true for all $n \in {\cal N}\setminus\{0\}$, then $P(n)$ is true for all $n \in {\cal N}$. Prove the correctness of this principle, using the facts that the standard ordering of the natural numbers $({\cal N}, \leq)$ is a well-ordering with least element $0$, and in addition every element $n \in {\cal N}\setminus\{0\}$ has an immediate predecessor $n-1$.