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