Search
Ask a question
0

Proving BIjection

Suppose that
a + b + c = d;
where a, b, c, d are nonnegative integers.
Let P be the assertion that d is even. Let W be the assertion that exactly one among
a, b, c are even, and let T be the assertion that all three are even.
Prove by cases that
P IFF [W OR T] 

1 Answer by Expert Tutors

Tutors, sign in to answer this question.
Andy C. | Math/Physics TutorMath/Physics Tutor
5.0 5.0 (4 lesson ratings) (4)
1
Given: A + B + C = D;
A,B,C, D are non-negative integers


Prove: D is even IF AND ONLY IF A or B or C are even OR All three are even.


Proof:
------>

All of the given hold, plus the fact that D is even.
WTS (wish to show) That one or all of A,B,C are even.

Proof By contradiction, suppose that all three of A,B,C are all odd integers.

Since D is even, then D = 2t for some integer t.

A+B+C = D = 2t

So (A+B+C)/2 = t

A/2 + B/2 + C/2 = t

Since A,B, and C are all odd by supposition,
A = 2x + 1, B = 2y + 1, and C = 2z + 1 for integers x,y, and z.

(2x+1)/2 + (2y+1)/2 + (2z+1)/2 = t

(2x+2y+2z+3)/2 = t <--- combines into one fraction

[2(x+y+z)+3] /2 = t <--- factors out 2 in the numerator

2(x+y+z)/2 + 3/2 = t <---- breaks them into 2 fractions

(x+y+z) + 3/2 = t <--- 2 cancels in the first fraction only

By closure property of integer addition, x+y+z is an integer,
but 3/2 is not. The sum thereof is not an integer. However,
this sum is equal to t, an integer. This is a contradiction.
Therefore, at least one of A,B, or C, or perhaps all three
must be an even integer, since the supposition is proven to be false.

<-----

All of the given hold, plus the fact that exactly one of, or perhaps,
all three of A,B, and C are an even integer.

WTS that D is even.

As a supporting proof, for two odd integers N1 = 2x+1 and N2=2y+1,
the sum is N1+N2 = 2x+1 + 2y + 1 = 2(x+y)+2 is an even integer,
where x and y are integers. Likewise, the sum of two even integers
is also an even integer. (The proof is left for the reader.)

If exactly one of A,B, and C is even, then the parity is:
even + odd + odd <--- can be obtained in this order by associative and commutative properties
of integers

even + (odd + odd) <---- associative property of integer addition

even + even <--- as just proven

which is even.

Likewise if all three of A,B, and C are even, then the parity must
be even, as the sum of two even integers are even, applied recursively.

So in either case, A+B+C is an even integer. Therefore, their sum (D) is even.

[end of proof]