# How can my proof be improved? “Let $n$ be an integer. If $3n$ is odd then so is $n$.”

I am attempting to self-study proof techniques and your criticism of my following proof would be greatly appreciated. Feel free to nitpick minor/trivial things; that's how I'll learn!

Edit: I have appended a revised proof with the criticisms received so that other rookies can learn from my progress too.

Edit 2: And another, third time lucky?

Theorem: Let $n$ be an integer. If $3n$ is odd then $n$ is odd.

Let $P$ be the sentence "$3n$ is odd" and $Q$ be the sentence "$n$ is odd." We therefore have;

$$P \rightarrow Q$$

By the law of the contrapositive, we may obtain;

$$\lnot Q \rightarrow \lnot P$$

Which is translates to "If $n$ is not odd then $3n$ is not odd", or put another way; "If $n$ is even then $3n$ is even."

If an integer $n$ is even then there exists some integer $m$ such that;

$$n = 2m$$

By multiplying this by $3$ we may obtain;

$$3n = 6m \equiv n = 2m$$

It has therefore been shown that if $n$ is even so is $3n$ and that this is equivalent to showing that if $3n$ is odd then so is $n$.

Attempt 2, taking into consideration previous criticism

Theorem: Let $n$ be an integer. If $3n$ is odd then $n$ is odd.

Let $P$ be the sentence "$3n$ is odd" and $Q$ be the sentence "$n$ is odd." We want to show that $$P \rightarrow Q$$ and that by taking contrapositives this is equivalent to showing $$\lnot Q \rightarrow \lnot P$$ which translates to;

"If $n$ is not odd then $3n$ is not odd", or put another way; "If $n$ is even then $3n$ is even."

If an integer $n$ is even then there exists some integer $m$ such that;

$$n = 2m$$

By multiplying this by $3$ we may obtain;

$$3n = 6m$$

This must still be even as an even integer multiplied by an odd integer produces an even one.

We must now show that $3n$ is even. If this is so, then $6m = 2k$ for some integer $k$.

As $3n=6m=2k$ we have;

$3n=2k$

It has therefore been shown that if $n$ is even so is $3n$ and that this is equivalent to showing that if $3n$ is odd then so is $n$.

Attempt 3

Theorem: Let $n$ be an integer. If $3n$ is odd then $n$ is odd.

Let $P$ be the sentence "$3n$ is odd" and $Q$ be the sentence "$n$ is odd." We want to show that $$P \rightarrow Q$$ and that by taking contrapositives this is equivalent to showing $$\lnot Q \rightarrow \lnot P$$ which translates to;

"If $n$ is not odd then $3n$ is not odd", or put another way; "If $n$ is even then $3n$ is even."

If an integer $n$ is even then there exists some integer $m$ such that;

$$n = 2m$$

By multiplying this by $3$ we may obtain;

$$3n = 6m$$

Which can be rewritten as;

$$3n = 2(3m)$$

Thus we have shown that $3n$ is even, as it is equal to $2(3m)$ which, as an integer multiplied by 2, must be even.

It has therefore been shown that if $n$ is even so is $3n$ and that this is equivalent to showing that if $3n$ is odd then so is $n$.

-
the two comments below are very constructive, however, for this problem, there is not need to solve it the way you did. It would suffice to say that if 3n is odd, then 3n=2n+n. Since 2n is even, and the only way even + something=odd is if the something is odd. So, n must be odd. – picakhu Jan 31 '11 at 19:50
The edited content, which includes the last displayed equation, is indeed all that is needed. (As a grammatical aside, you are abusing the semicolon something awful; most of the ones you use should be colons, because you are using them as annunciatory punctuation). – Arturo Magidin Feb 1 '11 at 3:19
@Arturo duly noted thanks! – Danny King Feb 1 '11 at 19:02

The very end of the proof is not very clear. First, there is no reason to go from $3n=6m$ back to $n=2m$. Instead, in order to show that $3n$ is even, you must show that it can be written as $2k$ for some integer $k$. So what you want is to take $3n=6m$, and express $6m$ as $2k$ for some $k$. That will prove that $3n$ is even (which you haven't as yet, at least not explicitly).

I don't know what kind of course this is for; if it is for an "introduction to proofs" course, chances are you are required to be very explicit about what you are doing, so the opening of your argument is likely required and good. Later, you should be free to summarize the entire first three paragraphs of your proof into: "We proceed by contrapositive: suppose $n$ is even. Then..."

Comment on the addition: The claim that "this must be even because an even integer multiplied by an odd integer produces an even one" relies on a statement that, for all I know, has not been proven, and which is far more general than is needed here.

Simply write $3n$ as 2 x <some integer> explicitly. Given that you know that $3n$ is equal to $6m$, it should be a trivial matter to express it that way.

Second: it's not the equation that "must be even". Equations (like statements) are neither even nor odd. It is integers that are even or odd (in this context); so what is the "This" it refers to? If "This" refers to $3n$, then the next line is unnecessary, but then this sentence amounts to asserting what you are trying to prove (instead of proving it).

Third: Given that you say you have to show that $3n$ is even, you cannot simply say "If this is so..." and proceed. That would mean that you are assuming what you want to prove in order to prove it, which of course is a circular argument. Of course you have concluded that $3n$ is even in that paragraph: you began by assuming it's even.

I think that you have convinced yourself that there is a clever trick or some deep thing that needs to go into showing that $3n$ is even. There isn't. There is a simple, nay, trivial algebraic manipulation that you need to do from your equation $3n=6m$ that will show that $3n$ is indeed even, and that is all you need to do.

-
Thanks very much Arturo. Actually it's not for any course, I'm just working through "Reading, Writing and Proving" by Daepp & Gorkin for fun in my own time, so I'm especially grateful for your advice as I have no professor to ask. My motivation is to be able to read and write proofs well. – Danny King Jan 31 '11 at 19:27
@Danny King: My suggestion is: 'unaccept' my answer, and edit your question by adding your new attempt (perhaps following a horizontal line, with <hr/>), and labeling it as an addition so people are clear Qiaochu's and mine answer reflects your original material. Then we can address your new attempt. – Arturo Magidin Jan 31 '11 at 20:03
I have been trying to improve my proof with your and Qiaochu Yuan's criticisms however I would like to clarify one detail. Fact A: $3n = 6m$ must be even because I multiplied an even statement ($n = 2m$) by an odd integer ($3$) which necessarily produces an even statement. Fact B: Letting $6m=2k$ yields $3n=6m=2k$ and therefore $3n=2k$ proving 3n is also even. So my question is: given facts A & B, does that prove that $n=2m \rightarrow 3n=2k$ ? Thanks! – Danny King Jan 31 '11 at 20:12
@Danny King: To prove that a number is even, you want to show that it can be expressed as $2k$ for some integer $k$. For instance, to prove that 100 is even, I can say: "$100 = 2(50)$, therefore $100$ is even". So to prove that $6m$ is even, you want to find some way of expressing it in the form $2k$ for some $k$. Your fact "A" is badly worded: statements are neither even nor odd. What you mean is that $3n$ should be even because $n$ is even, and an even number times an odd number is even. But that is more general than what you are trying to prove. (..cont) – Arturo Magidin Jan 31 '11 at 20:24
@Danny King: (..cont) Unless you've already shown that multiplying an even number by an odd number gives an even number, you cannot invoke it. And if you have already proven it, then it would be obvious how to show that $6m$ is an even number. But the point is: you cannot assume that $6m=2k$ in order to show that $6m$ is even (which is what you are trying to prove here); that amounts to assuming what you want to prove. You have to produce the $k$ that shows this. And I suspect you are trying very hard to do something which is very easy. How do you write $6m$ as $2$ times something? – Arturo Magidin Jan 31 '11 at 20:27

Your argument is structured as if you were arguing from your conclusion. The correct way to state this argument is "we want to show that $P \Rightarrow Q$, and by taking contrapositives this is equivalent (you also did not say this) to showing that $\neg Q \Rightarrow \neg P$."

I guess you are using $\equiv$ to mean "is equivalent to," but this is usually reserved for an equivalence relation on mathematical objects, not on mathematical statements. For statements you should use $\Leftrightarrow$.

And, of course, Arturo's comments are spot-on.

-
Ah okay thank you for those points, that actually cleared up some doubts I had. – Danny King Jan 31 '11 at 19:28