Every child knows this proof:

Assuming that:

$odd(x) = 2a + 1$, where $a \in \mathbb{N} $ and

$even(y) = 2b + 1$, where $b \in \mathbb{N} $ and also

$\lnot odd(x) = even (x)$

$\lnot even(x) = odd (x)$

then: $odd(x) \land even(y) \rightarrow odd (x + y)$ is simply proven by: $$x = 2a + 1 $$ $$y = 2b $$ $$x + y = 2a + 1 + 2b$$ $$x + y = 2(a + b) + 1$$ $$x + y = 2k + 1, k \in \mathbb{N}$$

Therefore $x + y$ is odd, by definition of odd.

I am interested in proving it the other way around: $odd (x + y) \rightarrow odd(x) \land even(y)$

I'm not even really certain how to get started. I cannot assume anything about either $x$ or $y$; the only thing which I can assume is that their sum is odd. Would one have to prove this with a contrapositive? The problem I see with this (might be a case of overthinking) is that:

$$\lnot(odd(x) \land even(y)) \rightarrow \lnot odd(x + y) $$ $$\lnot odd(x) \lor \lnot even(y) \rightarrow \lnot odd(x + y) $$ $$ even(x) \lor odd(y) \rightarrow \lnot odd(x + y) $$

which just seems wrong...

  • $\begingroup$ $odd (x + y) \rightarrow odd(x) \land even(y)$ should read $odd (x + y) \rightarrow (odd(x) \land even(y))\lor (odd(y) \land even(x))$. $\endgroup$ – Michael Hoppe May 6 '18 at 10:08

There are only $4$ cases to consider

  • if $x$ is odd and $y$ is odd, then $x+y$ is even.
  • if $x$ is even and $y$ is even, then $x+y$ is even.
  • if $x$ is odd and $y$ is even, then $x+y$ is odd.
  • if $x$ is even and $y$ is odd, then $x+y$ is odd.

Hence if $x+y$ is odd, and $x$ and $y$ are both integers, we know that $x$ and $y$ have different parity, one of them is odd and one of them is even.

If $x+y$ is odd, then ($x$ is odd and $y$ is even) or ($x$ is even and $y$ is odd).


Let me try:

Given $c=x+y$ ; where $c$ is odd, i.e.

$c= 2k+1 =x +y .$

1)Assume $x,y$ are even, i.e. $2|x$ and $2|y$

then $2|c$, a contradiction,

since $c=2k+1$.

Hence it is not true that both $x$ and $y$ are even.

Hence $x$ is odd or $y$ is odd.

2) Assume both $x$ and $y$ are odd, then

$x= 2m+1$; $y=2n+1$ , and

$x+y = 2(m+n)+2$, a contradiction

since $c=x+y = 2k+1.$

3) Hence:

Either $x$ or $y$ is odd, not both.


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.