Try It Now
Work these exercises to see how well you understand this material.
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 □