Winter 2014
MATH 309: Introduction to Proof in Discrete Mathematics
Branko Ćurgus

Monday, March 17, 2014

---

• Some solutions from Section 3.2 as a Mathematica file are here and a pdf print-out of the same file is here.
• Some solutions from Section 4.1 as a Mathematica file are here and a pdf print-out of the same file is here.
• Some solutions from Section 4.3 as a Mathematica file are here and a pdf print-out of the same file is here.
• Some solutions from Section 4.4 as a Mathematica file are here and a pdf print-out of the same file is here.
• Some solutions from Section 4.5 as a Mathematica file are here and a pdf print-out of the same file is here.
• Some solutions from Section 6.1 as a Mathematica file are here and a pdf print-out of the same file is here.

---

Friday, March 15, 2014

---

• Here is an updated list of topics for the final exam.

---

Monday, March 10, 2014

---

• Read Section 6.2 up to Linear nonhomogenous recurrence relations with constant coefficients on page 419.
• Do the exercises: 1, 2, 3, 4, 7, 11, 12, 23, 24, 25, 29, 32, 35, 41, 42, 43.
• Read Section 6.1.
• Do the exercises: 3, 4, 6, 7, 9, 14, 15, 16, 17, 19, 22, 23, 24, 25, 26, 27, 40, 41, 45.

---

Thursday, March 6, 2014

---

• We started Section 4.5 today.
• Do the exercises: 1-9, 12, 14-16, 20, 21, 23, 25, 30, 31, 33, 37, 39.

---

Tuesday, March 4, 2014

---

• We did Section 4.4 today.
• Do the exercises: 1-13, 21, 22, 28, 29, 30.

---

Friday, February 28, 2014

---

• Here is an updated list of topics that we did so far, some of which will appear on the coming exam.
• For Section 4.3 do as many exercises as you can from 1-43.

---

Tuesday, February 20, 2014

---

• Read Section 4.2.
• Do the exercises: 3, 4, 5, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 36, 40.
• The Pigeonhole Principle: If there are $N$ pigeons and these pigeons are distributed in $k$ pigeonholes, then there is at least one hole containing at least $\bigl\lceil N/k \bigr\rceil$ pigeons.
• Notice the following direct proof of the Pigeonhole Principle.
  • Denote by $m_1$, $m_2, \ldots, m_k$ the number of pigeons in each of the $k$ holes.
  • Then, by the sum rule, $N = m_1 + m_2 + \cdots + m_k$.
  • Denote by $m$ the maximum number of pigeons in one hole. Then for all $j \in \{1,\ldots,k\}$ we have $m_j \leq m$. By the properties of order of integers \[ m_1 + m_2 + \cdots + m_k \leq k m. \]
  • By the transitivity of inequality, from the last two items we conclude that $N \leq k m$. Consequently, since $k \gt 0$, we have $N/k \leq m$.
  • Since $m$ is a positive integer, properties of the ceiling function imply \[ \left\lceil \frac{N}{k}\right\rceil \leq m . \]
  • Since there is a hole with $m$ pigeons in it, we conclude: At lease one hole contains at least $\bigl\lceil N/k \bigr\rceil$ pigeons.
• Going back to counting problems, today in class I illustrated how one can program in Mathematica to really count the sets from the exercises and so have a hands-on verification of our abstract counting.
• In class use Mathematica version 5.2. On some campus computers we also have Mathematica version 8. These versions are not compatible. For this class I will only post version 5.2 notebooks since on in the labs there are more computers with version 5.2.
• Here is the Mathematica 5.2 file that I used. It is called 20140220.nb. Right-click on the underlined word "Here"; in the pop-up menu that appears, your browser will offer you to save the file in your directory. Make sure that you save it with the exactly same name. After saving the file you can open it with Mathematica 5.2. You will find Mathematica 5.2 on many campus computers in Start -> All Programs -> Math Applications -> Mathematica 5.2. Open Mathematica first, then open 20140220.nb from Mathematica 5.2. You can execute the entire file by the following manu sequence (in Mathematica): Kernel -> Evaluation -> Evaluate Notebook.
• To evaluate a particular cell in a Mathematica file place the cursor in the cell and press Shift+Enter. There is more about how to use Mathematica 5.2 at my Mathematica page.
• If you have problems running files that I post please let me know. If you spend some time learning how to use these files you will enhance the understanding of math that you are studying.

---

Tuesday, February 18, 2014

---

• Read Section 4.1.
• Do the exercises: As many as you can from 1-33. Also 36, 37 (the answer should involve a single formula involving n), 38-42, 47, 48, 49.
• The basic counting rules are:
  • The sum rule: For disjoint finite sets $A$ and $B$ we have $|A \cup B| = |A| + |B|$.
  • The product rule: For finite sets $A$ and $B$ we have $|A \times B| = |A| \cdot |B|$.
  • The inclusion-exclusion rule: For finite sets $A$ and $B$ we have $|A \cup B| = |A| + |B| - |A\cap B|$.
  • The complement rule: For finite sets $A$ and $U$ we have $|A| = |U| - |U\setminus A|$.
• Usually counting requires use of several rules. One way to avoid wrong counts is to make clear which counting rules you use and make sure that the rules are used correctly.
• The complement rule is almost miraculous when $A$ is difficult to count, but $U$ and $U\setminus A$ are much easier to count.

---

Friday, February 14, 2014

---

• Read the first part of Section 3.4, up to Recursively defined sets and structures.
• Do the exercises: 1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15, 16, 18, 19

---

Tuesday, February 11, 2014

---

• We started Section 3.3. You can skip Examples 10, 12, 13. Subsection "The well-ordering property" can be useful in Math 302.
• Do the exercises: 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 15, 18, 19, 20, 24, 25, 26 (use the result from 25), 32, 36, 37, 50, 51, 53, 54, 57, 59, 62.
• Today I solved Exercise 12 in Section 3.2. Exercise 12 requires us to prove that the sequence $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor \ $ with $n \in {\mathbb Z}^+$ has the values 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, ....
• To solve Exercise 12 we have to answer the following question: For a given $m \in {\mathbb Z}^+$ how many positive integers $n$ satisfy the equality
  

  $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $?

  This question will be answered by the following equivalences.
  • By the definition of the floor function
    

    $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $ \ m \leq \sqrt{2n} + \frac{1}{2} \lt m+1$.

  • By the properties of order of real numbers
    

    $m \leq \sqrt{2n} + \frac{1}{2} \lt m+1 \ $ if and only if $ \ m - \frac{1}{2} \leq \sqrt{2n} \lt m + \frac{1}{2}$

  • Since each term in the inequality is positive we have
    

    $m - \frac{1}{2} \leq \sqrt{2n} \lt m + \frac{1}{2} \ $ if and only if $ \ m^2 - m + \frac{1}{4} \leq 2n \lt m^2 + m + \frac{1}{4}$

  • Since $m^2 - m$, $2n$ and $m^2 + m$ are integers we have
    

    $m^2 - m + \frac{1}{4} \leq 2n \lt m^2 + m + \frac{1}{4} \ $ if and only if $ \ m^2 - m \lt 2n \leq m^2 + m$

  • Since $2 \gt 0$,
    

    $m^2 - m \lt 2n \leq m^2 + m \ $ if and only if $ \ \dfrac{(m-1)m}{2} \lt n \leq \dfrac{m(m + 1)}{2}$

  • Thus, for $m, n \in {\mathbb Z}^+$ we have proved the equivalence:
    

    $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $ \ \dfrac{m(m-1)}{2} \lt n \leq \dfrac{m(m+1)}{2}$.

  • Next, notice the identity \[ \dfrac{m(m+1)}{2} = \dfrac{m(m-1)}{2} + m. \] Therefore, $ \ \dfrac{m(m-1)}{2} \lt n \leq \dfrac{m(m+1)}{2} \ $ if and only if $\ n \ $ is one of $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \]
  • Finally we conclude that $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $\ n \ $ is one of $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \] That is, the sequence $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor$ takes the value $m$ exactly at $m$ distinct consecutive values of $n$.

---

Monday, February 10, 2014

---

• Here I summarize what we did from the notes Basic propositions about the Integers.
  • Proposition 2.5. For every $a\in \mathbb Z$ we have $a\cdot 0 = 0\cdot a = 0$.
  • Corollary 3.7. $0 \lt 1$. (In class I gave a proof by contradiction.)
  • Definitions 3.9 and 3.10 and Exercises 3.11 and 3.12.
  • Section 4 up to Definition 4.5.
  • Section 5, all except the proof of the Division Algorithm.
  • Section 6.
• The axioms for the integers have their own web-page here.
• Section 3.2: Do the exercises 2, 4, 5, 6, 9, 11, 12, some of 13-18, 19, 20, 21, 23. Notice that Exercises 11 and 12 are more challenging.

---

Friday, January 31, 2014

---

• Here is the list of topics that we did so far, some of which will appear on the final exam. In this list I emphasized some of the more important exercises that we did.

---

Thursday, January 30, 2014

---

• The axioms for the integers are posted here.
• Some basic properties of integers deduced from the axioms can be found here.

---

Friday, January 24, 2014

---

• Today we started Section 1.8. Do the exercises 1, 2, 4, 8, 9, 10, 11, 12, 13, 14, 17, 18, 23, 25, 26, 27, 28, 29, 31, 43, 44, 45, 48, 49, 56, 58, 60(f), 65, 66 ((b) and (d) in 66 are wrong)
• Here I state a formal definition of function. This definition identifies a function and its graph. The justification is that if you know the graph of a function, then you know the function, and conversely, if you know a function you know its graph. I like this definition since it takes advantage of the language that we learned in the logic part of the class. Simply stated the definition below says that a function from a set $A$ to a set $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that for each $x \in A$ there exists unique $y \in B$ such that $(x,y) \in F$.
  
  
  Definition Let $A$ and $B$ be nonempty sets. A function from $A$ into $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that

  • $\forall \, x \in A \ \ \exists \, y \in B \quad (x,y) \in F$,
  • $\forall \, x \in A \ \forall \, y \in B \ \forall \, z \in B \quad (x,y) \in F \wedge (x,z) \in F \ \Rightarrow \ y=z$.
• While reading Section 1.8. Pay attention to the following concepts.
  • function, domain, codomain, range,
  • one-to-one function (I prefer the synonym: injection)
  • onto function (I prefer the synonym: surjection)
  • bijection
    A comment on terminology:
    Our textbook and many other books use the synonym phrase "one-to-one correspondence".
    Here are three reasons why "bijection" is preferable to "one-to-one correspondence":
    1. In the setting of functions it is easy to confuse "one-to-one correspondence" with "one-to-one function". Notice that a "one-to-one function" is not necessarily a "one-to-one correspondence"
    2. The noun "correspondence" is not used in mathematics at an undergraduate level. Therefore, students might be wondering: what is a correspondence? is it a function or not?
    3. We should leave "one-to-one correspondence" to be used in informal settings. For example, here "one-to-one correspondence" is used in a preschool setting.
  • inverse function
  • composition of functions
  • Table 1 with the basic properties of the floor and ceiling functions.
• Wikipedia's Function page:
  • Function

---

Thursday, January 23, 2014

---

• We did Section 1.7 today. Do the exercises 2, 3, 11, 14, 18, 19, 20, 24, 26, 27, 28, 29, 30, 31, 32, 33
• Wikipedia's Set page is relevant here:
  • Set

---

Tuesday, January 21, 2014

---

• Here is the link to a page that gives 23 proofs that $\sqrt{2}$ is irrational. However, the proof that I gave in class is not included.
• We did Section 1.6: Sets today. Do the exercises 1 - 21, 24, 25, 27, 28.
• Some relevant Wikipedia links:
  • Set
  • The number 1
  • The number 0
  • Integers
  • Natural numbers
  • Rational numbers
  • Real numbers

---

Thursday, January 16, 2014

---

• Yesterday and today we did Section 1.5. Pay special attention to the "mathematical" proofs in this section. In particular pay attention how definitions are used in proofs. Remember: all definitions are biconditionals (that is "if and only if" statements), although they are not stated that way. Do the exercises 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 39, 40, 43, 44, 46, 49, 51, 55, 64, 65, 70.

---

Monday, January 13, 2014

---

• Today we did Section 1.4. Do the exercises 1, 2, 9, 10, 16, 19, 20, 24, 25, 26, 27, 28, 29, 30, some of 31-36, 37, 38, 39, 40, 41, 42, 43, 44, 45.
• Here are few exercises involving quantified statements with three variables. For each statement formulate the negation and decide which one is true: the original statement or its negation. Provide a proof of your claim.
  • $\forall\, a \ \forall\, b \ \exists\, c \quad cb \gt a$    (the universe of discourse consists of all real numbers)
  • $\forall\, a \ \forall\, b \ \exists\, c \quad cb \gt a$    (the universe of discourse consists of all positive real numbers)
  • $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (zx \gt 1)$    (the universe of discourse consists of all real numbers)
  • $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (zx \gt 1)$    (the universe of discourse consists of all positive real numbers)
  • $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (z^2 \gt x^2)$    (the universe of discourse consists of all real numbers)
  • $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (z^2 \gt x)$    (the universe of discourse consists of all real numbers)

---

Friday, January 10, 2014

---

• Here is the definition of the leap year from Wikipedia :

  In the Gregorian calendar, the current standard calendar in most of the world, most years that are evenly divisible by 4 are leap years. In each leap year, the month of February has 29 days instead of 28. Adding an extra day to the calendar every four years compensates for the fact that a period of 365 days is shorter than a solar year by almost 6 hours. Some exceptions to this rule are required since the duration of a solar year is slightly less than 365.25 days. Years that are evenly divisible by 100 are not leap years, unless they are also evenly divisible by 400, in which case they are leap years.

• As you can see Wikipedia's definition is quite verbose. It is clear that this definition uses only three predicates involving a year as a variable. These predicates are: $P(y)$ is "$y$ is divisible by $4$.   $Q(y)$ is "$y$ is divisible by $100$.   $R(y)$ is "$y$ is divisible by $400$. It is an interesting exercise use these predicates to write the definition of the leap year in a formal way. Here is one way to do this:
  Let $y$ stand for a particular year.
  
  $y\ $ is a leap year if and only if $\ \ \bigl(P(y) \wedge (\neg Q(y)) \bigr) \vee R(y) \ \ $
  where
  
  

  $P(y)\ $ stands for:	$Q(y)\ $ stands for:	$R(y)\ $ stands for:
  $\dfrac{y}{4}\ $ is an integer.	$\dfrac{y}{100}\ $ is an integer.	$\dfrac{y}{400}\ $ is an integer.

• This formal definition can be implemented on a computer, provided that a computer knows logical operations and can decide whether a number is an integer or not. I did it in class in Mathematica. Here is the file that I created and its pdf version.
• Today we talked about Section 1.3. The exercises for this section are 1, 2, 9, 11 - 19, 28, 30, 31, 33, 34, 41, 46, 47, 55, 56, 57.

---

Thursday, January 9, 2014

---

• Today we talked about Section 1.2. Do the exercises 3, 4, 6, 8, 12, 13 and some of 14-29. Also do 49 and 51.
• Tomorrow we will do Section 1.3. The exercises for this section are 1, 2, 9, 11 - 19, 28, 30, 31, 33, 34, 41, 46, 47, 55, 56, 57.

---

Tuesday, January 7, 2014

---

• The information sheet
• The textbook loan form
• Read Section 1.1. Do the exercises 6, 7, 10, 12, 13, 15, 16, 20, 21, 22, 23, 24, 27, 30, 38, 39, 40, 41, 51-55.
• Here is a pdf file of the first few sections of the book.
• Here are 12 different ways to say: If p, then q.

---