next up previous
Next: About this document ... Up: prob1 Previous: prob1

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$,

    \begin{displaymath}\phi^{n-2} \leq F_n \leq \phi^{n-1},\end{displaymath}

    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

    \begin{displaymath}(r,s) \preceq (r',s') \qquad \mbox{iff} \qquad
r \leq r' \mbox{ and } s \leq s'.\end{displaymath}

    (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?

    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\}$.

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

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

next up previous
Next: About this document ... Up: prob1 Previous: prob1
Pekka Orponen 2000-09-25