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