Proof Involving Even and Odd Numbers

Date: 02/08/2005 at 20:10:45
From: Ben
Subject: Mathematical Proofs

We are given the following problem.  If a - 3b is even, then a + b is 
even.  

I began with a couple of individual cases, such as if a is odd and b 
is even, then a = 2k+1 and b = 2k, so a - 3b = -4k + 1.  I kept on 
going on this track with a is even and b is odd, a is even and b is 
even.  I'm just lost after this point.  Any suggestions?

Date: 02/09/2005 at 08:49:07
From: Doctor Boyd
Subject: Re: Mathematical Proofs

Hi Ben,

Thanks for writing to Dr. Math.

I would say that the track you're on will lead you to the solution.  I
would recommend that you make some kind of chart or table and write
down exactly what happened in each case.  What you're looking for is
that each time a - 3b was even, then a + b was also even.  If a - 3b
was odd, then it doesn't actually matter what a + b is since the "if"
part of your "if" statement failed. 

However, you're trying a lot of cases, and you really don't need to
try that many.  If you're working with mathematical proofs, then 
you've probably been exposed to the idea of the contrapositive.  In 
other words, the following statements are logically equivalent:

  If P then Q
  If not Q, then not P

As an example, I hope you will agree that the following two statements
are logically the same:

  If the sun's out, then it's sunny.
  If it's not sunny, then the sun's not out.

So, we could prove "if a + b is not even, then a - 3b is not even",
and this would be the same proof logically.  That way we only have to
check cases where a + b is not even, i.e., where it is odd.  That 
means we only have to check the cases:

  a is odd and b is even
  b is odd and a is even

I do this because it's way easier to determine whether a + b is odd
than it is to determine whether a - 3b is odd. 

If for both cases a - 3b is not even (i.e., it's odd), then you have
your proof.  If not, then you have a counterexample.

Has this helped you with your question?  Please write back if you'd
like some more help with this, or if you have any other questions.

All the best,

- Doctor Boyd, The Math Forum
  http://mathforum.org/dr.math/