2
$\begingroup$

I tried to prove this by contradiction. I used contradiction to show that if $n$ is odd then $5n^2 - 3$ is even; but my Professor said this is not a correct answer to the question: you need to prove that if $5n^2 - 3$ is even then $n$ is odd. Why is what I said wrong, and how do I fix it?

$\endgroup$
  • 2
    $\begingroup$ Your error is in the direction of implication. "If $5n^2-3$ is even, then $n$ is odd" is not the same thing as "If $n$ is odd, then $5n^2-3$ is even." They both happen to be true, but they are not structurally equivalent. $\endgroup$ – Brian Tung Dec 14 '15 at 1:21
  • $\begingroup$ Your prof probably would have accepted a proof that demonstrated that if $n$ is even then $5n^2+3$ is odd $\endgroup$ – WW1 Dec 14 '15 at 1:31
1
$\begingroup$

Suppose $5n^2-3=k$, where $k\in\mathbb{N}$ is even. Then $$ 5n^2=k+3$$ and we know that $k+3$ is odd. Next, we have $$ n^2=\frac{k+3}{5}$$ which must be odd, because any odd divided by an odd is odd. Finally, we have that $$n=\sqrt{{\frac{k+3}{5}}}.$$ The square root of any odd perfect square must also be odd, so we know that $n$ is odd.

$\endgroup$
1
$\begingroup$

$$5n^2-3=2k+1$$

$$5n^2=2k+4$$

So $n^2$ must be even. So $n$ is even.

$\endgroup$
  • $\begingroup$ The questoin has been edited. $\endgroup$ – user236182 Dec 14 '15 at 1:22
0
$\begingroup$

This is kinda soft, but you know that $x^2$, if x is odd positive, is always odd. You also know that odd times odd is also odd. And that odd +odd is even. Therefor you can almost deduce the answer.

$\endgroup$
0
$\begingroup$

$$5n^2-3\equiv 0 \pmod 2 \iff 5n^2\equiv3\pmod 2 $$

As $$5\equiv 1, 3 \equiv 1 \pmod 2$$

We have that

$$5n^2\equiv 3 \pmod 2 \iff n^2 \equiv 1 \pmod 2$$

Suppose $n$ is even, that is $n\equiv 0\pmod 2$, then $n^2\equiv 0 \pmod 2$, thus $n$ is odd.

$\endgroup$
0
$\begingroup$

For contradiction, assume $n$ can be even. Let $n=2k$. Then $5n^2-3=2\left(10k^2-2\right)+1$ is odd, contradiction.

By contraposition, you can prove analogously that if $n$ is even, then $5n^2-3$ is odd.

$\endgroup$
0
$\begingroup$

You were asked to prove that if $5n^2-3$ is even, then n is odd. But what you proved was that if n is odd, then $5n^2-3$ is even.

$A \implies B$ is equivalent to $\neg B \implies \neg A $. So if you prove $\neg B \implies \neg A $, then you've proved $A \implies B$. This is an example of proof by contradiction. Assume the negation of the conclusion. Prove that this leads to a negation of one of your givens.

$A \implies B$ is NOT equivalent to $B\implies A$. For example $(x=2) \implies (x^2=4)$ is true. $(x^2=4) \implies x=2$ is false.

So for your question assume n is even, show that this means $5n^2-3$ is odd. Then you've done the right proof.

Suppose the question asked you to find out if this statement is true or false: "If $2n^2-3$ is odd then n is even". This statement is false because we can have n odd and $2n^2-3$ as odd. But if you assume n is even you will get $2n^2-3$ is odd. So your method would give the wrong result.

$\endgroup$
0
$\begingroup$

Can be shown by a parity argument.

The lowest bit defines the oddness or evenness.

From $5n^2 - 3$ we can easily get the parity of the result as $(1.n_0.n_0)\oplus1$ which gives us $n_o\oplus1$

For the OP, $\oplus$ is the exclusive or operation.

Let the least significant bit of $n$ be $n_0$ ( = parity of $n$ ).

As an even $n$ will be $n_0=0$ the expression's parity is $0\oplus1=1$, which is odd. And of course an odd $n$ will get an even parity.

Can be shown by simple substitution

Another method is simply to try $n = 2k$ and $n = 2k+1$ for an even and odd $n$ respectively.

For $n = 2k$ we get $5n^2-3 = 5(4k^2)-3$ which is always odd.

For $n = 2k+1$ we get $5n^2-3 = 5(4k^2)+5(4k)+5(1)-3$ which is always even.

$\endgroup$
0
$\begingroup$

To prove IF P THEN Q by contradiction you have to prove IF NOT Q and P THEN impossible.

Thus to prove by contradiction:

Assume $5n^2 - 3$ is even and $n$ is even. If $5n^2 - 3$ is even then $5n^2$ is odd. If $n$ is odd then $n^2$ is odd. So $5*n^2 = 5*\text{ an odd number} = 5n^2 = \text {an even number}$. That's a contradiction. So if $5n^2 - 3$ is even th3n $n$ also even is impossible. So n is odd.

One type of proof by contradiction is a proof by contrapositive. To prove IF P THEN Q. You can prove IF NOT Q THEN NOT P (thus the only way P can be true is if Q is also.) (The contradiction is NOT P and P can't both be true.)

A proof by contrapositivve:

Suppose $n$ is even. Then $5n^2$ is even. So $5n^2 - 3$ is odd. So if $5n^2 -3 $ is even, it must be $n$ is odd.

[A third of proof is a direct proof: If $5n^2 - 3$ is even then $5n^2$ is odd. So $n^2$ is odd. So $n$ is odd.]

What you tried to do was

IF Q THEN P. If $n$ is odd then $5n^2 -3$ is even. In this case that happens to be true but it isn't what was meant to be proven.

Consider IF p is a prime > 2 THEN p is odd. You can not prove IF p is odd greater than 2 THEN p is prime. That just isn't true. And it's not a contradiction nor a contrapositive.

That was what your professor objected to, not that you attempted a proof by contradiction.

As it turns out $n$ is odd $\iff 5n^2 - 3$ is even. You tried to prove $n$ odd $\implies 5n^2 - 3$ even. But the exercise was to prove $5n^2 - 3$ even $\implies n$ odd.

$\endgroup$
  • $\begingroup$ Regarding the first paragraph: that's the contrapositive method. When you prove something by contradiction, you can get a contradiction anywhere, not only when "not P". $\endgroup$ – user236182 Dec 14 '15 at 1:31
  • $\begingroup$ True. Careless error on my part. $\endgroup$ – fleablood Dec 14 '15 at 1:33
  • $\begingroup$ To be honest I've been incorrectly including "contrapositive" as a type of proof by contradiction all my life. It's never gotten my into trouble as both are valid methods of proof. (The "contradiction" of a contrapositive is that the premise, which is not used, is proven to be false so if we assume it was always true then we have a contradiction.) But it's incorrect terminology and I shouldn't do it. $\endgroup$ – fleablood Dec 14 '15 at 1:53
  • $\begingroup$ Well, contrapositive is a type of proof by contradiction. Every contrapositve type proof is a proof by contradiction. But not every proof by contradiction is a contrapositive proof. $\endgroup$ – Ameet Sharma Dec 14 '15 at 1:59
  • $\begingroup$ Okay, I personally never use the term "proof by contrapositive" but then I'm not a teacher. Terminology mustn't be abused. $\endgroup$ – fleablood Dec 14 '15 at 2:04

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.