3
$\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$
  • 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 '15 at 9:48
  • $\begingroup$ Hehe, the next chapter starts with a proof even/odd using the parity of integers. $\endgroup$ – Apeiron Nov 21 '15 at 10:37
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$
  • $\begingroup$ Right, so that insight would've saved me a lot of work :) $\endgroup$ – Apeiron Nov 21 '15 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.