4
$\begingroup$

I'm asked to prove 'Let $x \in Z$. $3x + 1$ is even iff $5x-2$ is odd'. I have the following proof techniques in my toolbox: trivial/vacuous proofs (not so relevant in this case), direct proof and proof via the contrapositive.


1) If $3x + 1$ is even, then $5x- 2$ is odd.

2) If $5x - 2$ is odd, then $3x + 1$ is even.

Theorem 1a: An odd number multiplied by an odd number yields an odd number.

Proof via direct proof. Let $n, m \in Z$. Assume n and m are odd numbers, so they can be written as $n = 2a + 1$ and $m = 2b + 1$ for any $a,b \in Z$.

Therefore $mn$ = $(2a + 1)(2b + 1)$ = $4ab + 2a + 2b + 1$ = $2(2ab + a + b) + 1$. Since $2ab + a + b + 1$ is an integer, $2(2ab + a + b) + 1$ is odd.

Theorem 1b: Adding and odd number to an odd number yields an even number.

Proof via direct proof. Let $n, m \in Z$. Assume n and m are odd numbers so they can be written as $n = 2a + 1$ and $m = 2b + 1$ for any $a,b \in Z$.

Therefore $m + n$ = $(2a + 1) + (2b + 1)$ = $2a + 2b + 2$ = $2(a + b + 1)$. Since $a + b + 1$ is an integer, $2(a + b + 1)$ is an even integer.

Theorem 1: If $3x + 1$ is even, then $5x- 2$ is odd.

Proof via direct proof. We know via 1a and 1b that for $3x + 1$ to be even $x$ has to be odd. Since $x$ is odd, $x = 2k + 1$ for any $k \in Z$.

Therefore $5(2k + 1) - 2$ = $10k + 5 - 2$ = $10k + 3$ = $10k + 2 + 1$ = $2(5k + 1) + 1$. Since $5k + 1$ is an integer, $2(5k + 1) + 1$ is an odd integer.

Theorem 2a: Subtracting an even number from an odd number yields an odd number.

Proof via direct proof. Assume $m,n \in Z$, $m$ is odd, $n$ is even, then: $m = 2a + 1$ and $n = 2b$.

$m - n$ = $(2a + 1) - 2b$ = $2a - 2b + 1$ = $2(a - b) + 1$. Since $a-b$ is an integer, $2(a - b) + 1$ is an odd integer.

Theorem 2: If $5x - 2$ is odd, then $3x + 1$ is even.

We know via 1a and 2a that for $5x - 2$ to be odd, $x$ must be odd. So, $x = 2k + 1$ for $k \in Z$. Therefore:

$3(2k + 1) + 1$ = $6k + 4$ = $2(3k + 2)$. Since $3k + 2$ is an integer, $2(3k + 2)$ must be an even integer. $\blacksquare$

Since this is the first time I've needed to establish intermediate results I was wondering if this approach is correct.

$\endgroup$
2
  • 4
    $\begingroup$ Your approach is correct, but it is very complicated! Note that the difference is $2x-1$, which is an odd number. THis means that they cannot be both odd or both even. $\endgroup$
    – Crostul
    Nov 21, 2015 at 9:48
  • $\begingroup$ Hehe, the next chapter starts with a proof even/odd using the parity of integers. $\endgroup$
    – Apeiron
    Nov 21, 2015 at 10:37

1 Answer 1

4
$\begingroup$

If they have the same parity, then their sum is divisible by two.

but you have $(3x+1)+(5x-2)=8x-1=2(4x-1)+1$ odd. so they need to have different parities.

$\endgroup$
1
  • $\begingroup$ Right, so that insight would've saved me a lot of work :) $\endgroup$
    – Apeiron
    Nov 21, 2015 at 10:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .