Texas A&M University-Corpus Christi / Dept. of Computing and Mathematical Sciences

MATH 2305 §002 -- Discrete Mathematics I -- Spring 2003

Chapter 2 Study Questions

Section 2.1 Proof Techniques -- Name:

  1. Theorems about subject XXX are always tautologies and never include facts about XXX as hypotheses.

  2. A counterexample to a conjecture P -> Q is a case where P is true and Q is false.

  3. It is possible to write out all possible ways to trace out the lines in a figure.
  4. Direct proofs are always written as formal proofs in predicate logic.
  5. ‘If and only if’ requires two proofs.
  6. In a proof by contradiction, you may assume both the original hypothesis and the negation of the conclusion.

Section 2.2 Induction -- Name:

  1. Anyone who reaches the first rung of a ladder can reach rungs that are arbitrarily high.
  2. Induction can be used to prove something true for all integers greater than or equal to some given value.
  3. There are four steps necessary for a proof using the first principle of induction.
  4. In an induction proof, you must prove P(k+1) is true.
  5. The integer 2^240 –1 is divisible by 3.
  6. The inequality n^2 > 3n is true for all positive integers, n.
  7. The second principle of induction applies when the k+1 case depends on cases further back than k.

 

Section 2.4 Recursion-Sequences and Objects -- Name:

  1. A sequence is a list of objects in some order.
  2. The Fibonacci sequence was introduced by a 14th century Spanish merchant.
  3. The set of ancestors of James can be defined recursively.
  4. An alphabet can have two letters.
  5. "Palindrome" is a palindrome.
  6. Exponentiation, but not multiplication of integers, can be defined recursively.

 

Section 2.4 Recursion-Algorithms and Solution of Relations -- Name:

  1. (See page 11) Implementing an algorithm requires skill and can go on forever.
  2. A recursive algorithm invokes itself with the same or larger input values.
  3. Recursive versions of algorithms are generally shorter than iterative versions of the same algorithm.
  4. Using a closed form solution to an recurrence relation still requires using the recurrence relation.
  5. Expand, guess and verify is the only approach to solving recurrence relations.