Try It Now

Work these exercises to see how well you understand this material.

Exercises

  1. Prove that the sum of the first n odd integers equals n2.

  2. Prove that for n ≥1: \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1).

  3. Use mathematical induction to show that for n ≥1,

    \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + ... + \frac{1}{n(n+1)} = \frac{n}{n+1}

  4. Prove that if n ≥2, the generalized DeMorgan’s Law is true:

    ¬(p1p2 ∧ ... ∧ pn ) ⇔ (¬p1 ) ∨ (¬p2 ) ∨ · · · ∨ ( ¬pn).

  5. The number of strings of n zeros and ones that contain an even number of ones is 2− 1. Prove this fact by induction for n ≥ 1.

  6. Suppose that there are n people in a room, n ≥1, and that they all shake hands with one another. Prove that \frac{n(n-1)}{2} handshakes will have occurred.

  7. 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.

  8. 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 bS.

      Prove that a 0 ≤ a ≤ 1.

      Hint:
       The number of times the rules are applied should be the integer that you do the induction on.

  9. 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, x= x− 1x.

      For example, x3 = x2x = (x1x)x = ( xx)x.

      Prove that if n, m ∈ ℙ, x= xmxn.

      Hint: Let p(m) be the proposition that xn= xmxfor all n ≥ 1.

 


Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.