Try It Now
Site: | Saylor Academy |
Course: | CS202: Discrete Structures |
Book: | Try It Now |
Printed by: | Guest user |
Date: | Friday, February 4, 2022, 5:37 PM |
Description
Work these exercises to see how well you understand this material.
Exercises
- Prove that the sum of the first n odd integers equals n2.
- Prove that for n ≥1:
.
- Use mathematical induction to show that for n ≥1,
- Prove that if n ≥2, the generalized DeMorgan’s Law is true:
¬(p1 ∧ p2 ∧ ... ∧ pn ) ⇔ (¬p1 ) ∨ (¬p2 ) ∨ · · · ∨ ( ¬pn). - The number of strings of n zeros and ones that contain an even number of ones is 2n − 1. Prove this fact by induction for n ≥ 1.
- Suppose that there are n people in a room, n ≥1, and that they all shake hands with one another. Prove that
handshakes will have occurred.
- Generalized associativity. It is well known that if a1, a2, and a 3 are numbers, then no matter what order the sums in the expression a1 + a 2 + a3 are taken in, the result is always the same. Call this fact p(3) and assume it is true. Prove using course-of-values induction that if a1, a2, . . . , and an are numbers, then no matter what order the sums in the expression a1 + a2 + · · · + an are taken in, the result is always the same.
- Let S be the set of all numbers that can be produced by applying any of the rules below in any order a finite number of times.
- Rule 1: 1 ∈S
- Rule 2: 1 ∈ S
- Rule 3: If a and b have been produced by the rules, then ab ∈S.
- Rule 4: If a and b have been produced by the rules, then a + b∈ S.
Prove that a ∈ S ⇒ 0 ≤ a ≤ 1.
Hint: The number of times the rules are applied should be the integer that you do the induction on.
- Proofs involving objects that are defined recursively are often inductive. A recursive definition is similar to an inductive proof. It consists of a basis, usually the simple part of the definition, and the recursion, which defines complex objects in terms of simpler ones. For example, if x is a real number and n is a positive integer, we can define xn as follows:
- Basis: x1 = x.
- Recursion: if n ≥ 2, xn = xn − 1x.
For example, x3 = x2x = (x1x)x = ( xx)x.
Prove that if n, m ∈ ℙ, xm + n = xmxn.
Hint: Let p(m) be the proposition that xm + n= xmxn for all n ≥ 1.
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.
Solutions
- Answer:
We wish to prove that P(n) : 1 + 3 + 5 + · · · + (2n − 1) = n2 is true for n ⩾ 1. Recall that the nth odd positive integer is 2n - 1.
Basis: for n = 1, P(n) is 1 = 12, which is true
Induction: Assume that for some n ⩾ 1, P(n) is true. Then:
- Answer: Proof:
- Answer: Basis: For n = 1, we observe that
Induction: Assume that for some n ⩾ 1, the formula is true. Then: - Solution: Basis: (n = 2) Proven with a truth table already.
Induction: Assume the generalized DeMorgan’s Law with n propositions is true for some n ≥ 2.
¬ (p1 ∧ p2 ∧ · · · ∧ pn ∧ pn + 1 ) ⇔ ¬ ((p1 ∧ p2 ∧ · · · ∧ pn) ∧ pn + 1)
⇔ ¬ (p1 ∧ p2 ∧ · · · ∧ pn) ∨ (¬pn + 1)
⇔ ((¬p1) ∨ (¬p2) ∨ · · · ∨ (¬pn)) ∨ (¬pn + 1)
⇔ (¬p1) ∨ (¬p2) ∨ · · · ∨ (¬pn) ∨ (¬pn + 1) - Answer: Let An be the set of strings of zeros and ones of length n (we assume that | An| = 2n is known). Let En be the set of the “even” strings, and Enc = the odd strings. The problem is to prove that for n ⩾ 1,|En | = 2n − 1. Clearly, | E1| = 1, and, if for some n ⩾ 1, |En | = 2n − 1 , it follows that |En + 1| = 2n by the following reasoning.
We partition En + 1 according to the first bit: En + 1 = {1 s | s ∈ Enc} ∪ {0s | s ∈ En}
Since {1s | s ∈ Enc} and {0s | s ∈ E n} are disjoint, we can apply the addition law. Therefore,
|En + 1| = |Enc| + |En| = 2 n − 1 + (2n − 2n − 1) = 2n . ■ - Answer: Assume that for n persons (n ⩾ 1),
handshakes take place. If one more person enters the room, he or she will shake hands with n people,
Also, for n = 1, there are no handshakes, which matches the conjectured formula:■.
- Solution: Let p(n) be “a1 + a2 + · · · + an has the same value no matter how it is evaluated.”
Basis: a1 + a2 + a3 may be evaluated only two ways. Since + is associative, (a1 + a2) + a 3 = a1 + (a2 + a 3). Hence, p(3) is true.
Induction: Assume that for some n ≥ 3, p(3), p(4), . . . , p(n) are all true.
Now consider the sum a1 + a2 + · · · + an + an + 1. Any of the n additions in this expression can be applied last. If the jth addition is applied last, we have cj = (a1 + a2 + · · · + aj) + (aj + 1 + · · · + an + 1). No matter how the expression to the left and right of the j th addition are evaluated, the result will always be the same by the induction hypothesis, specifically p(j ) and p(n + 1 − j ). We now can prove that c1 = c2 = · · · = cn. If i < j , - Hint: The number of times the rules are applied should be the integer that you do the induction on.
- Hint: Let p(m) be the proposition that xm + n = xmxn for all n ≥ 1.
Solution. For m ⩾ 1, let p(m) be xn + m = xnxm for all n ⩾ 1. The basis for this proof follows directly from the basis for the definition of exponentiation.
Induction: Assume that for some m ⩾ 1, p (m) is true. Then
xn + (m + 1) = x(n + m) +1 by associativity of integer addition
= xn + mx1 by recursive definition
= xnxmx1 induction hypothesis
= xnxm + 1 recursive definition □