Ask a question
0 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] 
Tutors, please sign in to answer this question.

1 Answer

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.


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]