A Short Course in Discrete Mathematics

Edward A. Bender, S. Gill Williamson

• Publisher: Dover Publications
• Year: 2012
• ISBN:
  9780486138657
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

What sort of mathematics do I need for computer science? In response to this frequently asked question, a pair of professors at the University of California at San Diego created this text. Its sources are two of the university's most basic courses: Discrete Mathematics, and Mathematics for Algorithm and System Analysis. Intended for use by sophomores in the first of a two-quarter sequence, the text assumes some familiarity with calculus. Topics include Boolean functions and computer arithmetic; logic; number theory and cryptography; sets and functions; equivalence and order; and induction, sequences, and series. Multiple choice questions for review appear throughout the text. Original 2005 edition. Notation Index. Subject Index.

Unit IS

Induction, Sequences and Series

Section 1: Induction

Suppose A(n) is an assertion that depends on n. We use induction to prove that A(n) is true when we show that

• it’s true for the smallest value of n and
• if it’s true for everything less than n, then it’s true for n.

In this section, we will review the idea of proof by induction and give some examples. Here is a formal statement of proof by induction:

Theorem 1 (Induction) Let A(m) be an assertion, the nature of which is dependent on the integer m. Suppose that we have proved A(n₀) and the statement

“If n > n₀ and A(k) is true for all k such that n₀ ≤ k < n, then A(n) is true.”

Then A(m) is true for all m ≥ n₀.¹⁹

Proof: We now prove the theorem. Suppose that A(n) is false for some n ≥ n₀. Let m be the least such n. We cannot have m = n₀ because one of our hypotheses is that A(n₀) is true. On the other hand, since m is as small as possible, A(k) is true for n₀ ≤ k < m. By the inductive step, A(m) is also true, a contradiction. Hence our assumption that A(n) is false for some n is itself false; in other words, A(n) is never false. This completes the proof.

Definition 1 (Induction terminology) “A(k) is true for all k such that n₀ ≤ k < n” is called the induction assumption or induction hypothesis and proving that this implies A(n) is called the inductive step. A(n₀) is called the base case or simplest case.

Example 1 (Every integer is a product of primes) A positive integer n > 1 is called a prime if its only divisors are 1 and n. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23. In another unit, we proved that every integer n > 1 is a product of primes. We now redo the proof, being careful with the induction.

We adopt the terminology that a single prime p is a product of one prime, itself. We shall prove A(n):

“Every integer n ≥ 2 is a product of primes.”

Our proof that A(n) is true for all n ≥ 2 will be by induction. We start with n₀ = 2, which is a prime and hence a product of primes. The induc...