Try It Now

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

Solutions

  1. Answer:

    We wish to prove that P(n) : 1 + 3 + 5 + · · · + (2n − 1) = nis 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:

    \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*}

  2. 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*}

  3. 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*}

  4. 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 p+ 1 ) ⇔ ¬ ((p1 p2 · · · pn) ∧ p+ 1)
                                                  ⇔ ¬ (p1 p2 · · · pn) ∨ (¬p+ 1)
                                                  ⇔ ((¬p1) ∨ (¬p2) ∨ · · · ∨ (¬pn)) ∨ (¬p+ 1)
                                                  ⇔ (¬p1) ∨ (¬p2) ∨ · · · ∨ (¬pn) ∨ (¬p+ 1)

  5. 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 | = 2− 1. Clearly, | E1| = 1, and, if for some n ⩾ 1, |En | = 2− 1 , it follows that |E+ 1| = 2n by the following reasoning.

    We partition E+ 1 according to the first bit: E+ 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,

    |E+ 1| = |Enc| + |En| = 2 − 1 + (2n 2− 1) = 2n  .

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

  7. 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 + · · · a+ a+ 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) + (a+ 1 + · · · + a+ 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 ,

    \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*}

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

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

    Solution. For m ⩾ 1, let p(m) be xm = 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

    x+ (+ 1) = x(m) +1      by associativity of integer addition
                     = xmx1        by recursive definition
                     = xnxmx1      induction hypothesis
                     = xnx+ 1      recursive definition □