Adding by a Form of 0 (Part 3)

As part of my discrete mathematics class, I introduce my freshmen/sophomore students to various proof techniques, including proofs about sets. Here is one of the examples that I use that involves adding and subtracting a number twice in the same proof.

Theorem. Let A be the set of even integers, and define

B = \{ n: n = m+1 for some odd integer m\}

Then A = B.

Proof (with annotations). Before starting the proof, I should say that I expect my students to use the formal definitions of even and odd:

  • An integer n is even if n = 2k for some integer k.
  • An integer n is odd if n = 2k+1 for some integer k.

To prove that A = B, we must show that A \subseteq B and B \subseteq A. The first of these tends to trickiest for students.

Part 1. Let n \in A. By definition of even, that means that there is an integer k so that n = 2k.

To show that n \in B, we must show that n = m + 1 for some odd integer m. To this end, notice that n = (n-1) + 1. Thus, we must show that n - 1 is an odd integer, or that n -1 can be written in the form 2k+1. To do this, we add and subtract 1 a second time:

n = 2k

= (2k - 1) + 1

= ([2k - 1 - 1] + 1) + 1

= ([2k-2] + 1) + 1

= (2[k-1] + 1) + 1.

By the closure axioms, k-1 is an integer. Therefore, 2[k-1] + 1 is an odd number by definition of odd, and hence $n \in B$.

The above part of the proof can be a bit much to swallow for students first learning about proofs. For completeness, let me also include Part 2 (which, in my experience, most students can produce without difficulty).

Part 2. Let n \in B, so that n = m + 1 for some odd integer m. By definition of odd, there is an integer k so that $m = 2k+1$. Therefore, n = (2k+1) + 1 = 2k+2 = 2(k+1). By the closure axioms, k +1 is an integer. Therefore, n is even by definition of even, and so we conclude that n \in A.

\square

For what it’s worth, this is the review problems for which I recorded myself talking through the solution for the benefit of my students.

In my opinion, the biggest conceptual barriers in this proof are these steps from Part 1:

2k = (2k - 1) + 1 = ([2k - 1 - 1] + 1) + 1.

These steps are undeniably awkward. Back in high school algebra, students would get points taken off for making the expression more complicated instead of simplifying the answer. But this is the kind of jump that I need to train my students to do so that they can master this technique and be successful in their future math classes.

Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: