## Try It Now

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

### Exercises

- Prove that the sum of the first
*n*odd integers equals*n*^{2}. - Prove that for
*n*≥1: . - Use mathematical induction to show that for
*n*≥1, - Prove that if
*n*≥2, the generalized DeMorgan’s Law is true:

¬(*p*_{1}∧*p*_{2}∧ ... ∧*p*) ⇔ (¬_{n}*p*_{1}) ∨ (¬*p*_{2}) ∨ · · · ∨ ( ¬*p*)._{n} - 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. - Suppose that there are
*n*people in a room,*n*≥1, and that they all shake hands with one another. Prove that handshakes will have occurred. - Generalized associativity. It is well known that if
*a*_{1},*a*_{2}, and*a*_{3}are numbers, then no matter what order the sums in the expression*a*_{1}+*a*_{2}+*a*_{3}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*_{1},*a*_{2},*. . . ,*and*a*are numbers, then no matter what order the sums in the expression_{n}*a*_{1}+*a*_{2}+*· · ·*+*a*are taken in, the result is always the same._{n} - 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.The number of times the rules are applied should be the integer that you do the induction on.

Hint:

- Rule 1: 1 ∈
- 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:^{n}

- Basis:
*x*^{1}=*x*. - Recursion: if
*n*≥ 2,*x*=^{n }*x*^{n }^{− }^{1}*x*.

For example,*x*^{3}=*x*^{2}*x*= (*x*^{1}*x*)*x*= (*xx*)*x*.

Prove that if*n, m*∈ ℙ,*x*^{m }^{+ }=^{n }*x*^{m}*x*.^{n}**Hint:**Let*p*(*m*) be the proposition that*x*^{m }^{+ }=^{n}*x*for all^{m}x^{n }*n*≥ 1.

- Basis:

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.