CS202: Discrete Structures

1. Prove that the sum of the first n odd integers equals n².
   
   
3. Prove that for n ≥1: $\sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1)$.
   
   
5. 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}$
   
   
6. Prove that if n ≥2, the generalized DeMorgan’s Law is true:
   
   ¬(p₁ ∧ p₂ ∧ ... ∧ p_n ) ⇔ (¬p₁ ) ∨ (¬p₂ ) ∨ · · · ∨ ( ¬p_n).
   
   
7. The number of strings of n zeros and ones that contain an even number of ones is 2^n − 1. Prove this fact by induction for n ≥ 1.
   
   
9. 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.
   
   
11. Generalized associativity. It is well known that if a₁, a₂, and a ₃ are numbers, then no matter what order the sums in the expression a₁  + a ₂ +  a₃ 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 a₁, a₂, . . . , and a_n are numbers, then no matter what order the sums in the expression a₁ + a₂ + · · · + a_n are taken in, the result is always the same.
    
    
12. 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.
      
      
13. 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 xⁿ as follows:
    
    • Basis: x¹ = x.
    • Recursion: if n ≥ 2, xⁿ = x^n − 1x.
      
      For example, x³ = x²x = (x¹x)x = ( xx)x.
      
      Prove that if n, m ∈ ℙ, x^m + n = x^mxⁿ.
      
      Hint: Let p(m) be the proposition that x^m + n= x^mxⁿ 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.