Try It Now

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.

1. Answer:
   
   We wish to prove that P(n) : 1 + 3 + 5 + · · · + (2n − 1) = n² is true for n ⩾ 1. Recall that the nth odd positive integer is 2n - 1.
   
   Basis: for n = 1, P(n) is 1 = 1², which is true
   
   Induction: Assume that for some n ⩾ 1, P(n) is true. Then:
   
   $\begin{align*} 1+3+...+(2(n+1)-1) &= (1+3+...+(2n-1)) + (2(n+1)-1) \\ &= n^2 + (2n+1) \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \mathrm{by \; P(n) \; and \; basic \; algebra} \\ &= (n+1)^2 \blacksquare \end{align*}$
   
   
3. Answer: Proof:
   • Basis: 1 = 1(2)(3)/6 = 1
   • Induction:
     
     $\begin{align*} \sum_{1}^{n+1} k^2 &= \sum_{1}^{n} k^2 + (n+1)^2 \\ &= \frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\ &= \frac{(n+1)(2n^2 + 7n + 6)}{6} \\ &= \frac{(n+1)(n+2)(2n+3)}{6} \blacksquare \end{align*}$
     
     
5. Answer: Basis: For n = 1, we observe that $\frac{1}{1 \cdot 2} = \frac{1}{1+1}$
   
   Induction: Assume that for some n ⩾ 1, the formula is true. Then:
   
   $\begin{align*} \frac{1}{(1 \cdot 2)} + ... + \frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &= \frac{n}{n+1} + \frac{1}{(n+1)(n+2)} \\ &= \frac{(n+2)n}{(n+1)(n+2)} + \frac{1}{(n+1)(n+2)} \\ &= \frac{(n+1)^2}{(n+1)(n+2)} \\ &= \frac{n+1}{n+2} \blacksquare \end{align*}$
   
   
6. 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.
   
   ¬ (p₁ ∧ p₂ ∧ · · · ∧ p_n ∧ p_{n + 1} ) ⇔ ¬ ((p₁ ∧ p₂ ∧ · · · ∧ p_n) ∧ p_{n + 1})
                                                 ⇔ ¬ (p₁ ∧ p₂ ∧ · · · ∧ p_n) ∨ (¬p_{n + 1})
                                                 ⇔ ((¬p₁) ∨ (¬p₂) ∨ · · · ∨ (¬p_n)) ∨ (¬p_{n + 1})
                                                 ⇔ (¬p₁) ∨ (¬p₂) ∨ · · · ∨ (¬p_n) ∨ (¬p_{n + 1})
   
   
7. Answer: Let A_n be the set of strings of zeros and ones of length n (we assume that | A_n| = 2ⁿ is known). Let E_n be the set of the “even” strings, and E_n^c  =  the odd strings. The problem is to prove that for n ⩾ 1,|E_n | = 2^n − 1. Clearly, | E₁| = 1, and, if for some n ⩾ 1, |E_n | = 2^n − 1 , it follows that |E_{n + 1}| = 2ⁿ by the following reasoning.
   
   We partition E_{n + 1} according to the first bit: E_{n + 1} = {1 s | s ∈ E_n^c} ∪ {0s | s ∈ E_n}
   
   Since {1s | s ∈ E_n^c} and {0s | s ∈ E _n} are disjoint, we can apply the addition law. Therefore,
   
   |E_{n + 1}| = |E_n^c| + |E_n| = 2 ^n − 1 + (2ⁿ − 2^n − 1) = 2ⁿ  . ■
   
   
9. Answer: Assume that for n persons (n ⩾ 1), $\frac{(n-1)n}{2}$  handshakes take place. If one more person enters the room, he or she will shake hands with n people,
   
   $\begin{align*} \frac{(n-1)n}{2} + n &= \frac{n^2-n+2n}{2} \\ &= \frac{n^2+n}{2} = \frac{n(n+1)}{2} \\ &= \frac{((n+1)-1)(n+1)}{2} \end{align*}$
   
   Also, for n = 1, there are no handshakes, which matches the conjectured formula:
   
   $\frac{(1-1)(1)}{2} = 0$ ■.
   
   
11. Solution: Let p(n) be “a₁ + a₂ + · · · + a_n has the same value no matter how it is evaluated.”
    
    Basis: a₁ + a₂ + a₃ may be evaluated only two ways. Since + is associative,  (a₁ + a₂) + a ₃ = a₁ + (a₂ + a ₃). 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 a₁ + a₂ + · · · + a_n + a_{n + 1}. Any of the n additions in this expression can be applied last. If the j^th addition is applied last, we have c_j = (a₁ + a₂ + · · · + a_j) + (a_{j + 1} + · · · + a_{n + 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 c₁ = c₂ = · · · = c_n. If i < j ,
    
    $\begin{align*} c_i &= (a_1 + a_2 + ... + a_i) + (a_{i+1} + ... + a_{n+1}) \\ &= (a_1 + a_2 + ... + a_i) + ((a_{i+1} + ... + a_j) + (a_{j+1} + ... + a_{n+1})) \\ &= ((a_1 + a_2 + ... + a_i) + (a_{i+1} + ... + a_j)) + (a_{j+1} + ... + a_{n+1}) \\ &= ((a_1 + a_2 + ... + a_j)) + (a_{j+1} + ... + a_{n+1}) \\ &= c_j \square \end{align*}$
    
    
12. Hint: The number of times the rules are applied should be the integer that you do the induction on.
    
    
13. Hint: Let p(m) be the proposition that x^m + n = x^mxⁿ for all n ≥ 1.
    
    Solution. For m ⩾ 1, let p(m) be x^n + m = xⁿx^m 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
    
    x^{n + (m + 1)} = x^{(n + m) +1}      by associativity of integer addition
                     = x^n + mx¹        by recursive definition
                     = xⁿx^mx¹      induction hypothesis
                     = xⁿx^{m + 1}      recursive definition □